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

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

Если pпростое число и a не делится на p, то a p — 1 1 (mod p)  (или p — 1 — 1 делится на p).

Или, в другой формулировке,

Для любого простого p и целого a, p — a делится на p.

Содержание

Доказательство

Докажем, что для любого простого p и целого неотрицательного a, apa делится на p. Доказываем индукцией по a.

База. Для a=0, apa = 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}

Но kpk делится на 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, истинность теоремы следует из a2a = 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 года.

См. также

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home