Говоря о свойствах, присущих простым числам, невозможно не упомянуть малую теорему Ферма.
Формулируется она следующим образом:
Для любого простого p и взаимно простого с ним натурального n: n^(p-1)- 1 делится на p.
История
Самые наблюдательные читатели уже догадались, что теорему сформулировал никто иной, как Пьер де Ферма :) В 1640 году Ферма написал письмо французскому математику Бернару Френиклю с формулировкой этой теоремы, однако доказать её не смог (удивительно, что математик не смог найти то простое и короткое доказательство, которое мы привели ниже). В 1683 году Готфрид Вильгельм Лейбниц доказал теорему, причём он сформулировал её независимо от Ферма. Теорема не выстояла и перед Эйлером: он доказал её в 1736 году. Была найдена ещё целая куча доказательств, но здесь мы приведём самое простое из них.
Доказательство
Напомним, что натуральные числа a и b называются сравнимыми по модулю m, если они дают одинаковые остатки при делении на m (т.е. их разность делится на m). Пишется: a ≡ b (mod m). Докажем такой факт: если ak ≡ bk (mod m), то a ≡ b (mod m) при некотором натуральном k, взаимно простом с m. Итак, ak ≡ bk (mod m), то есть ak - bk = k(a-b) делится на m. Это значит, что левая часть равенства содержит все простые множители, которые содержит m. Но k не содержит ни одного простого множителя, который есть в m, т.к. они взаимно просты. Значит, все простые множители, которые есть в m содержатся именно в a-b. То есть a-b делится на m, или a ≡ b (mod m).
Перейдем к доказательству. Рассмотрим числа n, 2n, 3n, ... pn. Никакие два из этих чисел не дают одинаковые остатки при делении на p. Почему это так? Предположим противное, т.е. нашлись такие i и j, что in ≡ jn (mod p). Самое время вспомнить вышеприведённый факт, а также то, что n и p взаимно просты. Это значит, что мы с чистой совестью можем сократить на n. Итак, i ≡ j (mod n). Но постойте, i и j меньше p и никак не могут давать одинаковые остатки при делении на p (ведь их остаток - это и есть сами числа). Стало быть, мы пришли к противоречию, то есть все числа n, 2n, 3n, ... pn имеют различные остатки при делении на p. Найдём произведение этих чисел. Оно равно (p-1)!*n^(p-1) и сравнимо с (p-1)! по модулю p. Т.е. (p-1)!*n^(p-1) ≡ (p-1)! (mod p). Что здесь можно заметить? Конечно же, (p-1)! и p взаимно просты. Вновь применяем вышеприведенный факт и получаем n^(p-1) ≡ 1 (mod p). То есть n^(p-1)- 1 делится на p. Мы победили! Малая теорема Ферма доказана!
Малая теорема Ферма - красивейший математический факт, играющий роль в таких областях как кодирование, программирование и шифрование.
Не забывайте подписываться на канал, ставить лайк и писать в комментариях идеи для статей!