Приглашение в теорию чисел

ОРЕ О.

Возьмем затем х = 2, у = 1 и найдем, что

3^p = (2 + 1)^p ≡ 2^p + 1^p;

теперь, используя предыдущий результат, 2^p ≡ 2 (mod p), получаем

2^p + 1^p ≡ 2 + 1 ≡ (mod p).

Итак, 3^p ≡ 3 (mod p).

Далее для х = 3, у = 1 получаем

4^p ≡ 4 (mod p).

Используя этот процесс, можно доказать по индукции, что а^p ≡ a (mod p) для всех значений числа

а = 0, 1…. р – 1. (7.5.6)

Случаи a = 0 и а = 1 очевидны. Так как каждое число сравнимо (mod р) с одним из остатков, записанных в (7.5.6), мы делаем вывод:

для любого целого числа а и любого простого числа р

a^p ≡ a (mod p). (7.5.7)

Это утверждение обычно называют теоремой Ферма, хотя некоторые авторы называют ее малой теоремой Ферма, чтобы отличить от последней теоремы Ферма, или гипотезы Ферма, о которой мы упоминали в § 3 главы 5.

Пример. Для р = 13 и а = 2 мы находим: 13 = 8+ 4 + 1, т. е. 2¹³ = 2⁸⁺⁴⁺¹ = 2⁸  2⁴ • 2¹. Так как 2⁴ = 16 ≡ 3 (mod 13), 2⁸ ≡ 9(mod 13), то

2¹³ = 2⁸ • 2⁴ • 2 ≡ 9 • 3 • 2 ≡ 2 (mod 13),

как и утверждает теорема Ферма.

В соответствии с правилом сокращения для сравнений, сформулированном в конце § 3, мы можем сократить общий множитель а в обеих частях записи теоремы Ферма (7.5.7) при условии, что число а взаимно просто с числом р, являющимся модулем сравнения. Это дает следующий результат:

если а является целым числом, не делящимся на простое число р, то

a^{p– 1} ≡ 1 (mod p). (7.5.8)

Этот результат также называют теоремой Ферма.

Пример. Когда а = 7, р = 19, мы находим, что

7² = 49 ≡ 11 (mod 19)

7⁴ ≡ 121 ≡ 7 (mod 19),

7⁸ ≡ 49 ≡ 11 (mod 19),

7¹⁶ ≡ 121 ≡ 7 (mod 19),

и это дает

a^{p– 1} = 7¹⁸ = 7¹⁶ • 7² ≡ 7 • 11 ≡ 1 (mod 19),

что соответствует утверждению (7.5.8).

В качестве приложения теоремы Ферма вновь рассмотрим треугольники Пифагора, обсужденные в гл. 5 и докажем следующее утверждение:

произведение длин сторон треугольника Пифагора делится на 60.

Доказательство. Очевидно, достаточно доказать это для простейших треугольников. В соответствии с формулой (5.2.7), это

произведение есть

Р = 2mn (m² — n²) (m² + n²) = 2mn (m⁴ — n⁴).

Число Р делится на 60 тогда и только тогда, когда оно делится на 4, на 3 и на 5. Так как одно из чисел m и n четно, то 2mn, а следовательно, и число Р, делится на 4. Оно делится на 3, если хотя бы одно из чисел m или n делится на 3, но если ни одно из них не делится на 3, то Р все же будет делиться на 3, так как из условий (7.5.8), а также D(m, 3) = 1 и D (n, 3) = 1 следует, что m² ≡ 1 (mod 3) и n² ≡ 1 (mod 3), так что

m² — n² ≡ 1 – 1 = 0 (mod 3).

Аналогично, число Р делится на 5. Это очевидно, если m или n делится на 5. Если ни одно из них не делится на 5, то вновь по теореме Ферма (7.5.8) получаем

m⁴ — n⁴ ≡ 1 – 1 = 0 (mod 5).

ГЛАВА 8

НЕКОТОРЫЕ ПРИМЕНЕНИЯ СРАВНЕНИЙ

§ 1. Проверка вычислений

Как мы уже упоминали, создателем теории сравнений был немецкий математик Карл Фридрих Гаусс. Его знаменитая работа по теории чисел «Арифметические исследования» появилась в 1801 году, когда ему было 24 года. В первых главах этой книги рассказывается о теории сравнений. Однако здесь следует упомянуть, что следы теории сравнений можно обнаружить за несколько столетий до Гаусса. Некоторые из них присутствуют в древних правилах проверки арифметических вычислений. Они составляют существенную часть инструкции по арифметическим операциям эпохи Ренессанса. Некоторые из них используются до сих пор, а из всего того, что нам известно об их происхождении, можно сказать, что их корни лежат в античности.

Мы не знаем, каким образом эти правила были впервые введены, однако попытаемся указать один из возможных путей, на котором они могли быть открыты. Вернемся к временам счетных досок. На таком абаке каждая цифра в числах, которые участвовали в вычислениях, обычно выкладывалась с помощью фишек, камней, палочек или орехов, причем каждая группа отмечала количество единиц, десятков, сотен и т. д. в соответствии с местом их нахождения. В нашей десятичной системе число

N = a_n10ⁿ + a_{n– 1}10^{n– 1} +… + a₂10² + a₁10 + a₀ = (a_n, a_{n– 1}…, a₂, a₁, a₀)₁₀ (8.1.1)