Малая теорема Ферма

Малая теорема Ферма — классическая теорема теории чисел, утверждает что

Если p — простое число и a не делится на p, то a p — 1 ≡ 1 (mod p)  (или a p — 1 — 1 делится на p). Малая теорема Ферма/рамка Или, в другой формулировке, Для любого простого p и целого a, (a p — a) делится на p. Малая теорема Ферма/рамка Доказательство   Докажем, что для любого простого p и целого неотрицательного a, $a^p-a$ делится на p. Доказываем индукцией по a. База. Для a=0, $a^p-a = 0$ и делится на p. Переход. Пускай утверждение верно для a=k. Докажем его для a=k+1. $a^p-a = (k+1)^p-(k+1) = k^p+1+\sum_{l=1}^{p-1} {p \choose l} k^l - k-1 =$ $= k^p - k + \sum_{l=1}^{p-1}k^l {p \choose l}$ Но $k^p-k$ делится на p по предположению индукции. Что же касается остальных слагаемых, то ${p \choose l} = {p! \over l!(p-l)!}$. Для $1 \le l \le p-1$, числитель этой дроби делится на p, а знаменатель — не делится, следовательно, ${p \choose l}$ делится на $p$. Таким образом, вся сумма $k^p - k + \sum_{l=1}^{p-1} {p \choose l}$ делится на p. Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2, истинность теоремы следует из $a^2-a=a(a-1)$Шаблон:ЧТД Обобщения теоремы Небольшое обобщение теоремы таково: если p простое число, а m и n — такие положительные целые числа, что $m\equiv n\pmod{p-1}$, тогда $a^m\equiv a^n\pmod{p} \quad\forall a\in\mathbb{Z}$. В данной форме теорема используется в системе шифрования с открытым ключом RSA. Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа. Малая теорема Ферма также имеет изящное обобщение в теории конечных полей. Псевдопростые числа Eсли a и p взаимно простые числа, такие что $a^{p-1} - 1$ делится на p, то число p может не быть простым. В случае, когда p является составным, p называется псевдопростым по основанию a. Ф.Саррус в 1820 году нашёл 341 = 11×31 — первое псевдопростое число, по основанию 2. Число p, являющееся псевдопростым по основанию a для всех a, взаимно простых с p, называется числом Кармайкла (например, 561 — наименьшее из чисел Кармайкла). История Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к Френиклю содержало следующее положение: p делит $a^{p-1}$ в случае, когда p является простым числом и a взаимно простое с p. Ещё в древности китайским математикам была известна гипотеза (иногда называемая Китайской гипотезой), что p является простым числом в том и только в том случае, когда $2^p \equiv 2 \pmod {p}$ (фактически, особый случай малой теоремы Ферма). Тем не менее, обратное утверждение (о том, что из $2^p \equiv 2 \pmod {p}$ следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными, см. выше. Существует широко распространённое предположение, что китайская гипотеза была выдвинута примерно за 2000 лет до аналогичных работ Ферма в 1600-х. Стоит отметить, что гипотеза могла быть известна и другим математикам древности, даже несмотря на то, что она оказалась частично неверной. Тем не менее, в некоторых источниках (Ribenboim, 1995) утверждается, что предположение относительно столь раннего появления гипотезы является распространённым заблуждением, а в действительности гипотеза была выдвинута лишь в 1872 году. Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года. См. также Великая теорема Ферма Сильное псевдопростое число Система шифрования с открытым ключом RSA Ссылки С. Г. Гиндикин Малая теорема Ферма // Квант. — 1972. — № 10. Википедия Малая теорема Ферма адрес Викисловарь — адрес Викицитатник — адрес Викиучебник — адрес Викитека — адрес Викиновости — адрес Викиверситет — адрес Викигид — адрес Выделить Малая теорема Ферма и найти в: Вокруг света теорема Ферма адрес Академик теорема Ферма/ru/ru/ адрес Астронет адрес Элементы теорема Ферма+&search адрес Научная Россия теорема Ферма&mode=2&sort=2 адрес Кругосвет теорема Ферма&results_per_page=10 адрес Научная Сеть Традиция — адрес Циклопедия — адрес Викизнание — теорема Ферма адрес Google Bing Yahoo Яндекс Mail.ru Рамблер Нигма.РФ Спутник Google Scholar Апорт Онлайн-переводчик Архив Интернета Научно-популярные фильмы на Яндексе Документальные фильмы Список ru-вики Вики-сайты на русском языке Список крупных русскоязычных википроектов Каталог wiki-сайтов Русскоязычные wiki-проекты Викизнание:Каталог wiki-сайтов Научно-популярные сайты в Интернете Лучшие научные сайты на нашем портале Лучшие научно-популярные сайты Каталог научно-познавательных сайтов НАУКА В РУНЕТЕ: каталог научных и научно-популярных сайтов Страница 0 - краткая статья Страница 1 - энциклопедическая статья Разное - на страницах: 2 , 3 , 4 , 5 Прошу вносить вашу информацию в «Малая теорема Ферма 1», чтобы сохранить ее Комментарии читателей: