Работа с длинными числами

Давайте для удобства считать, что и , иначе вычтем целую часть дробей, не изменив дробную часть, получив и в нужном диапазоне (условие на несократимость дробей останется). Скажем, что

(1)

— количество цифр в записи , – количество цифр в записи ( и — периоды наших дробей).

Рассмотрим последовательно написанный раз (такая последовательность в первой дроби есть), по условию она же есть, и во второй, причём в ней цифр, значит, во второй дроби эта последовательность является сдвигом , записанным раз. Тогда скажем, что во второй дроби построенная последовательность перед первым имеет кусок , оставшийся кусок из назовём , то есть . Тогда эта же последовательность во второй дроби выглядит как , , написанный раз, и остаток , причём . Обозначим рассматриваемую последовательность за (), тогда:

(2)

(3)

Скажем, — количество цифр в , —- количество цифр в . Тогда верно следующее:

(4)

(5)

(6)

Вычитая (2) из (4) и (5) из (6) соответственно, получаем:

(7)

(8)

Подставим из (7) равенства в (8), получим:

Вспомним, что пары чисел и взаимно просты. Значит, и .

Докажем, что и взаимно просты. Из (1):

ибо и взаимно просты.

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