Задача 1: Числа a и b взаимно просты, ac делится на b. Докажите, что c делится на b.

Решение: Найдутся числа x и y такие, что ax – by = 1. Домножив это равенство на c, получим acx – bcy = c, из которого и следует, что .

Задача 2: Числа a и b взаимно просты, c делится на a, c делится на b. Докажите, что c делится на ab.

Решение: Найдутся числа x и y такие, что ax – by = 1. Домножив это равенство на c, получим acx – bcy = c, из которого и следует, что .

Задача 3: Докажите, что  НОД  двух чисел делится на произвольный общий делитель этих чисел.

Решение: Существуют x и y, что (a,b) = ax + by. Рассмотрим произвольный общий делитель d чисел a и b. Т.к. правая часть делится на d, то и (a,b) делится на d.

Задача 4: Числа a и b взаимно просты. Докажите, что для любого натурального c. Докажите, что  НОД (a,bc) =  НОД (a,c)

Указание: Докажите, что наборы общих делителей совпадают.

Решение: ax + by = 1, значит acx + bcy = c…

Задача 5: Докажите, что любое натуральное число представляется в виде отношения 99-ой степени некоторого натурального числа и 19-ой степени некоторого натурального числа.

Задача 6: Фальшивомонетчик Вова взял два взаимно простых числа m и n и нарисовал кучу купюр достоинством в m и n рублей. Докажите, что он сможет без сдачи набрать ими любую сумму начиная с mn рублей.