Даны два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел 
и 
делится на 
(А. Голованов)
Будем решать обобщенную задачу. Дано натуральное число n и два нечетных натуральных числа a и b. Докажите, что существует такое натуральное k, что хотя бы одно из чисел 
и 
делится на 
Воспользуемся следующим известным утверждением: пусть число 
дает остаток 
при делении на 
где 
Тогда 
дает остаток 
при делении на 
Пусть 
делится на 
и не делится на 
а 
делится на 
и не делится на 
Очевидно, что при этом 
Тогда дает остаток при делении на а дает остаток при делении на 
Пусть 
положим для краткости 
По лемме число
дает остаток при делении на
Будем решать задачу индукцией по n. Если 
то нам подойдет 
поскольку 
и 
дают равные остатки при делении на 
Сделаем переход от n к 
По индукционному предположению при некотором k число делится на 
Если оно делится и на 
то переход сделан. Иначе оно дает остаток 
при делении на 
Пусть 
Тогда по лемме 
дает остаток при делении на 
Следовательно, 
дает остаток при делении на Воспользуемся формулой разности степеней:
Первая скобка дает остаток при делении на вторая состоит из r нечетных слагаемых и, значит, нечётна. Стало быть, разность 
дает остаток при делении на Но тогда
делится на поскольку выражения в скобках дают одинаковые остатки при делении на