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

ОРЕ О.

Если числа имеют общий делитель, больший единицы, то они также имеют общий простой делитель.

Итак, два числа могут быть взаимно простыми только тогда, когда они не имеют общих простых множителей, поэтому условие (4.2.1) означает, что числа а и b не имеют общих простых множителей, т. е. все их простые множители различны.

Вернемся к началу этой главы, где мы приводили дробь а/b к простейшему виду. Если d₀ есть наибольший общий делитель чисел а и b, то мы можем написать

a = a₀d₀, b = b₀d₀. (4.2.2)

Тогда

a/b = a₀d₀/b₀d₀ = a₀/b₀. (4.2.3)

В

формуле (4.2.2) числа а₀ и b₀ не могут иметь простых общих множителей, в противном случае числа а и b имели бы общин множитель, больший, чём d₀. Следовательно,

D(a₀, b₀) = 1. (4.2.4)

Это означает, что для второй дроби в формуле (4.2.3) дальнейшее сокращение невозможно.

Одним из часто применяемых свойств взаимно простых чисел является следующее.

Если произведение ab делится на число с, которое взаимно просто с числом b, то число а делится на с.

Доказательство. Так как число с делит произведение ab, то простые множители числа с содержатся среди простых множителей чисел а и b. Но так как D(b, c) = 1, то их не может быть среди множителей числа b. Таким образом, все простые множители числа с делят число а, но не делят число b, и они появляются в числе а в степенях, не меньших, чем в числе с, так как число с делит ab.

Позже мы используем другой факт.

Если произведение двух взаимно простых чисел является квадратом,

ab = c², D(a, b) = 1, (4.2.5)

то числа а и b являются квадратами:

а = а₁², b = b₁². (4.2.6)

Доказательство. Для того чтобы некоторое число было квадратом, необходимо и достаточно, чтобы все степени в разложении его на простые множители были четными. Так как числа а и b — взаимно простые (4.2.5), то любой простой множитель из с² содержится либо в а, либо в b, но не в обоих; отсюда простые множители чисел а и b должны иметь четные степени.

Система задач 4.2.

1. Какие числа взаимно простые с числом 2?

2. Почему D(n, n + 1) = 1?

3. Исследуйте пары дружественных чисел в табл. 2 (стр. 45) и найдите те из них, которые взаимно просты.

4. Может ли правило, выраженное в формулах (4.2.5) и (4.2.6), быть справедливым не только для квадратов, но и для произвольных степеней?

§ 3. Алгоритм Евклида

Вновь вернемся к нашим дробям а/b. Если а > b, то дробь является числом, большим 1, и мы часто разделяем ее на целую часть и правильную дробь, меньшую единицы.

Примеры. Мы пишем

32/5 = 6 + 2/5 = 6 2/5, 63/7 = 9 + 0/7 = 9.

В общем случае мы используем деление с остатком

чисел а

и b (a ≥ b), а именно:

a = qb + r, где 0 ≤ r ≤ b—1. (4.3.1)

Рис. 14.

Очевидно, что это всегда возможно. Действительно, рассмотрим числа 0, 1, 2… на числовой прямой (рис. 14). Где-то на этой прямой расположено число а. Начиная от точки 0 станем отмечать точки b, 2b, Зb и т. д. до точки qb такой, что qb не больше, чем а, в то время как (q + 1)b уже больше а. Расстояние от точки qb до точки а и есть r. Мы называем число r остатком при делении (4.3.1), a q — частным. Это частное q встречается столь часто, что имеется специальный символ для его обозначения:

q = [a/b].

Этот символ обозначает наибольшее целое число, не превосходящее числа а/b. Для примеров, приведенных выше, получим

[32/5] = 6, [63/7] = 9.

В предыдущем разделе мы исследовали наибольший общий делитель двух натуральных чисел а и b:

d₀ = D(a, b). (4.3.2)

Чтобы найти число d₀, мы полагали, что мы знаем разложения чисел а и b на простые множители. Однако нахождение таких разложений может оказаться очень трудным занятием для больших чисел. Существует совсем другой метод для нахождения наибольшего общего делителя, который не использует подобных разложений. Он основан на следующем:

Если a = qb + r, где 0 ≤ r ≤ b—1, то

D(a, b) = d = D(r, b). (4.3.3)

Доказательство. Запишем

d₀ = D(a, b), d₁ = D(r, b).

Таким образом, доказательство соотношения (4.3.3) означает доказательство того, что d₀ = d₁. Любой общий делитель чисел а и b также делит число

r = а — qb.

Следовательно, число r делится на d₀.

Так как число d₀ является делителем как числа r, так и числа b, то оно должно делить и число d₁ = D(b, r); отсюда d₁ ≥ d₀. С другой стороны, в соответствии с соотношением (4.3.1) любой общий делитель чисел r и b делит число а, откуда число d₁ делит число а. Так как число d₁ делит также и число b, то оно должно делить и число d₀ = D(a, b), следовательно, d₀ ≥ d₁. Из сказанного следует, что d₀ = d₁.