Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

2. Теорема Ферма

В XVII столетии Ферма, основатель современной теории чисел, открыл чрезвычайно важную теорему. Если р - простое число, не делящее целого числа а, то

аp-1 ≡ 1 (mod p).

Другими словами, (р - 1)-я степень а при делении на р дает остаток 1.

Некоторые из ранее произведенных нами вычислений подтверждают эту теорему: так, мы видим, что 106 ≡ 1 (mod 7), 102 ≡ 1 (mod 3) и 1010 ≡ 1 (mod 11). Таким же образом легко проверить, что 212 ≡ 1 (mod 13) и 510 ≡ 1 (mod 11). Для этой цели нет необходимости на самом деле вычислять столь высокие степени данных чисел; достаточно использовать мультипликативное свойство сравнений:


Обращаясь к доказательству теоремы Ферма, рассмотрим числа, кратные а:

m1 = а, m2 = 2а, m3 = 3а, ..., mp-1 = (р-1)а.

Никакие два из этих чисел не могут быть между собой сравнимы по модулю р. В противном случае р должно было бы делить разность mr - ms = (r - s)а, где r, s была бы пара целых чисел, подчиненных ограничению 1≤r<s≤(р - 1). Но из закона 7) следует, что этого не может случиться: так как s - r меньше, чем р, то р не делит s - r; с другой стороны, по предположению, р не делит и а. Таким же образом мы убеждаемся, что ни одно из чисел m не сравнимо с нулем. Отсюда следует, что числа m1, m2, ..., mp-1 соответственно сравнимы с числами 1,2, ...,р-1, взятыми в некоторой их перестановке. Дальше заключаем:

m1m2...mp-1 = 1*2*3*...*(p-1)ap-1 ≡ 1*2*3*...*(p-1) (mod p),

или же, полагая ради краткости К = 1*2*3*...*(р - 1),

K(ap-1-1) ≡ 0 (mod p).

Число К не делится на р, так как ни один из входящих в него множителей не делится на р, значит, согласно закону 7) (ар-1 - 1) должно делиться на р, т. е.

аp-1 - 1 ≡ 0 (mod p).

Это и есть теорема Ферма.

Проверим эту теорему еще раз. Возьмем р = 23 и а = 5; тогда получаем по модулю 23 52 ≡ 2, 54 ≡ 4, 58 ≡ 16 ≡ - 7, 516 ≡ 49 ≡ 3, 520 ≡ 12, 522 ≡ 24 ≡ 1. Если возьмем а = 4 вместо 5, то будем иметь опять-таки по модулю 23 42 ≡ - 7, 43 ≡ - 28 ≡ - 5, 44 ≡ - 20 ≡ 3, 48 ≡ 9, 411 ≡ - 45 ≡ 1, 422 ≡ 1. В примере, где было взято а = 4, р = 23 (как и во многих иных), можно заметить, что не только (р - 1)-я степень, но и более низкая степень а уже оказывается сравнимой с единицей. Наименьшая такая степень - в нашем примере степень 11 - непременно есть делитель числа р - 1 (см. ниже, упражнение 3).

Упражнения.

1)С помощью подобных же вычислений проверить, что

28 ≡ 1 (mod 17); 38 ≡ - 1 (mod 17); 314 ≡ -1 (mod 29); 214 ≡ - 1 (mod 29); 414 ≡ 1 (mod 29); 514 ≡ 1 (mod 29).

2) Проверить теорему Ферма, взяв р = 5, 7, 11, 17 и 23 и придавая числу а различные значения.

3) Доказать общую теорему: Наименьшее число е, для которого ае ≡ 1 (mod р), должно быть делителем р-1.

[Указание. Произвести деление р-1 на е, получая

р - 1 = ke + r,

где 0≤r<e, и дальше воспользоваться тем обстоятельством, что аp-1 ≡ ае ≡ 1 (mod р).]

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Зачем математики ищут простые числа с миллионами знаков?

Задача построения новых оснований математики - унивалентные основания

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru