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

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

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-110^n-1 +… + a₂10² + a₁10 + a₀ = (a_n, a_n-1…, a₂, a₁, a₀)₁₀ (8.1.1)

потребовало бы для своей записи

S_N = a_n + a_n-1 +… + а₂ + а₁ + а₀ (8.1.2)

фишек. Это число мы называем суммой цифр числа N.

Теперь предположим, что мы хотим выполнить на доске простое действие, а именно: сложить два числа N и M. Тогда мы должны отметить на доске также второе число

M = (b_m, b_m-1, …, b₂, b₁, b₀)₁₀,

у которого на тех же линиях лежит

S_M = b_m + b_m-1 + … + b₂ + b₁ + b₀

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

S_N+M ≡ S_N + S_M (mod 9), (8.1.3)

т. е. количество фишек, находящихся на доске, должно отличаться от первоначального общего числа фишек на число, кратное 9. Эта проверка (8.1.3) до сих пор сохранила свое старое название «выбрасывание девяток».

После того как это правило было открыто, не составило труда заметить, что оно также применимо при сложении нескольких чисел, при вычитании и при умножении; в последнем случае, в соответствии с (8.1.3),

S_M S_N ≡ S_MN (mod 9). (8.1.4)

Теоретическое доказательство этих правил является легкой задачей при использовании сравнений. Очевидно, что

1 ≡ 1, 10 ≡ 1, 10² ≡ 1, 10³ ≡ 1… (mod 9); (8.1.5)

таким образом, из (8.1.1) и (8.1.2) мы делаем вывод, что

N ≡ S_N (mod 9).    (8.1.6)

Поэтому из правил сравнений, которые мы установили в § 3 главы 7, ясно, что

S_N ± S_M ≡ N ± М ≡ S_{N ± M},

S_N • S_M = N •M ≡ S_N•M (mod 9).

Правило «выбрасывания девяток» чаще всего применяется к умножению. Возьмем в качестве примера числа