Задача 60887

Темы:    [ Периодические и непериодические дроби ] [ Функция Эйлера ] [ Арифметика остатков (прочее) ]

Сложность: 4- Классы: 10,11

Условие

Пусть  (m, n) = 1.  Докажите, что сумма длин периода и предпериода десятичного представления дроби  ^m/_n  не превосходит φ(n).

Решение

При делении m на n в столбик будут получаться остатки, взаимно простые с n. Поскольку таких чисел всего φ(n), то остаток повторится не позже, чем на шаге  φ(n) + 1.  С этого момента и начнётся второй период.

Замечания

Пусть  n = 2^a3^bk,  где  (k, 10) = 1,  и  c = max{a, b}.  Тогда дробь  10^c·^m/_n  чисто периодическая, и длина её периода не превосходит φ(k). Дробь ^m/_n имеет тот же период и предпериод длины c. Таким образом сумма длин периода и предпериода не превосходит  φ(k) + c.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	5
Название	Числа, дроби, системы счисления
Тема	Системы счисления
параграф
Номер	2
Название	Десятичные дроби
Тема	Десятичные дроби
задача
Номер	05.049