Малая теорема Ферма — классическая теорема теории чисел, утверждает что
Если p — простое число и a не делится на p, то ap — 1≡1 (mod p) (или a p — 1 — 1 делится на p).
Малая теорема Ферма/рамка
Или, в другой формулировке,
Для любого простого p и целого a, (a p — a) делится на p.
Малая теорема Ферма/рамка
Доказательство
Докажем, что для любого простого p и целого неотрицательного a, делится на p. Доказываем индукцией по a.
База. Для a=0, и делится на p.
Переход. Пускай утверждение верно для a=k. Докажем его для a=k+1.
Но делится на p по предположению индукции. Что же касается остальных слагаемых, то . Для , числитель этой дроби делится на p, а знаменатель — не делится, следовательно, делится на . Таким образом, вся сумма делится на p.
Для отрицательных a и нечётных p теорему легко доказать подстановкой b=-a. Для отрицательных a и p=2, истинность теоремы следует из Шаблон:ЧТД
Небольшое обобщение теоремы таково: если p простое число, а m и n — такие положительные целые числа, что , тогда . В данной форме теорема используется в системе шифрования с открытым ключом RSA.
Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа.
Малая теорема Ферма также имеет изящное обобщение в теории конечных полей.
Псевдопростые числа[]
Eсли a и pвзаимно простые числа, такие что делится на p, то число p может не быть простым. В случае, когда p является составным, p называется псевдопростым по основанию a. Ф.Саррус в 1820 году нашёл 341 = 11×31 — первое
псевдопростое число, по основанию 2.
Число p, являющееся псевдопростым по основанию a для всех a, взаимно простых с p, называется числом Кармайкла (например, 561 — наименьшее из чисел Кармайкла).
История[]
Пьер Ферма сформулировал исходное утверждение теоремы около 1636 года. Письмо от 18 октября 1640 года Пьера Ферма к Френиклю содержало следующее положение: p делит в случае, когда p является простым числом и a взаимно простое с p.
Ещё в древности китайским математикам была известна гипотеза (иногда называемая Китайской гипотезой), что p является простым числом в том и только в том случае, когда (фактически, особый случай малой теоремы Ферма). Тем не менее, обратное утверждение (о том, что из следует, что p простое), а, следовательно, и гипотеза в целом, оказались неверными, см. выше.
Существует широко распространённое предположение, что китайская гипотеза была выдвинута примерно за 2000 лет до аналогичных работ Ферма в 1600-х. Стоит отметить, что гипотеза могла быть известна и другим математикам древности, даже несмотря на то, что она оказалась частично неверной. Тем не менее, в некоторых источниках (Ribenboim, 1995) утверждается, что предположение относительно столь раннего появления гипотезы является распространённым заблуждением, а в действительности гипотеза была выдвинута лишь в 1872 году.
Сам Ферма оставил свою теорему без доказательства. Первым, кому удалось его найти, был Готфрид Вильгельм Лейбниц, в рукописях которого утверждается, что доказательство ему было известно до 1683 года.