Maths Olympiad Prep

Library / /89 of 152

Number theory Difficulty 6.7 National Olympiad Prove it Russia

Each of positive rational numbers aa and bb has the minimal period of length 30 in the decimal notation. A number aba-b has the minimal period of length 15 in a decimal notation. Find the least positive integer kk for which it may happen that the length of the minimal period of the number a+kba+kb in the decimal notation is also 15. (A. Golovanov)

Solution

Домножив, если нужно, числа aa и bb на подходящую степень десятки, мы можем считать, что десятичные записи чисел a,b,aba, b, a-b и a+kba+kb — чисто периодические (то есть периоды начинаются сразу после запятой).

Воспользуемся следующим известным фактом: десятичная запись рационального числа rr — чисто периодическая с (не обязательно минимальной) длиной периода TT тогда и только тогда, когда rr имеет вид m10T1\frac{m}{10^{T}-1} для некоторого целого mm.

Применительно к условию задачи это значит, что a=m10301a = \frac{m}{10^{30}-1} и b=n10301b = \frac{n}{10^{30}-1}. Нам также известно, что числа ab=mn10301a-b = \frac{m-n}{10^{30}-1} и a+kb=m+kn10301a+kb = \frac{m+kn}{10^{30}-1} записываются десятичными дробями с периодом длины 15, то есть могут быть записаны как обыкновенные дроби со знаменателем 1015110^{15}-1. Поэтому так может быть записана и их разность (k+1)b=(k+1)n10301(k+1)b = \frac{(k+1)n}{10^{30}-1}. Таким образом, число (k+1)n(k+1)n делится на 1015+110^{15}+1, а число nn — не делится (иначе и bb записывалось бы дробью с периодом длины 15). Значит, число k+1k+1 делится на некоторый простой делитель числа 1015+110^{15}+1. Наименьший из таких делителей — это 7. Действительно, число 1015+110^{15}+1 даёт остаток 1 при делении на 2 и на 5, а также остаток 2 при делении на 3. С другой стороны, оно делится на 103+1=714310^3+1 = 7 \cdot 143. Итак, k+17k+1 \ge 7 и k6k \ge 6.

В некотором смысле минимальный пример чисел, удовлетворяющих условию при k=6k = 6, получается, если положить ab=110151a - b = \frac{1}{10^{15}-1} и a+6b=210151a + 6b = \frac{2}{10^{15}-1}. Тогда a=87(10151)a = \frac{8}{7(10^{15}-1)} и b=17(10151)b = \frac{1}{7(10^{15}-1)}. Ясно, что длины минимальных периодов чисел aba-b и a+6ba+6b равны 15. Далее, длины минимальных периодов чисел aa и bb больше 15 и делятся на 15 (так как 10T110^T - 1 должно делиться на 1015110^{15} - 1). С другой стороны, так как 10301=7(10151)10^{30} - 1 = 7(10^{15} - 1), числа aa и bb периодичны с длиной периода 30. Значит, длины их минимальных периодов равны 30.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.