Question

Пусть a и b – натуральные числа. Докажите, что среди чисел a, 2a, 3a, ..., ba ровно (a, b) чисел делится на b.

Answer 1

Ответ:

(a, b)

Пошаговое объяснение:

Пусть a=(a, b)*l, b=(a, b)*k; k,l∈N. Тогда (l, k)=1 [(a, b)=((a, b)*l, (a, b)*k)=(a, b)*(l, k) => (l, k)=1].

Число na [n∈N, n≤b] = n*(a, b)*l будет делиться на b=(a, b)*k тогда, и только тогда, когда n*l будет делиться на k. Но (l, k)=1, а тогда это утверждение равносильно тому, что n делится на k.

Осталось найти количество чисел из отрезка [1; b] , делящихся на k.

На k делится каждое k-ое число из этого множества. А тогда количество таких чисел равно [((b-1)+1)/k]=[b/k], где [x] - целая часть числа x.

Но b=(a, b)*k, а тогда [b/k]=[(a, b)*k/k]=[(a, b)]. (a, b), очевидно, число натуральное. А значит искомое кол-во чисел равно [(a, b)]=(a, b)

Answer 2

Для доказательства этого утверждения воспользуемся принципом Дирихле для целых чисел.

Пусть существуют два числа i и j (1 ≤ i < j ≤ b) такие, что ij ≡ 0 (mod b). То есть, ij делится на b без остатка. Разделим это уравнение на i, предполагая, что i и b взаимно просты (так как (i, b) = 1):

j ≡ 0 (mod b)

Учитывая, что j находится в диапазоне от 1 до b, мы получаем j = 0. Но это противоречит условию, что 1 ≤ j ≤ b. Таким образом, нет двух чисел i и j таких, что ij ≡ 0 (mod b).

Теперь рассмотрим числа a, 2a, 3a, ..., ba. Если некоторое число k удовлетворяет условию ka ≡ 0 (mod b), то это означает, что ka делится на b без остатка. Предположим, что существует два числа i и j (1 ≤ i < j ≤ b) такие, что ia ≡ ja (mod b). Тогда (j - i)a ≡ 0 (mod b), и, исходя из доказанного выше, (j - i) должно быть равно 0 (mod b).

Поэтому, (j - i) = kb для некоторого целого числа k. Тогда j = i + kb. Поскольку 1 ≤ i < j ≤ b, получаем, что 1 ≤ i < i + kb ≤ b. Но это противоречит условию, что i и j должны быть различными. Таким образом, нет двух чисел i и j таких, что ia ≡ ja (mod b).

Из этого следует, что все числа вида ka (1 ≤ k ≤ b) различны по модулю b. При этом b возможных остатков по модулю b. Поэтому, среди чисел a, 2a, 3a, ..., ba ровно (a, b) чисел будет делиться на b.