Оценочная теория чисел

Докажем, что подойдут все дроби, у которых числитель и знаменатель отличаются на а также все дроби, у которых числитель и знаменатель нечетны и отличаются на степень двойки. С дробями первого вида все понятно, а дроби второго вида особенны потому, что если числитель и знаменатель увеличить на то разность их не изменится и останется степенью двойки. Но два нечетных числа, отличающиеся на степень двойки, очевидно, взаимно просты, иначе их разность делилась бы на их нечетный НОД, что невозможно.

Посчитаем, сколько таких дробей. Дробей первого вида Дроби второго вида, у которых числитель и знаменатель отличаются на это т.е. Нужно сложить эти выражения по всем Получится Также нужно учесть неправильные дроби, поэтому всего их Значит, в сумме выходит

Докажем, что все остальные дроби не подходят. Если и четные, то дробь сократима. Остаются дроби, у которых числитель и знаменатель отличаются на у которого есть нечетный делитель Но такая дробь не может быть особенной, поскольку можно выбрать нечетное число кратное и большее, чем и и взять или (хотя бы одно из этих чисел натуральное, поскольку нечетно, и хотя бы одно из и нечетно). Тогда дробь будет сократима на поскольку ее числитель или знаменатель, по построению, будет равен а значит будет делиться на но разность числителя и знаменателя также кратна т.е. и числитель и знаменатель кратны т.е. дробь сократима.

Остаётся рассмотреть дроби вида но в случае они сократимы, а в случае такая дробь сократима для всех