Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2000/02/27.pdf Дата изменения: Fri Dec 23 19:25:44 2005 Дата индексирования: Tue Oct 2 00:13:07 2012 Кодировка: Windows-1251 Поисковые слова: m 13

ШКОЛА

В

'КВАНТЕ'

27
тельно,

Числа вида 99...9
Взглянем на равенства 1/7 = = 0,(142857) и 1/13 = 0,(076923). Заметьте: 142857 7 = 999999 и 76923 13 = 999999. Это не случайность: как вы помните, в правиле преобразования чисто периодической дроби в обыкновенную фигурирует число 10 1 = 9K9 . Поэтому мы займемся числами этого вида. Лемма 1. Для всякого натурального числа k, не кратного ни 2, ни 5, существует такое натуральное число r, для которого разность 10r 1 кратна n. Доказательство. Первый способ для любителей многоточий. Рассмотрим k чисел: 9, 99, 999, ..., 99K9 . 13 2 Докажем, что хотя бы одно из них кратно k. Предположим противное: пусть ни одно из них не кратно k. Поскольку количество ненулевых остатков от деления на k равно k 1, какие-то два из k рассматриваемых чисел дают одинаковые остатки при делении на k. Разность этих чисел нацело делится на k и представляет из себя несколько девяток, после которых написано несколько нулей:
99K9 - 99K9 = 99K900K0 1 3 1 3 1 31 3. 2 2 22
r+ s s r s k r r

где t натуральное тельство завершено6 .
Упражнения

число5

. Доказа-

m k

=

mt kt

= mt

1 10 - 1
r

.

;

13. Сколько чисел, кратных 13, имеется среди первых ста чисел последовательности 1, 11, 111, ...? 14. Если число вида 11...1 кратно 7, то оно кратно и 11, и 13, и 15873. Докажите это. 15. Первую цифру k-значного числа, кратного 13, стерли и записали позади последней цифры этого числа. При каких k полученное число кратно 13? (Например, из кратных 13 чисел 503906 и 7969 таким образом получаем числа 39065 и 9697, первое из которых кратно 13, а второе нет.) 16. Для каких пар натуральных чисел (m, n), где n > 1, число 100K01 кратно 13 2 числу 11K1 ? 13 2
n

Воспользовавшись равенством r 1/(10 1) = 0,( 00K0 1), получаем 13 2

m k

= mt 0, 00K01 . 13 2
r -1 r

b

r -1

g

Поскольку m < k, то mt < kt < 10 , так что произведение числа mt на число 0, 00K01 это периодическая дробь, 13 2

b

m

Поскольку k взаимно просто с 10, из делимости числа 99K900K0 на k сле1 31 3 22
r s

дует, что число 99K9 нацело делится 13 2
r

17. а) Если p простое число и наименьший период десятичного разложения дроби 1/p состоит из 2n цифр, то сумма двух n-значных чисел (могущих начинаться и с нуля), образованных первыми n и последними n цифрами периоn да, равна 10 1. Докажите это. (Например, 1/13 = 0,(076923), при этом 76 + + 923 = 999. Простота знаменателя существенна: 1/21 = 0,(047619), но 47 + + 619 999.) б) Длина наименьшего периода десятичного представления дроби 1/p, где p простое число, четна в точности тогда, когда p является делитеn лем некоторого числа вида 10 + 1. Докажите это. 18. а) Найдите длину наименьшего периода десятичного представления дроби 1/31. б) Докажите, что никакое число вида 100...01 не кратно 31. 19 (М981). Докажите, что число 11...1 (1986 единиц) имеет по крайней мере а) 8; б) 128; в*) 1024 различных делителя.

длина периода которой равна r, а период десятичная запись числа mt, возможно, дополненная слева необходимым количеством нулей. Нам осталось только понять, почему наименьшему возможному числу r соответствует наименьший возможный период. Но это сразу ясно из правила перевода периодической десятичной дроби в обыкновенную. Теорема 2 доказана. Она вполне ясно характеризует длину r периода чисто периодической десятичной дроби. А если есть предпериод, то надо вспомнить равенство c- a c-b m m2 5 c = :10 , ab k 25k и ответ станет очевиден: Следствие теоремы 2. Длиной наименьшего периода десятичного представления несократимой дроби m/n, ab где n = 2 5 k , a,b 0 и НОД(k,10) = = 1, является такое наименьшее наr туральное число r, что 10 1 кратно k. Следствие следствия теоремы 2. Длина наименьшего периода десятичного представления несократимой дроби m/n зависит только от знаменателя n, а не от числителя m.

r -1

g

на k. Лемма доказана.
Второй способ для тех, кто не любит многоточия. Рассмотрим числа 1, 10, 102 , ..., 10k -1 . Ни одно из них не кратно k. Поскольку количество ненулевых остатков от деления на k равно k 1, какието два из k рассматриваемых чисел дают одинаковые остатки при делении на k. Разность этих чисел:
10
r+ s

Длина периода
Теорема 2. Если m, n взаимно простые натуральные числа, причем n взаимно просто с 10 и m < n, то в десятичном представлении дробь m/n является чисто периодической. Длина ее наименьшего периода это такое наименьшее натуральное число r, что 10r 1 кратно n. Доказательство. По лемме 1, 10r 1 = kt для некоторых натуральных чисел r и t. Следоваn 1234

Функция L(n)
Обозначим через L(n) длину наименьшего периода десятичного представления дроби 1/n (см. таблицу 1). В силу ab следствия теоремы 2, если n = 2 5 k , где a,b 0 и НОД(k,10) = 1, то L(n) = L(k) = r, где r это наименьшее r натуральное число, для которого 10 1 кратно k. Таблица 1
5 1 6 7 8 1 9 10 11 12 13 14 15 16 17 1 12 1 6 61 1 16 16

- 10 ,

s

где 0 s < r + s < k , нацело делится на k.

Из
s

10 10 - 1 на k и из взаимной просто-

ты чисел 10 и k следует, что 10 1 кратно k, т.е.
10 1 = kt,
7*
r

FH

делимости
r

IK

произведения
r

L(n) 1

11

1

5 Например, для k = 7 можно взять r = = 6; при этом t = (106 1)/7 = 142857. 6 Между прочим, оно замечательно не только отсутствием многоточий, но и тем, что показывает: существует нужное нам число r < k, а не только r k .

Функция L определена на всем множестве натуральных чисел7 , но в дей7 Напоминаем, что в доказательстве теоремы 1 мы договорились периодом конечной десятичной дроби считать число 1.