<<

стр. 2
(всего 9)

СОДЕРЖАНИЕ

>>

Докажите, что n! делится на 2n?r , но не делится на 2n?r+1 .
3.104. Результат предыдущей задачи допускает обобщение. Пусть
p — простое число и представление числа n в p-ичной системе имеет
вид:
n = ak pk + ak?1 pk?1 + . . . + a1 p1 + a0 .
Найдите формулу, выражающую показатель ?p , с которым это число p
входит в каноническое разложение n!, через n, p и коэффициенты ak .
3.105. При помощи формулы Лежандра из задачи 3.101 докажите,
1
Cn (n 0) всегда целое. (См. также 2.115.)
что число 2n
n+1
(2m)! (2n)!
3.106. Докажите, что число (m, n 0) всегда целое.
m! n! (m + n)!
n!
3.107. Существует ли такое целое r, что число n?r является целым
2
при любом n 1?

4. О том, как размножаются кролики
Определение. Последовательность чисел Фибоначчи
{F0 , F1 , F2 , . . . } = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, . . . }
задается условиями F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn (n 0).
4. О том, как размножаются кролики 37

Эти числа были впервые описаны в «Книге абака» (1202 г.) итальян-
ского математика Леонардо Пизанского (Фибоначчи).
3.108. Задача Леонардо Пизанского. Некто приобрел пару кро-
ликов и поместил их в огороженный со всех сторон загон. Сколько
кроликов будет через год, если считать, что каждый месяц пара дает
в качестве приплода новую пару кроликов, которые со второго месяца
жизни также начинают приносить приплод?
3.109. О том, как прыгают кузнечики. Предположим, что име-
ется лента, разбитая на клетки и уходящая вправо до бесконечности. На
первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик
может перепрыгнуть либо на одну, либо на две клетки вправо. Сколь-
кими способами кузнечик может добраться до n-й от начала ленты
клетки? (См. также 3.114.)
3.110. Некоторый алфавит состоит из 6 букв, которые для передачи
по телеграфу кодированы так:
· ·· ·? ?·
? ??
При передаче одного слова не сделали промежутков, отделяющих букву
от буквы, так что получилась сплошная цепочка из точек и тире, содер-
жащая 12 знаков. Сколькими способами можно прочитать переданное
слово?
3.111. Чему равны числа Фибоначчи с отрицательными номерами
F?1 , F?2 , . . . , F?n , . . . ?
3.112. Тождество Кассини. Докажите равенство
Fn+1 Fn?1 ? F2 = (?1)n (n > 0).
n

Будет ли тождество Кассини справедливо для всех целых n? (См.
также 12.13.)
3.113. Докажите следующие свойства чисел Фибоначчи:
а) F1 + F2 + . . . + Fn = Fn+2 ? 1; в) F2 + F4 + . . . + F2n = F2n+1 ? 1;
г) F2 + F2 + . . . + F2 = Fn Fn+1 .
б) F1 + F3 + . . . + F2n?1 = F2n ; 1 2 n

3.114. Докажите, что при n 1иm 0 выполняется равенство
Fn+m = Fn?1 Fm + Fn Fm+1 .
Попробуйте доказать его двумя способами: при помощи метода ма-
тематической индукции и при помощи интерпретации чисел Фибоначчи
из задачи 3.109. Докажите также, что тождество Кассини является
частным случаем этого равенства.
38 3. Алгоритм Евклида и основная теорема арифметики

3.115. Докажите равенства
а) F2n+1 = F2 + F2 ;
n n+1
б) Fn+1 Fn+2 ? Fn Fn+3 = (?1)n+1 ;
в) F3n = F3 + F3 ? F3 .
n n+1 n?1

3.116. Вычислите F4 ? Fn Fn+1 Fn+3 Fn+4 .
n+2

3.117. Вычислите сумму
1 2 Fn
+ + ... + .
1·2 1·3 Fn?1 · Fn+1

3.118. Делимость чисел Фибоначчи. Докажите справедливость
следующих утверждений:
а) 2 | Fn ?? 3 | n; в) 4 | Fn ?? 6 | n;
б) 3 | Fn ?? 4 | n; г) Fm | Fn ?? m | n.
3.119. Докажите, что для любого натурального m существует число
Фибоначчи Fn (n 1), кратное m.
3.120. Пусть первое число Фибоначчи, делящееся на m есть Fk .
Докажите, что m | Fn тогда и только тогда, когда k | n.
3.121. Докажите, что два соседних числа Фибоначчи Fn?1 и Fn
(n 1) всегда взаимно просты.
3.122* . Теорема Люка. Докажите равенство (Fn , Fm ) = F(m,n) .
(См. также 3.141.)
3.123. В последовательности чисел Фибоначчи выбрано 8 чисел,
идущих подряд. Докажите, что их сумма не является числом Фибо-
наччи.
3.124. Рассмотрим множество последовательностей длины n, состо-
ящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите,
что количество таких последовательностей равно Fn+2 . Найдите вза-
имно однозначное соответствие между такими последовательностями и
маршрутами кузнечика из задачи 3.109.
3.125. Фибоначчиева система счисления. Докажите, что про-
извольное натуральное число n, не превосходящее Fm , единственным
образом можно представить в виде
m

n= b k Fk ,
k=2

где все числа b2 , . . . , bm равны 0 либо 1, причем среди этих чисел нет
двух единиц стоящих рядом, то есть bk bk+1 = 0 (2 k m ? 1).
4. О том, как размножаются кролики 39

Для записи числа в фибоначчиевой системе счисления используется
обозначение:
n = (bk . . . b2 )F .
(См. также 12.14, 4.193 .)
3.126. Формула Бине. Докажите по индукции формулу Бине:
?n ? ?n
v
Fn = ,
5
v v
1+ 5 1? 5
где ? = — «золотое сечение» или число Фидия, а ? =
2 2
(«фи с крышкой») — сопряженное к нему. (См. также 11.43, 11.75.)
3.127. Докажите следующий вариант формулы Бине:
[(n?1)/2]
n?1
Cn 5k .
2 Fn = 2k+1
k=0

(См. также 4.129.)
3.128. Докажите, что число Фибоначчи Fn совпадает с ближайшим
?n
целым числом к v , то есть
5
?n 1
Fn = v + .
2
5
3.129. Числа Фибоначчи и треугольник Паскаля. Докажите
равенство:
C0 + C1 + C2 + . . . = Fn+1 .
n n?1 n?2

Сумма, стоящая в левой части равенства, может быть интерпретиро-
вана, как сумма элементов треугольника Паскаля, стоящих в одной
диагонали (См. приложение В, II и задачи 2.67, 3.124, 11.44 и 11.45.)
3.130. Вычислите сумму:
Sn = C0 ? C1 + C2 ? . . .
n n?1 n?2

(См. также 11.44, 11.45.)
3.131. Сколько существует последовательностей из 1 и 2, таких что
сумма чисел в каждой такой последовательности равна n? Например,
если n = 4, то таких последовательностей пять:
11111, 112, 121, 211, 22.
3.132. Решите в целых числах уравнение
x · ?n+1 + y · ?n = 1.
40 3. Алгоритм Евклида и основная теорема арифметики

Определение. Последовательность чисел Люка
{L0 , L1 , L2 , . . . } = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, . . . }
задается равенствами L0 = 2, L1 = 1, Ln+2 = Ln+1 + Ln (n 0).
3.133. Докажите, что числа Люка связаны с числами Фибоначчи
соотношениями:
а) Ln = Fn?1 + Fn+1 ;
б) 5 Fn = Ln?1 + Ln+1 ;
в) F2n = Ln · Fn ;
г) L2 + L2 = 5F2n+1 ;
n+1 n
д) Fn+2 + Fn?2 = 3Fn .
(См. также 9.79, 11.41.)
3.134. В вершинах правильных многоугольников записываются чис-
ла 1 и 2. Сколько существует таких многоугольников, что сумма чисел
стоящих в вершинах равна n (n 3)? Две расстановки чисел, которые
можно совместить поворотом не отождествляются.
3.135. Выразите Ln в замкнутой форме через ? и ?. (См. также
11.77.)
3.136. Докажите равенства
v v
7+3 5 4 7?3 5
4
а) ? = 1;
2 2
v v
11 + 5 5 9 76 ? 34 5
5
б) + = 1.
2 2
Найдите общую формулу, для которой данные равенства являются
частными случаями.
3.137* . Решите в целых числах уравнения:
а) x2 ? xy ? y2 = 1;
б) x2 ? xy ? y2 = ?1.
3.138. а) Докажите, что в последовательности чисел Фибоначчи при
m 2 встречается не менее 4 и не более 5 m-значных чисел.
б) Докажите, что число F5t+2 (t 0) содержит в своей десятичной
записи не менее t + 1 цифры.
3.139. Рассмотрим алгоритм Евклида из задачи 3.36 состоящий из k
шагов. Докажите, что начальные числа m0 и m1 должны удовлетворять
неравенствам m1 Fk+1 , m0 Fk+2 .
3.140. Теорема Ламе. Пусть число m1 в десятичной системе счис-
ления записывается при помощи t цифр. Докажите, что при любом m0
5. Цепные дроби 41

число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет
неравенству k 5t.
3.141. Фибоначчиевы коэффициенты.
1
1 1
1 1 1
1 2 2 1
1 3 6 3 1
1 5 15 15 5 1
1 8 40 60 40 8 1
1 13 104 260 260 104 13 1

Данная таблица аналогична треугольнику Паскаля и состоит из фи-
k
боначчиевых коэффициентов Fn , определяемых равенством
Fn · Fn?1 · . . . · Fn?k+1
k
Fn = (0 k n).
Fk · Fk?1 · . . . · F1
а) Докажите, что фибоначчиевы коэффициенты обладают свой-
k k
ством симметрии Fn = Fn?k .
k?1
k
б) Найдите формулу, которая выражает коэффициент Fn через Fn?1
k
и Fn?1 (аналогичную равенству б) из задачи 2.77).
в) Объясните, почему все фибоначчиевы коэффициенты являются
целыми числами.
3.142* . Обобщенные биномиальные коэффициенты. Пусть
A1 , A2 , . . . — последовательность ненулевых целых чисел, такая, что
(m, n
(Am , An ) = A(m,n) 1).
Докажите, что все обобщенные биномиальные коэффициенты
An · An?1 · . . . · An?k+1
Ak =
n
Ak · Ak?1 · . . . · A1
являются целыми числами. (См. также 8.89.)

5. Цепные дроби
Определение. Пусть a0 — целое, a1 , a2 , . . . , an — натуральные и
an > 1. n-членной цепной (непрерывной) дробью называется выражение
1
(3.1)
a0 +
1
a1 +
a2 + . . . 1
+
an
42 3. Алгоритм Евклида и основная теорема арифметики

(обозначается [a0 ; a1 , a2 , . . . , an ]).
Числа a1 , a2 , . . . , an называются неполными частными дроби (3.1).
147 129
3.143. Разложите в цепные дроби числа и .
13 111
Pn
3.144. Пусть = [1; 1, . . . , 1 ]. Чему равны Pn и Qn ?
Qn
n

3.145. Как связано разложение рационального числа в цепную
дробь с алгоритмом Евклида?
3.146. Геометрическая интерпретация алгоритма Евклида.
Работу алгоритма Евклида (см. раздел 2) можно представить следую-
щим образом. В прямоугольник размерами m0 ? m1 (m1 m0 ) укла-
дываем a0 квадратов размера m1 ? m1 , в оставшийся прямоугольник
размерами m1 ? m2 (m2 m1 ) укладываем a1 квадратов размера
m2 ? m2 , и т. д. до тех пор, пока весь прямоугольник не покроется
квадратами. (См. также 3.157.)
Выразите общее число квадратов через элементы цепной дроби чис-
ла m1 /m2 .
3.147. Для каждого натурального n приведите пример прямоуголь-
ника, который разрезался бы ровно на n квадратов.
3.148. Цепные дроби и электрические цепи. Для данного ра-
ционального числа a/b постройте электрическую цепь из единичных
сопротивлений, общее сопротивление которой равнялось бы a/b. Как
такую цепь можно получить при помощи разбиения прямоугольника
a ? b на квадраты из задачи 3.146?
3.149. Пусть a0 — целое, a1 , . . . , an — натуральные числа. Опреде-
лим две последовательности
(1
P?1 = 1, P 0 = a0 , Pk = ak Pk?1 + Pk?2 k n);
(1
Q?1 = 0, Q0 = 1, Qk = ak Qk?1 + Qk?2 k n).
Докажите, что построенные последовательности для k = 0, 1, . . . , n
обладают следующими свойствами:
Pk
а) = [a0 ; a1 , a2 , . . . , ak ];
Qk
б) Pk Qk?1 ? Pk?1 Qk = (?1)k+1 ;
в) (Pk , Qk ) = 1.
Определение. Рациональные дроби
Pk
(k = 0, 1, . . . , n)
= [a0 ; a1 , a2 , . . . , ak ]
Qk
5. Цепные дроби 43

называются подходящими дробями к непрерывной дроби (3.1).
3.150. Докажите следующие свойства подходящих дробей:
а) Pk Qk?2 ? Pk?2 Qk = (?1)k ak (k 2);
k+1
(?1)
Pk P
? k?1 =
б) (k 1);
Qk Qk?1 Qk Qk?1
в) Q1 < Q2 < . . . < Qn ;
P0 P P Pn P5 P P
< 2 < 4 < ... < 3 < 1;
г) ... <
Q0 Q2 Q4 Qn Q5 Q3 Q1
P P
д) 2k < 2l+1 (k, l 0).
Q2k Q2l+1
a
3.151. Пусть числа a и b определены равенством = [a0 ; a1 , a2 , . . .
b
. . . , an ]. Докажите, что уравнение ax ? by = 1 c неизвестными x и y
имеет решением одну из пар (Qn?1 , Pn?1 ) или (?Qn?1 , ?Pn?1 ). Отчего
зависит, какая именно из пар является решением?
3.152. Разлагая число a/b в непрерывную дробь, решите в целых
числах уравнения ax ? by = 1, если
a) a = 101, b = 13;
б) a = 79, b = 19.
3.153. Григорианский календарь. Обыкновенный год содержит
365 дней, високосный — 366. n-й год, номер которого не делится на 100,
является високосным тогда и только тогда, когда n кратно 4. n-й год,
где n делится на 100, является високосным тогда и только тогда, когда n
кратно 400. Так, например, 1996-й и 2000-й годы — високосные, а 1997-й
и 1900-й — нет. Эти правила были установлены папой Григорием XIII.
До сих пор мы имели ввиду «гражданский год», число дней которого
должно быть целым. Астрономическим же годом называется период
времени, за который Земля совершает полный оборот вокруг Солнца.
Считая, что «григорианский год» полностью согласован с астрономиче-
ским годом, найдите продолжительность астрономического года. (См.
также 12.7.)
Определение. Бесконечной непрерывной дробью называется выра-
жение вида
1
[a0 ; a1 , . . . , an , . . . ] = a0 +
1
a1 +
a2 + . . . 1
+
an + . . .

где a0 — целое, a1 , a2 , . . . , an , . . . — натуральные числа.
44 3. Алгоритм Евклида и основная теорема арифметики

Величиной бесконечной непрерывной дроби называется предел ее
подходящих дробей, то есть такое число ?, что
Pn
? = lim ,
Qn
n>?

Pn
где = [a0 ; a1 , a2 , . . . , an ].
Qn
3.154. Докажите, что любое иррациональное число ? допускает
представление
? = [a0 ; a1 , . . . , an?1 , ?n ],
где a0 — целое, a1 , a2 , . . . , an?1 — натуральные, ?n > 1 — иррациональ-
ное действительное числа. Отсюда следует, что каждому иррациональ-
ному действительному числу можно поставить в соответствие бесконеч-
ную цепную дробь.
3.155. Докажите, что для любой бесконечной цепной дроби
[a0 ; a1 , . . . , an , . . . ]
существует предел ее подходящих дробей — иррациональное число ?.
Объясните, почему если это число ? разложить в бесконечную цепную
дробь при помощи алгоритма предыдущей задачи, то получится беско-
нечная цепная дробь, равная исходной.
Таким образом, существует взаимно-однозначное соответствие меж-
ду иррациональными числами и бесконечными цепными дробями. По-
этому в дальнейшем будем отождествлять цепную дробь с ее числовым
значением.
3.156. Предположим, что число ? задано бесконечной цепной дро-
бью
? = [a0 ; a1 , . . . , an , . . . ].
Докажите, что
1 1 1 1
? . . . + (?1)n
? = a0 + ? + + ...
q0 q1 q 1 q2 q2 q3 qn qn+1
3.157. Последовательности {ak } и {bk } строятся по следующему за-
кону:
v
a1 = 1, b1 = 2, an+1 = min(an , bn ), bn+1 = |bn ? an | (n 1).
а) Докажите, что an = 0 и an стремится к 0 при n > ?.
б) Докажите, что последовательность cn = a2 + a2 + . . . + a2 имеет
1 2 n
предел и найдите этот предел.
5. Цепные дроби 45

3.158. Юлианский календарь. Из астрономии известно, что год
имеет 365,2420 . . . = [365; 4, 7, 1, 3, . . . ] так называемых «календарных
суток». В Юлианском стиле каждый четвертый год — високосный, то
есть состоит из 366 дней. За сколько лет при таком календаре накап-
ливается ошибка в одни сутки? На сколько дней отстает Юлианский
календарь за 1000 лет? И вообще, почему он отстает, если юлианский
год длиннее астрономического?
3.159. Персидский календарь. Наиболее точный календарь ввел
в Персии в 1079 году персидский астроном, математик и поэт Омар
Альхайями. Восстановите этот календарный стиль, рассмотрев третью
подходящую дробь [365; 4, 7, 1] к длительности астрономического года.
За сколько лет в этом календаре накапливается ошибка в одни сутки?
Определение. Бесконечная непрерывная дробь вида
[a0 ; a1 , . . . , ak , ak+1 , . . . , ak+T , ak+1 , . . . , ak+T , . . . ] =
= [a0 ; a1 , . . . , ak , ak+1 , . . . , ak+T ]
называется периодической с периодом ak+1 , . . . , ak+T . Набор a0 , a1 , . . .
. . . , ak называется предпериодом.
Бесконечная непрерывная дробь вида [ a0 ; a1 , . . . , aT ?1 ] называется
чисто периодической.
3.160. Вычислите следующие цепные дроби:
а) [ 5; 1, 2, 1, 10 ]; б) [ 5; 1, 4, 1, 10 ]; в) [ 2; 1, 1, 3 ].
3.161. Разложите в цепные дроби числа:
v v 1v
а) 2; б) 3; в) + 7.
2
3.162. Формат A4. Найдите наименьшее натуральное n, для кото-
рого существует такое m, что
v m 297
2< < .
n 210
3.163. Числа из электрической розетки. Найдите наименьшее
натуральное n, для которого существует такое m, что
v m 220
3< < .
n 127
(См. [185].)
Определение. Число называется квадратичной иррационально-
стью, если оно является иррациональным корнем некоторого квадрат-
ного уравнения с целыми коэффициентами.
46 3. Алгоритм Евклида и основная теорема арифметики
v
Если ? = b + c d — квадратичная иррациональность, то число ? =
v
= b ? c d называется сопряженным к числу ?.
3.164. Докажите, что значение любой периодической цепной дро-
би — квадратичная иррациональность.
Верно более сильное утверждение.
Теорема Лагранжа. Число разлагается в периодическую цепную
дробь тогда и только тогда, когда оно является квадратичной ирраци-
ональностью. (См. [5], [28].)
3.165. Найдите рациональное число, которое отличается от ? не
более чем v 0,0001, где v
на v
а) ? = 2; б) ? = 2 + 5; в) ? = 3 + 7.
3.166. Докажите равенство:
v v
(1 + 2)n+1 ? (1 ? 2)n+1
v v
[ 2; 2, . . . , 2 ] = .
(1 + 2)n ? (1 ? 2)n
n

3.167* . Теорема Лежандра. Докажите, что если
p 1
?? < 2,
q 2q
p
то — подходящая дробь к числу ?.
q
3.168. Теорема Валена. Докажите, что если pn /qn (n 1) —
подходящая дробь к числу ?, то имеет место по крайней мере одно
из неравенств
pn 1 pn?1 1
или
?? <2 ?? <2.
qn qn?1
2qn 2qn?1
Получите отсюда теорему Валена: для любого ? найдется бесконечно
много дробей p/q таких, что
p 1
?? < 2.
q 2q
3.169* . Докажите, что для любых целых чисел p и q (q = 0),
справедливо неравенство
v p 1
2? > 2.
q 3q
3.170. Докажите, что при k 1 выполняется равенство:
aFk+2 ? 1
= [aFk ; aFk?1 , . . . , aF0 ],
Fk+1
a ?1
5. Цепные дроби 47

где {Fk } — последовательность чисел Фибоначчи.
3.171. Докажите, что положительный корень квадратного уравне-
ния bx2 ? abx ? a = 0, где a и b — натуральные числа, разлагается в
чисто периодическую цепную дробь с длиной периода, равной 2. Верно
ли обратное утверждение?
3.172. Докажите, что если квадратное уравнение с целыми коэф-
фициентами имеет корень x = [ a; b ], то вторым корнем служит число
1
.
?
[ a; b ]
3.173. Докажите, что если положительная квадратичная ирра-
v
A+ D
циональность ? = разлагается в чисто периодическую цеп-
B
ную дробь, то сопряженная ей квадратичная иррациональность ? =
v
A? D
принадлежит интервалу (?1; 0).
=
B
3.174. Докажите, что если квадратное уравнение с целыми коэф-
фициентами имеет корень x = [a; b, c ], то вторым корнем будет число
a ? [ c, b ].
Глава 4
Арифметика остатков

1. Четность
4.1. Пусть m и n — целые числа. Докажите, что mn(m + n) — четное
число.
4.2. Рукопожатия. Каждый из людей, когда-либо живших на зем-
ле, сделал определенное число рукопожатий. Докажите, что число лю-
дей, сделавших нечетное число рукопожатий — четно.
4.3. В прямоугольном треугольнике длины сторон — натуральные
взаимно простые числа. Докажите, что длина гипотенузы — нечетное
число, а длины катетов имеют разную четность.
4.4. На доске написано 10 плюсов и 15 минусов. Разрешается стереть
любые два знака и написать вместо них плюс, если они одинаковы,
и минус в противном случае. Какой знак останется на доске после
выполнения 24 таких операций?
4.5. Из шахматной доски вырезали две противоположные угловые
клетки (a8 и h1). Можно ли оставшуюся часть доски покрыть непере-
крывающимися косточками домино?
4.6. Город имеет форму квадрата 5 ? 5 (см. рисунок). Какую наи-
меньшую длину может иметь маршрут, если нужно пройти по каждой
улице этого города и вернуться в прежнее место? (По
каждой улице можно проходить любое число раз.)
4.7. Может ли ладья перейти из одного угла шах-
матной доски в противоположный угол (по диагона-
ли), побывав по одному разу на всех 64 клетках? Тот
же вопрос для коня.
4.8. Вороны на деревьях. Вдоль улицы стоят 6
деревьев и на каждом из них сидит по вороне. Раз в
час две из них взлетают и каждая садится на одно из соседних деревьев.
Может ли получится так, что все вороны соберутся на одном дереве?
4.9. Термит и 27 кубиков. Представим себе большой куб, скле-
енный из 27 меньших кубиков. Термит садится на центр грани одного
1. Четность 49

из наружных кубиков и начинает прогрызать ход. Побывав в кубике,
термит к нему уже не возвращается. Движется он при этом всегда
параллельно какому-нибудь ребру большого куба. Может ли термит
прогрызть все 26 внешних кубиков и закончить свой ход в центральном
кубике? Если возможно, покажите, каким должен быть путь термита.
4.10. На хоккейном поле лежат три шайбы A, B и C. Хоккеист бьет
по одной из них так, что она пролетает между двумя другими. Так он
делает 25 раз. Могут ли после этого шайбы оказаться на своих местах?
4.11. Все косточки домино выложены в цепь. На одном конце ока-
залось 5 очков. Сколько очков на другом конце?
4.12. Можно ли множество всех натуральных чисел больше 1 раз-
бить на два непустых подмножества так, чтобы для любых двух чисел
a и b из одного множества число ab ? 1 принадлежало другому?
4.13. Дан выпуклый 2n-угольник A1 , . . . , A2n . Внутри него взята
точка P, не принадлежащая ни одной из диагоналей. Докажите, что
точка P принадлежит четному числу треугольников с вершинами в
точках A1 , . . . , A2n .
4.14. В ряд выписаны числа 1, 2, . . . , 10. Можно ли расставить меж-
ду ними знаки «+» и «?» так, чтобы значение полученного выражения
было равно нулю?
4.15* . К 17-значному числу прибавили число, записанное теми же
цифрами, но в обратном порядке. Докажите, что хотя бы одна цифра
полученной суммы четна.
4.16. Улитка ползет по плоскости с постоянной скоростью, каждые
15 минут поворачивая под прямым углом. Докажите, что вернуться в
исходную точку она может лишь через целое число часов.
4.17. Есть 101 монета, из которых 50 фальшивых, отличающихся
по весу на 1 грамм от настоящих. Коля Васин взял одну монету и за
одно взвешивание на весах со стрелкой, показывающей разность весов
на чашках, хочет определить фальшивая ли она. Сможет ли он это
сделать?
4.18. 7 стаканов. На столе стоят 7 стаканов — все вверх дном.
Разрешается за один ход перевернуть любые 4 стакана. Можно ли за
несколько ходов добиться того, чтобы все стаканы стояли правильно?
4.19. В клетках квадратной таблицы 4 ? 4 расставлены знаки +
и ? , как показано на рисунке
+ ? + +
+ + + +
+ + + +
+ + + +
50 4. Арифметика остатков

Разрешается одновременно менять знак во всех клетках, расположен-
ных в одной строке, в одном столбце или на прямой, параллельной
какой-нибудь диагонали (в частности, можно менять знак в любой уг-
ловой клетке). Докажите, что, сколько бы мы ни производили таких
перемен знака, нам не удастся получить таблицу из одних плюсов.
4.20. Марсианские амебы. В пробирке находятся марсианские
амебы трех типов A, B и C. Две амебы любых двух разных типов
могут слиться в одну амебу третьего типа. После нескольких таких
слияний в пробирке оказалась одна амеба. Каков ее тип, если исходно
амеб типа A было 20 штук, типа B — 21 штука, и типа C — 22 штуки?
(См. также 5.78.)
4.21. Игра «Йога». На поле для игры расставлены 32 фишки
(смотрите рис. 1). При взятии одна фишка перескакивает через дру-
гую — почти как в шашках, но не по диагонали, а по горизонтали или
по вертикали. Допустим, в конце игры осталась 1 фишка. Объясните,
почему для ее расположения есть только 5 вариантов, изображенных
на рисунке 2. (См. также 5.79.)



?? 




Рис. 1. Рис. 2.

Указание: Рассадите на поле для игры марсианских амеб. Пусть в
клетках A и B сидят амебы, а клетка C — пустая. Тогда амеба A, пере-
прыгивая через амебу B превращается в амебу C, а амеба B исчезает.
4.22. Код, исправляющий ошибку. Предположим, что требуется
передать сообщение, состоящее из n2 нулей и единиц. Запишем его
в виде квадратной таблицы n ? n. Допишем к каждой строке сумму
ее элементов по модулю 2. Получится еще один столбец высоты n.
Аналогично поступим с каждым столбцом (в том числе найдем и сумму
элементов дописанного столбца). Например, если требуется передать
сообщение 0111, то таблица 2 ? 2 окажется дополненной до таблицы
3 ? 3:
0 1 1
0 1
> 1 1 0
1 1
1 0 1
2. Делимость 51

Докажите, что если при передаче расширенной таблицы (n+1)?(n+1)
произойдет одна ошибка, то эту ошибку можно будет найти и исправить.
Какое наименьшее число ошибок должно произойти, чтобы об этом
нельзя было узнать?

2. Делимость
.
.
4.23. Пусть p > 3 — простое число. Докажите, что p2 ? 1 . 24.
4.24. Докажите, что любое натуральное число, десятичная запись
которого состоит из 3n одинаковых цифр, делится на 37.
4.25. Докажите, что число 11 . . . 1 (1986 единиц) имеет по крайней
мере а) 8; б) 32 различных делителя.
4.26. Докажите, что числа
2001 2001
а) 23 + 1; б) 23 ? 1 — составные.
4.27. Докажите следующие соотношения:
. . .
а) 241 ? 1 . 83; б) 270 + 370 . 13; в) 215 ? 1 . 20801.
. .
.
4.28. Докажите, что для любого простого числа p > 2 числитель
дроби
m 1 1 1
= + + ... +
n 1 2 p?1
делится на p.
4.29. Натуральные числа m и n таковы, что m > n, m не делится
на n и имеет от деления на n тот же остаток, что и m + n от деления
на m ? n. Найдите отношение m : n.
4.30. Даны целые числа a, b, c такие, что a + b + c . 6. Докажите,
.
.
. 6.
3.
3 3
что a + b + c .
.
.
4.31. Докажите, что 1110 ? 1 . 100.
4.32. Сколько имеется различных прямоугольных треугольников,
длины сторон которых выражены целыми числами, если один из кате-
тов этих треугольников равен 15?
4.33. Решите уравнения:
а) 3x2 + 5y2 = 345; б) 1 + x + x2 + x3 = 2y .
4.34. Докажите, что число 11999 + 21999 + . . . + 161999 делится на 17.
4.35. Назовем шестизначное число счастливым, если сумма его пер-
вых трех цифр равна сумме последних трех цифр. Докажите, что сумма
всех счастливых чисел делится на 13.
52 4. Арифметика остатков

4.36. Докажите, что числа от 1 до 2001 включительно нельзя вы-
писать подряд в некотором порядке так, чтобы полученное число было
точным кубом.
77 77
? 77 . 10.
77 .
4.37. Докажите, что 7 .
4.38. Число x таково, что x2 заканчивается на 001 (в десятичной
системе счисления). Найдите три последние цифры числа x (укажите
все возможные варианты).
4.39. Имеется много одинаковых квадратов. В вершинах каждого
из них в произвольном порядке написаны числа 1, 2, 3 и 4. Квадраты
сложили в стопку и написали сумму чисел, попавших в каждый из
четырех углов стопки. Может ли оказаться так, что
а) в каждом углу стопки сумма равна 2004?
б) в каждом углу стопки сумма равна 2005?
4.40. Дан многочлен с целыми коэффициентами. Если в него вместо
неизвестной подставить 2 или 3, то получаются числа, делящиеся на 6.
Докажите, что если вместо неизвестной в него подставить 5, то также
получится число, делящееся на 6.
4.41. Докажите, что в трехзначном числе, делящемся на 37, всегда
можно переставить цифры так, что новое число также будет делится
на 37.
4.42. Докажите, что если p — простое число и 1 p ? 1, то
k
C . p.
.
k
.
p

4.43. Докажите утверждение обратное тому, что было в задаче 4.42:
если Ck . n при 1 k n ? 1, то n — простое число.
.
n.

4.44. Докажите, что если p — простое число и 1 p ? 2, то
k
? Ck?2 . p. Верно ли обратное утверждение?
.
k
C p?k?1 .
p?k+1

4.45. Докажите, что если p — простое число, то при любых целых a
и b выполняется соотношение
(a + b)p ? ap ? bp . p.
.
.
4.46* . Камни лежат в трех кучках: в одной — 51 камень, в другой —
49 камней, а в третьей — 5 камней. Разрешается объединять любые
кучки в одну, а также разделять кучку из четного количества камней на
две равные. Можно ли получить 105 кучек по одному камню в каждой?
В следующих задачах понадобится вспомнить принцип Дирихле из
раздела 2.
4.47. Докажите, что среди любых n натуральных чисел, не деля-
щихся на n, есть несколько чисел, сумма которых делится на n.
3. Сравнения 53

4.48. Докажите, что среди любых десяти последовательных нату-
ральных чисел найдется число, взаимно простое с остальными.
4.49. На 99 карточках пишутся числа 1, 2, . . . , 99. Затем карточки
тасуются и раскладываются чистыми сторонами вверх. На чистых сто-
ронах карточек снова пишутся числа 1, 2, . . . , 99. Для каждой карточки
числа, стоящие на ней, складываются и 99 полученных сумм перемно-
жаются. Докажите, что в результате получится четное число.

3. Сравнения
Определение. Пусть m 1. Два числа a и b называются сравни-
мыми по модулю m, если их разность делится на m. Записывается это
в виде a ? b (mod m).
4.50. Что означают записи:
а) a ? b (mod 0); б) a ? b (mod 1)?
4.51. Свойства сравнений. Докажите, что если a ? b (mod m) и
c ? d (mod m), то
а) a + c ? b + d (mod m); б) ac ? bd (mod m).
Определение. Классом вычетов по данному модулю m называется
множество всех целых чисел сравнимых с некоторым данным целым
?
числом a по модулю m. Такой класс обозначается a.
?
4.52. Докажите, что класс a состоит из всех чисел вида mt + a, где
t — произвольное целое число.
?
?
4.53. Докажите, что два класса a и b совпадают тогда и только
тогда, когда a ? b (mod m).
Определение. Полной системой вычетов по некоторому модулю
называется система чисел, взятых по одному из каждого класса по
этому модулю.
4.54. Докажите, что любые m чисел x1 , . . . , xm попарно несрав-
нимых по модулю m, представляют собой полную систему вычетов по
модулю m.
4.55. Пусть числа x1 , x2 , . . . , xm образуют полную систему вычетов
по модулю m. Для каких a и b числа yj = axj + b (j = 1, . . . , m) также
образуют полную систему вычетов по модулю m?
4.56. Из свойств сравнений следует, что с классами вычетов можно
делать все операции, которые допустимы для целых чисел: складывать,
вычитать, умножать, возводить в степень. Отличие будет лишь в том,
что построенная арифметика действует на конечном множестве классов
54 4. Арифметика остатков

вычетов. Например, для m = 6 получаются такие таблицы сложения и
умножения:
?
+ 012345 012345
0 0 1 2 3 4 5 0 0 0 0 0 0 0
1 1 2 3 4 5 0 1 0 1 2 3 4 5
2 2 3 4 5 0 1 2 0 2 4 0 2 4
3 3 4 5 0 1 2 3 0 3 0 3 0 3
4 4 5 0 1 2 3 4 0 4 2 0 4 2
5 5 0 1 2 3 4 5 0 5 4 3 2 1

Постройте аналогичные таблицы сложения и умножения для модулей
m = 7, 8, . . . , 13.
4.57. Когда сравнения a ? b (mod m) и ac ? bc (mod m) равно-
сильны?
4.58. Равносильны ли сравнения a ? b (mod m) и ac ? bc (mod mc)?
4.59. Имеется 100 камней. Два игрока берут по очереди от 1 до 5
камней. Проигрывает тот, кто берет последний камень. Определите вы-
игрышную стратегию первого игрока. (См. также 5.81.)
4.60. Разочарованный вкладчик фонда «Нефтьалмазинвест» разо-
рвал акцию на 8 кусков. Не удовлетворившись этим, он разорвал один
из кусков еще на 8, и т. д. Могло ли у него получиться 2002 куска?
4.61. Иван-царевич имеет два волшебных меча, один из которых
может отрубить Змею Горынычу 21 голову, а второй — 4 головы, но
тогда у Змея Горыныча вырастает 1999 голов. Может ли Иван отру-
бить Змею Горынычу все головы, если в самом начале у него было 100
голов? (Примечание: если, например, у Змея Горыныча осталось лишь
3 головы, то рубить их ни тем, ни другим мечом нельзя.)
4.62. В магазине было 6 ящиков яблок, массы которых соответствен-
но 15, 16, 18, 19, 20 и 31 килограммов. Две фирмы приобрели 5 ящиков,
причем одна из них взяла по массе яблок в два раза больше, чем другая.
Какой ящик остался в магазине?
4.63. Составьте список всевозможных остатков, которые дают числа
2
n при делении на 3, 4, 5, . . . , 9.
4.64. Докажите, что если все коэффициенты уравнения
ax2 + bx + c = 0
— целые нечетные числа, то ни один из корней этого уравнения не может
быть рациональным.
3. Сравнения 55

4.65. Докажите, что квадрат целого числа не может оканчиваться
четырьмя одинаковыми цифрами, отличными от 0. Какими тремя циф-
рами может оканчиваться целое число, квадрат которого оканчивается
тремя одинаковыми цифрами, отличными от 0?
4.66. Докажите, что если две последние цифры целого числа нечет-
ны, то это число не может быть квадратом целого числа.
4.67. Найдите остатки от деления числа 22001 на 3, 5, 7, . . . , 17.
4.68. Шестизначное число делится на 7. Его первую цифру стерли, а
затем записали ее позади последней цифры. Докажите, что новое число
также делится на 7.
4.69. Найдите все p такие, что числа p, p + 10, p + 14 — простые.
4.70. Известно, что числа p и 8p2 + 1 — простые. Найдите p.
4.71. Известно, что числа p и p2 +2 — простые. Докажите, что число
p3 + 2 также является простым.
4.72. Найдите конечную арифметическую прогрессию с разностью 6
максимальной длины, состоящую из простых чисел.
77
4.73. Найдите последнюю цифру числа 77 .
n2 + 1
4.74. Может ли число быть целым при натуральных n?
3
4.75. Пусть a и b — целые числа. Докажите, что
а) если a2 + b2 . 3, то a2 + b2 . 9; б) если a2 + b2 . 21, то a2 + b2 . 441.
. . . .
. . . .
4.76. Целые числа a, b, c и d таковы, что a4 + b4 + c4 + d4 . 5. .
.
. 625.
.
Докажите, что abcd .
.
4.77. Целые числа a, b и c таковы, что a3 + b3 + c3 . 7. Докажите,
.
. 343.
.
что abc .
4.78. Найдите остаток от деления на 17 числа 21999 + 1.
4.79. Встретится ли каждое простое число в качестве сомножителя
некоторого числа Евклида en ? (См. также 3.25.)
4.80. Пусть в прямоугольном треугольнике длины сторон выража-
ются целыми числами. Докажите, что длина одного из катетов кратна 3,
и длина одной из трех сторон делится на 5.
4.81. Пусть m — произведение первых n простых чисел (n > 1).
Докажите, что ни одно из чисел
а) m + 1; б) m ? 1
не является полным квадратом.
4.82. При каких целых n число an = 5n2 + 10n + 8 делится на 3?
А при каких на 4?
56 4. Арифметика остатков

4.83. При каких целых n выражение n2 ? 6n ? 2 делится на
а) 8; б) 9; в) 11; г) 121?
4.84. При каких целых n выражение n2 ? n ? 4 делится на
а) 17; б) 289?
4.85. Найдите все такие целые числа x, что x ? 3 (mod 7), x2 ?
? 44 (mod 72 ), x3 ? 111 (mod 73 ).
4.86. Докажите, что 22225555 + 55552222 . 7.
.
.
4.87. Докажите справедливость следующих сравнений:
а) 1 + 2 + 3 + . . . + 12 ? 1 + 2 + 22 + . . . + 211 (mod 13);
б) 12 + 22 + 32 + . . . + 122 ? 1 + 4 + 42 + . . . + 411 (mod 13).
Будут ли справедливы аналогичные сравнения для б?льших показа-
о
телей?
4.88. Докажите, что число 1k + 2k + . . . + 12k делится на 13 для
k = 1, 2, . . . , 11.
4.89. Докажите, что если 6n + 11m делится на 31, то n + 7m также
делится на 31.
4.90. Известно, что ax4 + bx3 + cx2 + dx + e, где a, b, c, d, e — данные
целые числа, при всех целых x делится на 7. Докажите, что все числа
a, b, c, d, e делится на 7.
4.91. Докажите, что если многочлен с целыми коэффициентами
P(x) = an xn + . . . + a1 x + a0
принимает при x = 0 и x = 1 нечетные значения, то уравнение P(x) = 0
не имеет целых корней.
4.92. Докажите, что pp+2 + (p + 2)p ? 0 (mod 2p + 2), где p > 2 —
простое число.
4.93. Решите сравнения:
а) 8x ? 3 (mod 13); в) 7x ? 2 (mod 11);
б) 17x ? 1 (mod 37); г) 80x ? 17 (mod 169).
Чтобы решить сравнение ax ? b (mod m), попробуйте сначала ре-
шить в целых числах уравнение ax + my = b.
4.94. Найдите все пары чисел вида 1xy2 и x12y, таких, что оба числа
делятся на 7.
4.95. В каких случаях разрешимо сравнение ax ? b (mod m)? Опи-
шите все решения этого сравнения в целых числах.
4.96. Для каких чисел a решением сравнения ax ? 1 (mod p) будет
само число a?
3. Сравнения 57

4.97. Теорема Вильсона. Докажите, что для простого p
(p ? 1)! ? ?1 (mod p).
4.98. Обращение теоремы Вильсона. Докажите, что если
n>1и
(n ? 1)! ? ?1 (mod n),
то n — простое число.
4.98 . Геометррическое доказательство теоремы Вильсона.
Пусть p > 2 — простое число. Сколькими способами можно провести
через вершины правильного p-угольника замкнутую ориентированную,
p-звенную ломанную? (Ломанные, которые можно совместить поворо-
том, считаются одинаковыми.) Найдите формулу и выведите из неё
теорему Вильсона.
4.99. Теорема Лейбница. Докажите, что p — простое тогда и толь-
ко тогда, когда
(p ? 2)! ? 1 (mod p).
4.100. Теорема Клемента. Докажите, что числа p и p+2 являются
простыми числами-близнецами тогда и только тогда, когда
4((p ? 1)! + 1) + p ? 0 (mod p2 + p).
4.101. Известно, что числа a1 , . . . , an равны ±1 и
a1 a2 + a2 a3 + . . . + an?1 an + an a1 = 0.
.
.
Докажите, что n . 4.
Пусть F(x1 , . . . , xn ) — многочлен с целыми коэффициентами от пе-
ременных x1 , . . . , xn . Очевидно, что каждое решение уравнения
(4.1)
F(x1 , . . . , xn ) = 0
в целых числах является и решением сравнения
F(x1 , . . . , xn ) ? 0 (mod m) (m (4.2)
1).
Поэтому, если хотя бы при одном m сравнение (4.2) неразрешимо, то
уравнение (4.1) не имеет решений в целых числах.
4.102. Докажите, что следующие уравнения не имеют решений в
целых числах:
а) x2 + y2 = 2003; д) 15x2 ? 7y2 = 9;
б) 12x + 5 = y2 ; е) x2 ? 5y + 3 = 0;
в) ? x2 + 7y3 + 6 = 0; ж) x4 + . . . + x4 = 1999;
1 14
г) x2 + y2 + z2 = 1999; 3 3
з) 8x ? 13y = 17.
58 4. Арифметика остатков

4.103. Докажите, что сумма пяти последовательных целых чисел не
может быть полным квадратом.
4.104. Гармонические числа. Докажите, что числа
1 1 1
Hn = 1 + + + ... +
2 3 n
при n > 1 не будут целыми.
4.105. Решите в натуральных числах уравнение
1! + 2! + . . . + n! = m2 .
4.106. Решите в целых числах уравнение
2x ? 1 = 5y .
4.107. Докажите что если (m, n) = 1, то сравнение a ? b (mod mn)
равносильно одновременному выполнению сравнений a ? b (mod m)
и a ? b (mod n).

4. Теоремы Ферма и Эйлера
4.108. Найдите такое n, чтобы число 10n ? 1 делилось на
а) 7; б) 13; в) 91; г) 819.
4.109. Докажите, что
а) 111 . . . 1 . 13; б) 111 . . . 1 . 17.
. .
. .
12 16
Малая теорема Ферма. Пусть p — простое число и p a. Тогда
ap?1 ? 1 (mod p).
4.110. Докажите теорему Ферма, разлагая (1 + 1 + . . . + 1)p посред-
ством полиномиальной теоремы.
4.111. Пусть p — простое число, p = 2, 5. Докажите, что существует
число вида 111 . . . 11, кратное p.
Придумайте два решения этой задачи: одно, использующее теорему
Эйлера, и второе — принцип Дирихле.
4.112. Для каких n число n2001 ? n4 делится на 11?
4.113. Докажите, что для любого натурального числа найдется
кратное ему число, десятичная запись которого состоит только из 0 и 1.
4.114. Дано простое p и целое a, не делящееся на p. Пусть k —
наименьшее натуральное число, такое что ak ? 1 (mod p). Докажите,
что p ? 1 делится на k.
4. Теоремы Ферма и Эйлера 59

4.115. С помощью индукции докажите следующее утверждение, эк-
вивалентное малой теореме Ферма: если p — простое число, то для лю-
бого натурального a справедливо сравнение
ap ? a (mod p).
4.116. Известно, что
a12 + b12 + c12 + d12 + e12 + f12 . 13.
.
.
Докажите, что abcdef . 136 .
.
.
4.117. Геометрическое доказательство малой теоремы Фер-
ма. Пусть p > 2 — простое число. Сколько существует способов рас-
красить вершины правильного p-угольника в a цветов? (Раскраски,
которые можно совместить поворотом, считаются одинаковыми.) По-
лучите формулу и выведите из нее малую теорему Ферма.
4.118. Найдите остатки от деления на 103 чисел
а) 5102 ; б) 3104 .
4.119. Докажите, что число 30239 + 23930 — составное.
4.120. Будет ли простым число 2571092 + 1092?
4.121. Докажите, что если p — простое число, p = 2, 5, то длина
периода разложения 1/p в десятичную дробь делит p ? 1. Приведите
пример, когда длина периода совпадает с p ? 1.
4.122. Пусть p — простое число. Докажите, что любой простой де-
литель числа 2p ? 1 имеет вид 2kp + 1.
4.123. Пусть n — натуральное число, не кратное 17. Докажите, что
либо n8 + 1, либо n8 ? 1 делится на 17.
4.124. Докажите, что при любом простом p
.
.
1 . . . 1 2 . . . 2 3 . . . 3 . . . 9 . . . 9 ?123 . . . 9 . p.
p p p p

4.125. Пусть для простого числа p > 2 и целого a, не делящегося
на p, выполнено сравнение x2 ? a (mod p). Докажите, что
a(p?1)/2 ? 1 (mod p).
4.126. Докажите, что если x2 + 1 делится на нечетное простое p, то
p = 4k + 1.
4.127. При помощи задачи 4.126 докажите, что существует беско-
нечно много простых чисел вида p = 4k + 1. (См. также 3.7.)
60 4. Арифметика остатков

4.128. Докажите, что для простого числа p вида p = 4k + 1 числа
x = ±(2k)! являются решениями сравнения x2 + 1 ? 0 (mod p).
4.129. Пользуясь результатом задачи 3.127 найдите остатки, кото-
рые при простом p дают числа Фибоначчи Fp и Fp+1 при делении на
p.
4.130. Пусть p — простое число и p > 3. Докажите, что если разре-
шимо сравнение
x2 + x + 1 ? 0 (mod p),
то p ? 1 (mod 6). Выведите отсюда бесконечность множества простых
чисел вида 6n + 1. (См. также 3.7.)
4.131. Пусть p — простое число и p > 5. Докажите, что если разре-
шимо сравнение
x4 + x3 + x2 + x + 1 ? 0 (mod p),
то p ? 1 (mod 5). Выведите отсюда бесконечность множества простых
чисел вида 5n + 1.
Определение. Функция Эйлера ?(n) определяется как количество
чисел от 1 до n, взаимно простых с n.
4.132. Найдите
a) ?(17); б) ?(p); в) ?(p2 ); г) ?(p? ).
4.133. Чему равна сумма
?(1) + ?(p) + ?(p2 ) + . . . + ?(p? ),
где ? — некоторое натуральное число? (См. также 4.149.)
4.134. Основным свойством функции Эйлера ?(n) является ее
мультипликативность. Для взаимно простых a и b рассмотрим
таблицу
1, 2, 3, ..., b
b + 1, b + 2, b + 3, ..., 2b
... ... ... ..., ...
(a ? 1)b + 1, (a ? 1)b + 2, (a ? 1)b + 3, ..., ab.

В каких столбцах этой таблицы находятся числа взаимно простые с
числом b? Сколько в каждом из этих столбцов чисел взаимно простых
с a? Докажите мультипликативность функции Эйлера, ответив на эти
вопросы.
Определение. Приведенной системой вычетов по некоторому мо-
дулю m называется система чисел, взятых по одному из каждого класса,
4. Теоремы Ферма и Эйлера 61

?
взаимно простого с модулем. (Говорят, что класс a взаимно прост с
модулем m, если само число a взаимно просто с m.)
4.135. Сколько классов составляют приведенную систему вычетов
по модулю m?
4.136. Пусть числа x1 , x2 , . . . , xr образуют приведенную систему
вычетов по модулю m. Для каких a и b числа yj = axj + b (j = 1, . . . , r)
также образуют приведенную систему вычетов по модулю m?
4.137. Пусть (m, n) = 1, а числа x и y пробегают приведенные
системы вычетов по модулям m и n соответственно. Докажите, что
число A = xn+ym пробегает при этом приведенную систему вычетов по
модулю mn. Выведите отсюда мультипликативность функции Эйлера.
4.138. Пусть n = p?1 . . . p?s . Докажите равенство
1 s

?(n) = n(1 ? 1/p1 ) . . . (1 ? 1/ps )
а) пользуясь мультипликативностью функции Эйлера;
б) пользуясь формулой включений и исключений (см. 2.99).
4.139. Решите уравнения
а) ?(x) = 2; б) ?(x) = 8; в) ?(x) = 12; г) ?(x) = 14.
4.140. По какому модулю числа 1 и 5 составляют приведенную си-
стему вычетов?
4.141. Решите уравнения
а) ?(x) = x/2; б) ?(x) = x/3; в) ?(x) = x/4.
4.142. Для каких n возможны равенства:
a) ?(n) = n ? 1; б) ?(2n) = 2?(n); в) ?(nk ) = nk?1 ?(n)?
4.143. Решите уравнения
а) ?(5x ) = 100; б) ?(7x ) = 294; в) ?(3x · 5y ) = 600.
4.144. Известно, что (m, n) > 1. Что больше ?(m · n) или ?(m) ?
? ?(n)? (См. также 3.93.)
4.145. Решите уравнение a = 2?(a).
4.146. Докажите, что если n > 2, то число всех правильных несо-
кратимых дробей со знаменателем n — четно.
4.147. Найдите сумму всех правильных несократимых дробей со
знаменателем n.
4.148. Выпишем в ряд все правильные дроби со знаменателем n
и сделаем возможные сокращения. Например, для n = 12 получится
следующий ряд чисел:
0 1 111 5 1 7 2 3 5 11
, ,,,, ,, ,,,, .
1 12 6 4 3 12 2 12 3 4 6 12
62 4. Арифметика остатков

Сколько получится дробей со знаменателем d, если d — некоторый де-
литель числа n?
4.149. Тождество Гаусса. Докажите равенство

?(d) = n,
d|n

где знак означает, что суммирование идет по всем делителям числа n
d|n
(См. также 4.133.)
4.150. Вписанные ломаные. Окружность разделена n точками
на n равных частей. Сколько можно составить различных замкнутых
ломаных из n р а в н ы х звеньев с вершинами в этих точках?
4.151. Докажите равенства:
а) ?(m) ?(n) = ?((m, n)) ?([m, n]);
б) ?(mn) ?((m, n)) = ?(m) ?(n) (m, n).
Следующая теорема является обобщением малой теоремы Ферма.
Теорема Эйлера. Пусть m 1 и (a, m) = 1. Тогда имеет место
сравнение
a?(m) ? 1 (mod m).
(См. также 4.197.)
4.152. Существует ли степень тройки, заканчивающаяся на 0001?
4.153. Докажите теорему Эйлера с помощью малой теоремы Ферма
а) в случае, когда m = pn ;
б) в общем случае.
4.154. Докажите, что 751 ? 1 делится на 103.
4.155. Пусть p > 2 — простое число. Докажите, что
.
.
7p ? 5p ? 2 . 6p.
4.156. При помощи теоремы Эйлера найдите число x, удовлетворя-
ющее сравнению ax + b ? 0 (mod m), где (a, m) = 1.
4.157. Докажите, что при любом целом a:
a) a5 ? a . 30; в) a11 ? a . 66;
. .
. .
. .
. 510; г) a73 ? a . 2 · 3 · 5 · 7 · 13 · 19 · 37 · 73.
17
б) a ? a . .
4.158. Докажите, что для любого нечетного числа m существует
.
.
такое натуральное число n, что 2n ? 1 . m.
4.159. Докажите, что при любом нечетном n число 2n! ? 1 делится
на n.
5. Признаки делимости 63

4.160. Числа Кармайкла. Докажите, что для составного числа
561 справедлив аналог малой теоремы Ферма: если (a, 561) = 1, то
выполняется сравнение a560 ? 1 (mod 561).
Числа, обладающие этим свойством, называются числами Кармайк-
ла.
4.161. Найдите все такие целые числа a, для которых число a10 + 1
делится на 10.
?
4.162. Усиление теоремы Эйлера. m = p1 1 . . . p?s — разложение
s
натурального числа m на простые множители. Обозначим через ?(m)
наименьшее общее кратное чисел ?(p?1 ), . . . , ?(p?s ):
1 s

?(m) = [?(p?1 ), . . . , ?(p?s )].
1 s

Докажите, что для любого целого числа a такого, что (a, m) = 1, будет
выполняться сравнение
a?(m) ? 1 (mod m).

5. Признаки делимости
4.163. Признаки делимости на 3, 9 и 11. Число N записано в
десятичной системе счисления
N = an an?1 . . . a1 a0.
Докажите следующие признаки делимости:
а) N . 3 ?? an + an?1 + . . . + a1 + a0 . 3;
.
. .
.
. 9 ?? a + a . 9;
. .
б) N . n?1 + . . . + a1 + a0 .
n
. .
. 11 ?? ±an an?1 ± . . . ? a1 + a0 . 11.
в) N . .
4.164. Может ли число, записываемое при помощи 100 нулей, 100
единиц и 100 двоек, быть полным квадратом?
4.165. Признаки делимости на 2, 4, 8, 5 и 25. Сформулируйте
и докажите признаки делимости на числа 2, 4, 8, 5 и 25.
4.166. Найдите все числа вида xy9z, которые делились бы на 132.
4.167. Найдите все числа вида 13xy45z, которые делились бы на 792.
4.168. Цифровой корень числа. Рассмотрим число N, записан-
ное в десятичной системе счисления. Найдем сумму цифр этого числа,
потом сложим цифры, которыми записана сумма и т. д. Будем продол-
жать этот процесс, пока в конце концов не получим однозначное число,
которое называют цифровым корнем числа N. Докажите, что цифровой
корень сравним с N по модулю 9.
64 4. Арифметика остатков

4.169. Делится ли на 9 число 1234 . . . 500? (В записи этого числа
подряд выписаны числа от 1 до 500.)
4.170. Докажите, что число 192021 . . . 7980 делится на 1980.
4.171. Докажите, что число abcd делится на 99 тогда и только тогда,
когда число ab + cd делится на 99.
4.172. Последовательность {xn } устроена следующим образом: x1 =
= 32001 , а каждый следующий член равен сумме цифр предыдущего.
Найдите x5 .
4.173. Найдите наименьшее число, запись которого состоит лишь из
нулей и единиц, делящееся без остатка на 225.
4.174. Какие цифровые корни бывают у полных квадратов и полных
кубов?
4.175. Два числа a и b получаются друг из друга перестановкой
цифр. Чему равен цифровой корень числа a ? b?
4.176. Докажите, что если n > 6 — четное совершенное число, то его
цифровой корень равен 1.
4.177. На доске написано число 8n . У него вычисляется сумма цифр,
у полученного числа вновь вычисляется сумма цифр, и так далее, до
тех пор, пока не получится однозначное число. Что это за число, если
n = 2001?
4.178. Докажите ошибочность следующих записей:
а) 4237 · 27925 = 118275855; в) 19652 = 3761225;
v
г) 5 371293 = 23.
б) 42971064 : 8264 = 5201;
4.179. Коля Васин выписал пример на умножение, а затем заме-
нил все цифры буквами: одинаковые цифры одинаковыми буквами, а
разные — разными. Получилось равенство ab · cd = effe. Не ошибся ли
Коля?
4.180. Докажите, что в записи числа 230 есть по крайней мере две
одинаковые цифры, не вычисляя его.
4.181. Существует ли число, которое является степенью 2 такое, что
перестановкой его цифр можно получить другую степень 2?
4.182. Признак делимости на 19. Существует следующий способ
проверить делится ли данное число N на 19:
1) отбрасываем последнюю цифру у числа N;
2) прибавляем к полученному числу произведение отброшенной
цифры на 2;
3) с полученным числом проделываем операции 1) и 2) до тех пор,
пока не останется число, меньшее или равное 19.
5. Признаки делимости 65

4) если остается 19, то 19 | N, в противном случае 19 N.
Докажите справедливость этого признака делимости.
4.183. Аналогичные признаки делимости существуют и для всех
чисел вида 10n ± 1 и их делителей. Например, существует признак
делимости на 21, из которого получается и признак делимости на 7.
Как устроен признак делимости на 21?
4.184. При каких x и y число xxyy является квадратом натурального
числа?
4.185. Найдите все такие трехзначные числа, которые в 12 раз боль-
ше суммы своих цифр.
4.186. Докажите, что если числа N и 5N имеют одинаковую сумму
цифр, то N делится на 9.
4.187. Двое пишут а) 30-значное; б) 20-значное число, употребляя
только цифры 1, 2, 3, 4, 5. Первую цифру пишет первый, вторую —
второй, третью — первый и т. д. Может ли второй добиться того, чтобы
полученное число разделилось на 9, если первый стремится ему поме-
шать?
4.188. Рассматриваются всевозможные семизначные числа с цифра-
ми 1, 2, 3, 4, 5, 6, 7, записанными в произвольном порядке. Докажите,
что ни одно из них не делится ни на какое другое.
4.189. Признак делимости Паскаля. Пусть запись числа N в
десятичной системе счисления имеет вид N = an an?1 . . . a1 a0, ri — оста-
ток от деления числа 10i на m (i = 0, . . . , n). Докажите, что число N
делится на m тогда и только тогда, когда число M = an rn + an?1 + . . .
. . . + a1 r1 + a0 делится на m.
4.190. С помощью признака делимости Паскаля установите призна-
ки делимости на числа 3, 9, 6, 8, 12, 15, 11, 7, 27, 37.
Иногда в качестве ri удобнее брать не остаток, а «недостаток», то
есть такое наибольшее неположительное число, что 10i ? ri (mod m).
4.191. Опишите все системы счисления, в которых число делится
на 2 тогда и только тогда, когда сумма его цифр делится на 2. Решите
задачу, заменив модуль 2 произвольным натуральным числом m > 1.
4.192. Найдите наименьшее основание системы счисления, в кото-
рой одновременно имеют место следующие признаки делимости:
1) число делится на 5 тогда и только тогда, когда сумма его цифр
делится на 5;
2) число делится на 7 тогда и только тогда, когда число, составлен-
ное из двух его последних цифр, делится на 7.
66 4. Арифметика остатков

4.193. Докажите, что если необходимый и достаточный признак
делимости, выражающийся через свойства цифр числа, не зависит от
порядка цифр, то это признак делимости на 3 или на 9.
4.193 . Установите признаки делимости на а) 2, б) 3, в) 5, для чисел,
записанных в фибоначчевой системе счисления.


6. Китайская теорема об остатках
Китайская теорема об остатках. Пусть целые числа m1 , . . . , mn
попарно взаимно просты, то есть (mi , mj ) = 1 при i = j, m = m1 . . . mn ,
и a1 , . . . , an , A — произвольные целые числа. Тогда существует ровно
одно целое число x такое, что
?
? x ? a1 (mod m1 ),
?
.............. (4.3)
?
?
x ? an (mod mn )

и A x < A + m. (См. также 6.51.)
Одним из важнейших применений китайской теоремы об остатках
является система счисления в остатках. В ней целое число представ-
ляется набором его остатков (или вычетов) по взаимно простым моду-
лям. В такой системе счисления операции с числами сводятся к опера-
циям с их остатками.
4.194. При каких целых n число an = n2 + 3n + 1 делится на 55?
4.195. Найдите остатки от деления:
14
а) 1910 на 66; б) 1914 на 70; в) 179 на 48; г) 1414 на 100.
4.196. Натуральные числа m1 , . . . , mn попарно взаимно просты.
Докажите, что сравнение

a?b (mod m1 · m2 · . . . · mn )

равносильно системе
?
?a ? b (mod m1 ),
?
?
?a ? b (mod m2 ),
?.....
? ........
?
?
a?b (mod mn ).
6. Китайская теорема об остатках 67

4.197. Натуральные числа m1 , . . . , mn попарно взаимно просты. До-
кажите, что число x = (m2 m3 . . . mn )?(m1 ) является решением системы
?
? x ? 1 (mod m1 ),
?
?
? x ? 0 (mod m ),
2

?.............
?
?
?
x ? 0 (mod mn ).
4.198. Пользуясь результатом предыдущей задачи, укажите в явном
виде число x, которое удовлетворяет системе (4.3).
4.199. Докажите китайскую теорему об остатках.
4.200. Укажите все целые числа x, удовлетворяющие системам:
x ? 3 (mod 5), x ? 2 (mod 13),
а) б)
x ? 7 (mod 17); x ? 4 (mod 19).
4.201. Найдите наименьшее натуральное число, дающее при деле-
нии на 2, 3, 5, 7 остатки 1, 2, 4, 6 соответственно.
4.202. На столе лежат книги, которые надо упаковать. Если их
связать в одинаковые пачки по 4, по 5 или по 6 книг, то каждый раз
останется одна лишняя книга, а если связать по 7 книг в пачку, то
лишних книг не останется. Какое наименьшее количество книг может
быть на столе?
4.203. Найдите остаток от деления числа 1000! на 10250 .
4.204. Найдите наименьшее четное натуральное число a такое, что
a + 1 делится на 3, a + 2 — на 5, a + 3 — на 7, a + 4 — на 11, a + 5 —
на 13.
4.205. Пусть натуральные числа m1 , m2 , . . . , mn попарно взаимно
просты. Докажите, что если числа x1 , x2 , . . . , xn пробегают полные
системы вычетов по модулям m1 , m2 , . . . , mn соответственно, то число
x = x1 m2 . . . mn + m1 x2 m3 . . . mn + . . . + m1 m2 . . . mn?1 xn
пробегает полную систему вычетов по модулю m1 m2 . . . mn . Выведите
отсюда китайскую теорему об остатках.
4.206. Китайская теорема об остатках и функция Эйлера.
Докажите, что число x является элементом приведенной системы вы-
четов тогда и только тогда, когда числа a1 , . . . , an , определенные срав-
нениями (4.3) принадлежат приведенным системам вычетов по модулям
m1 , . . . , mn соответственно. Выведите отсюда мультипликативность
функции Эйлера.
68 4. Арифметика остатков

4.207. Предположим, что числа m1 , . . . , mn попарно взаимно про-
c
сты. Докажите, что любую правильную дробь вида можно
m1 . . . mn
представить в виде алгебраической суммы правильных дробей вида
ni /mi (y = 1, . . . , n).
4.208. Какие цифры надо поставить вместо звездочек, чтобы число
454 ? ? делилось на 2, 7 и 9?
4.209. Найдите наименьшее натуральное число, половина которо-
го — квадрат, треть — куб, а пятая часть — пятая степень.
4.210. Числа-автоморфы. а) Трехзначное число 625 обладает
своеобразным свойством самовоспроизводимости, как то:

6252 = 390 625.

Сколько четырехзначных чисел удовлетворяют уравнению

x2 ? x (mod 10000)?

б) Докажите, что при любом k существует ровно 4 набора из k
цифр — 00 . . . 00, 00 . . . 01 и еще два, оканчивающиеся пятеркой и ше-
стеркой, — обладающие таким свойством: если натуральное число окан-
чивается одним из этих наборов цифр, то его квадрат оканчивается тем
же набором цифр.
4.211. Больное войско. Генерал хочет построить для парада своих
солдат в одинаковые квадратные каре, но он не знает сколько солдат (от
1 до 37) находится в лазарете. Докажите, что у генерала может быть
такое количество солдат, что он, независимо от заполнения лазарета,
сумеет выполнить свое намерение.
Например, войско из 9 человек можно поставить в виде квадрата
3 ? 3, а если один человек болен, то в виде двух квадратов 2 ? 2.
4.212. Восточный Календарь. В китайской натурфилософии вы-
деляются пять первоэлементов природы — дерево, огонь, металл, вода
и земля, которым соответствуют пять цветов — синий (или зеленый),
красный, белый, черный и желтый. В восточном календаре с древних
времен используется 12-летний животный цикл так, что каждому из 12
годов в цикле соответствует одно из животных. Кроме того, каждый
год проходит под покровительством одной из стихий и окрашивается в
один из цветов:
годы, оканчивающиеся на 0 и 1 — годы металла (цвет белый);
годы, оканчивающиеся на 2 и 3 — это годы воды (цвет черный);
годы, оканчивающиеся на 4 и 5 — годы дерева (цвет синий);
6. Китайская теорема об остатках 69

годы, оканчивающиеся на 6 и 7 — годы огня (цвет красный);
годы, оканчивающиеся на 8 и 9 — годы земли (цвет желтый).
В 60-летнем календарном цикле каждое животное возникает 5 раз.
С помощью китайской теоремы об остатках объясните, почему оно все
5 раз бывает разного цвета.
Глава 5
Числа, дроби, системы счисления

1. Рациональные и иррациональные числа
Определение. Число ? называется рациональным, если оно пред-
ставимо в виде ? = m/n, где m — некоторое целое, а n — натуральное
числа. Все остальные действительные числа называются иррациональ-
ными. Множество всех рациональных чисел обозначается через Q. Два
числа называются несоизмеримыми, если их отношение иррационально.
Определение. Десятичная дробь
? = 0,a1 a2 . . . ak b1 b2 . . . bn b1 b2 . . . bn b1 b2 . . . bn . . . ,
где b1 b2 . . . bn — наименьший по длине отрезок цифр, повторяющий-
ся начиная с некоторого места, называется периодической десятичной
дробью. При том набор цифр b1 b2 . . . bn называется периодом, набор
a1 a2 . . . ak — предпериодом, n — длиной периода и дробь записывается в
виде
? = 0,a1 a2 . . . ak (b1 b2 . . . bn ).
5.1. Представьте следующие рациональные числа в виде десятичных
дробей:
1 2 1 1
а) ; б) ; в) ; г) .
7 7 14 17
5.2. Найдите цифры a и b такие, для которых
v
0,aaaaa . . . = 0,bbbbb . . .
5.3. Найдите период дроби
1
= 0,0204081632 . . .
49
Как можно объяснить тот факт, что после запятой появляются степени
числа 2?
5.4. Число Фейнмана. Объясните поведение следующей десятич-
ной дроби и найдите ее период:
1
= 0,004115226337448 . . .
243
1. Рациональные и иррациональные числа 71

<<

стр. 2
(всего 9)

СОДЕРЖАНИЕ

>>