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)