alfutova(алгебра и теория чисел). Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике

• Название: Сборник задач для математических школ м мцнмо, 2002. 264 с Настоящее пособие представляет собой сборник задач по математике
• Дата: 27.01.2020
• Размер: 2 Mb.
• Имя файла: alfutova(алгебра и теория чисел).pdf
• Тип: Сборник задач; #106051
• страница: 5 из 23

длины сторон которых выражены целыми числами, если один из катетов этих треугольников равен 15?
4.33. Решите уравнения:
а) 3x
2
+ 5y
2
= б) 1 + x + x
2
+ x
3
= 2
y
4.34. Докажите, что число 1 1999
+ 2 1999
+ . . . + 16 делится на 17.
4.35. Назовем шестизначное число счастливым, если сумма его первых трех цифр равна сумме последних трех цифр. Докажите, что сумма всех счастливых чисел делится на 13.

52 4. Арифметика остатков. Докажите, что числа от 1 до 2001 включительно нельзя выписать подряд в некотором порядке так, чтобы полученное число было точным кубом. Докажите, что 7 7
77 7
− 7 7
77
... 10 4.38. Число x таково, что заканчивается на 001 (в десятичной системе счисления. Найдите три последние цифры числа x (укажите всевозможные варианты. Имеется много одинаковых квадратов. В вершинах каждого из них в произвольном порядке написаны числа 1, 2, 3 и 4. Квадраты сложили в стопку и написали сумму чисел, попавших в каждый из четырех углов стопки. Может ли оказаться так, что а) в каждом углу стопки сумма равна б) в каждом углу стопки сумма равна 2005?
4.40. Дан многочлен с целыми коэффициентами. Если в него вместо неизвестной подставить 2 или 3, то получаются числа, делящиеся на Докажите, что если вместо неизвестной в него подставить 5, то также получится число, делящееся на 6.
4.41. Докажите, что в трехзначном числе, делящемся навсегда можно переставить цифры так, что новое число также будет делится на 37.
4.42. Докажите, что если p — простое число и 1 6 k 6 p − 1, то p
... p
4.43. Докажите утверждение обратное тому, что было в задаче
4.42
:
если C
k n
... n при 1 6 k 6 n − 1, то n — простое число. Докажите, что если p — простое число и 1 6 k 6 p − 2, то p−k+1
− C
k−2
p−k−1
... p
. Верно ли обратное утверждение. Докажите, что если p — простое число, то при любых целых a и b выполняется соотношение + b)
p
− a p
− b p
... p.
4.46
*
. Камни лежат в трех кучках водной камень, в другой камней, а в третьей — 5 камней. Разрешается объединять любые кучки в одну, а также разделять кучку из четного количества камней на две равные. Можно ли получить 105 кучек по одному камню в каждой?
В следующих задачах понадобится вспомнить принцип Дирихле из раздела 4.47. Докажите, что среди любых n натуральных чисел, неделя- щихся наесть несколько чисел, сумма которых делится на n.

3. Сравнения 4.48. Докажите, что среди любых десяти последовательных натуральных чисел найдется число, взаимно простое с остальными. На 99 карточках пишутся числа 1, 2, . . . , 99. Затем карточки тасуются и раскладываются чистыми сторонами вверх. На чистых сторонах карточек снова пишутся числа 1, 2, . . . , 99. Для каждой карточки числа, стоящие на ней, складываются и 99 полученных сумм перемножаются. Докажите, что в результате получится четное число. Сравнения
Определение. Пусть m > 1. Два числа a и b называются сравнимыми по модулю m, если их разность делится на m. Записывается это в виде a ≡ b (mod m).
4.50. Что означают записи:

а) a ≡ b (mod б) a ≡ b (mod 1)?
4.51. Свойства сравнений. Докажите, что если a ≡ b (mod m) и c
≡ d (mod m), то а) a + c ≡ b + d (mod б) ac ≡ bd (mod Определение. Классом вычетов поданному модулю m называется множество всех целых чисел сравнимых с некоторым данным целым числом a по модулю m. Такой класс обозначается ¯
a
4.52. Докажите, что класс ¯
a состоит из всех чисел вида mt + a, где t
— произвольное целое число. Докажите, что два класса ¯
a и ¯
b совпадают тогда и только тогда, когда a ≡ b (mod Определение. Полной системой вычетов по некоторому модулю называется система чисел, взятых по одному из каждого класса поэтому модулю. Докажите, что любые m чисел x
1
, . . . , x попарно несравнимых по модулю m, представляют собой полную систему вычетов по модулю m.
4.55. Пусть числа x
1
, x
2
, . . . , x образуют полную систему вычетов по модулю m. Для каких a и b числа y j
= ax j
+ b

(j = 1, . . . , m) также образуют полную систему вычетов по модулю m?
4.56. Из свойств сравнений следует, что с классами вычетов можно делать все операции, которые допустимы для целых чисел складывать,
вычитать, умножать, возводить в степень. Отличие будет лишь в том,
что построенная арифметика действует наконечном множестве классов

54 4. Арифметика остатков вычетов. Например, для m = 6 получаются такие таблицы сложения и умножения 1
2 3
4 5
0 0
1 2
3 4
5 1
1 2
3 4
5 0
2 2
3 4
5 0
1 3
3 4
5 0
1 2
4 4
5 0
1 2
3 5
5 0
1 2
3 4
×
0 1
2 3
4 5
0 0
0 0
0 0
0 1
0 1
2 3
4 5
2 0
2 4
0 2
4 3
0 3
0 3
0 3
4 0
4 2
0 4
2 5
0 5
4 3
2 Постройте аналогичные таблицы сложения и умножения для модулей m = 7
, 8, . . . , 13.

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

3. Сравнения 4.65. Докажите, что квадрат целого числа не может оканчиваться четырьмя одинаковыми цифрами, отличными от 0. Какими тремя цифрами может оканчиваться целое число, квадрат которого оканчивается тремя одинаковыми цифрами, отличными от 0?
4.66. Докажите, что если две последние цифры целого числа нечет- ны, то это число не может быть квадратом целого числа. Найдите остатки отделения числа 2 на 3, 5, 7, . . . , 17.
4.68. Шестизначное число делится на 7. Его первую цифру стерли, а затем записали ее позади последней цифры. Докажите, что новое число также делится на 7.
4.69. Найдите все p такие, что числа p, p + 10, p + 14 — простые. Известно, что числа p и 8p
2
+ 1
— простые. Найдите p.
4.71. Известно, что числа p и p
2
+ 2
— простые. Докажите, что число p
3
+ также является простым. Найдите конечную арифметическую прогрессию с разностью максимальной длины, состоящую из простых чисел. Найдите последнюю цифру числа 7 7
77 4.74. Может ли число n
2

+ 1 быть целым при натуральных n?
4.75. Пусть a и b — целые числа. Докажите, что а) если a
2
+ b
2
... 3
, то a
2
+ b
2
... б) если a
2
+ b
2
... 21
, то a
2
+ b
2
... 441 4.76. Целые числа a, b, c и d таковы, что a
4
+ b
4
+ c
4
+ d
4
... Докажите, что abcd ... 625.
4.77. Целые числа a, b и c таковы, что a
3
+ b
3
+ c
3
... 7
. Докажите,
что abc ... 343.
4.78. Найдите остаток отделения на 17 числа 2 1999
+ 1 4.79. Встретится ли каждое простое число в качестве сомножителя некоторого числа Евклида e n
? (См. также. Пусть в прямоугольном треугольнике длины сторон выражаются целыми числами. Докажите, что длина одного из катетов кратна и длина одной из трех сторон делится на 5.
4.81. Пусть m — произведение первых n простых чисел (n > Докажите, что ни одно из чисел а) m + б) m − не является полным квадратом. При каких целых n число a n
= 5n
2

+ 10n + делится на А при каких на 4?

56 4. Арифметика остатков. При каких целых n выражение n
2

− 6n − делится на а) б) в) г) 121?
4.84. При каких целых n выражение n
2

− n − делится на а) б) 289?
4.85. Найдите все такие целые числа x, что x ≡ 3 (mod 7), x
2
≡
≡ 44 (mod 7 2
)
, x
3
≡ 111 (mod 7 3
)
4.86. Докажите, что 2222 5555
+ 5555 2222
... 7 4.87. Докажите справедливость следующих сравнений:
а) 1 + 2 + 3 + . . . + 12 ≡ 1 + 2 + 2 2
+ . . . + 2 11
(
mod б) 1 2
+ 2 2
+ 3 2
+ . . . + 12 2
≡ 1 + 4 + 4 2
+ . . . + 4 11
(
mod Будут ли справедливы аналогичные сравнения для больших показателей. Докажите, что число 1
k
+ 2
k
+ . . . + 12
k делится на 13 для k = 1, 2, . . . , 11 4.89. Докажите, что если 6n + 11m делится на 31, то n + 7m также делится на 31.
4.90. Известно, что ax
4
+ bx
3
+ cx
2
+ dx + e
, где a, b, c, d, e — данные целые числа, при всех целых x делится на 7. Докажите, что все числа a
, b, c, d, e делится на 7.
4.91. Докажите, что если многочлен с целыми коэффициентами) = a n
x n
+ . . . + a
1
x + принимает при x = 0 и x = 1 нечетные значения, то уравнение P(x) = не имеет целых корней. Докажите, что p p+2
+ (p + 2)
p
≡ 0 (mod 2p + 2), где p > 2 простое число. Решите сравнения:
а) 8x ≡ 3 (mod в) 7x ≡ 2 (mod б) 17x ≡ 1 (mod г) 80x ≡ 17 (mod Чтобы решить сравнение ax ≡ b (mod m), попробуйте сначала решить в целых числах уравнение ax + my = b.
4.94. Найдите все пары чисел вида 1xy2 и x12y, таких, что оба числа делятся на 7.
4.95. В каких случаях разрешимо сравнение ax ≡ b (mod m)? Опишите все решения этого сравнения в целых числах. Для каких чисел a решением сравнения ax ≡ 1 (mod p) будет само число a?

3. Сравнения 4.97. Теорема Вильсона. Докажите, что для простого p
(p − 1)!
≡ −1
(
mod p).
4.98. Обращение теоремы Вильсона. Докажите, что если n > и − 1)!
≡ −1
(
mod то n — простое число 0
. Геометррическое доказательство теоремы Вильсона.
Пусть p > 2 — простое число. Сколькими способами можно провести через вершины правильного угольника замкнутую ориентированную,
p
-звенную ломанную (Ломанные, которые можно совместить поворотом, считаются одинаковыми) Найдите формулу и выведите из неё
теорему Вильсона. Теорема Лейбница. Докажите, что p — простое тогда и только тогда, когда − 2)!
≡ 1
(
mod p).
4.100. Теорема Клемента. Докажите, что числа p и p+2 являются простыми числами-близнецами тогда и только тогда, когда − 1)! + 1) + p
≡ 0
(
mod p
2
+ p).
4.101. Известно, что числа a
1
, . . . , a равны ±1 и a
1
a
2
+ a
2
a
3
+ . . . + a n−1
a n
+ a n
a
1
= Докажите, что n ... Пусть F(x
1
, . . . , x n
)
— многочлен с целыми коэффициентами от переменных. Очевидно, что каждое решение уравнения, . . . , x n
) = в целых числах является и решением сравнения, . . . , x n
)
≡ 0
(
mod m)
(m > Поэтому, если хотя бы при одном m сравнение (
4.2
) неразрешимо, то уравнение (
4.1
) не имеет решений в целых числах. Докажите, что следующие уравнения не имеют решений в целых числах:
а) x
2
+ y
2
= д) 15x
2
− 7y
2
= б) 12x + 5 = е) x
2
− 5y + 3 = в) − x
2
+ 7y
3
+ 6 = ж) x
4 1
+ . . . + x
4 14
= г) x
2
+ y
2
+ z
2
= з) 8x
3
− 13y
3
= 17

58 4. Арифметика остатков. Докажите, что сумма пяти последовательных целых чисел не может быть полным квадратом. Гармонические числа. Докажите, что числа 1 +
1 2
+
1 3
+ . . . +
1
n при n > 1 не будут целыми. Решите в натуральных числах уравнение + 2! + . . . + n! = m
2 4.106. Решите в целых числах уравнение 1 = 5
y
4.107. Докажите что если (m, n) = 1, то сравнение a ≡ b (mod равносильно одновременному выполнению сравнений a ≡ b (mod и a ≡ b (mod n).
4. Теоремы Ферма и Эйлера. Найдите такое n, чтобы число 10
n
− делилось на а) б) в) г) 819.
4.109. Докажите, что а) 111 . . . 1
| {z }
12
... б) 111 . . . 1
| {z }
16
... Малая теорема Ферма. Пусть p — простое число и p - a. Тогда a
p−1
≡ 1
(
mod p).
4.110. Докажите теорему Ферма, разлагая (1 + 1 + . . . + 1)
p посредством полиномиальной теоремы. Пусть p — простое число, p 6= 2, 5. Докажите, что существует число вида 111 . . . 11, кратное Придумайте два решения этой задачи одно, использующее теорему
Эйлера, и второе — принцип Дирихле. Для каких n число n
2001

− делится на 11?
4.113. Докажите, что для любого натурального числа найдется кратное ему число, десятичная запись которого состоит только из 0 и 1.
4.114. Дано простое p и целое a, не делящееся на p. Пусть k наименьшее натуральное число, такое что a k
≡ 1 (mod p). Докажите,
что p − 1 делится на k.

4. Теоремы Ферма и Эйлера 4.115. С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма если p — простое число, то для любого натурального a справедливо сравнение a
p
≡ a
(
mod p).
4.116. Известно, что a
12
+ b
12
+ c
12
+ d
12
+ e
12
+ f
12
... Докажите, что abcdef ... 13 6
4.117. Геометрическое доказательство малой теоремы Ферма. Пусть p > 2 — простое число. Сколько существует способов раскрасить вершины правильного угольника в a цветов (Раскраски,
которые можно совместить поворотом, считаются одинаковыми) Получите формулу и выведите из нее малую теорему Ферма. Найдите остатки отделения на 103 чисел а) 5 б) 3 104 4.119. Докажите, что число 30 239
+ 239 30
— составное. Будет ли простым число 257 1092
+ 1092
?
4.121. Докажите, что если p — простое число, p 6= 2, 5, то длина периода разложения 1/p в десятичную дробь делит p − 1. Приведите пример, когда длина периода совпадает с p − 1.
4.122. Пусть p — простое число. Докажите, что любой простой делитель числа 2
p
− имеет вид 2kp + 1.
4.123. Пусть n — натуральное число, не кратное 17. Докажите, что либо n
8
+ 1
, либо n
8
− делится на 17.
4.124. Докажите, что при любом простом p
1 . . . 1
| {z }
p
2 . . . 2
| {z }
p
3 . . . 3
| {z }
p
. . . 9 . . . 9
| {z }
p
−123 . . . 9 ... p.
4.125. Пусть для простого числа p > 2 и целого a, не делящегося на p, выполнено сравнение x
2
≡ a (mod p). Докажите, что a
(p−1)/2
≡ 1
(
mod p).
4.126. Докажите, что если x
2
+ делится на нечетное простое p, то p = 4k + 1 4.127. При помощи задачи
4.126
докажите, что существует бесконечно много простых чисел вида p = 4k + 1. (См. также

60 4. Арифметика остатков. Докажите, что для простого числа p вида p = 4k + 1 числа x =
±(2k)! являются решениями сравнения x
2
+ 1
≡ 0 (mod p).
4.129. Пользуясь результатом задачи
3.127
найдите остатки, которые при простом p дают числа Фибоначчи F
p и при делении на p
4.130. Пусть p — простое число и p > 3. Докажите, что если разрешимо сравнение x
2
+ x + 1
≡ 0
(
mod то p ≡ 1 (mod 6). Выведите отсюда бесконечность множества простых чисел вида 6n + 1. (См. также. Пусть p — простое число и p > 5. Докажите, что если разрешимо сравнение x
4
+ x
3
+ x
2
+ x + 1
≡ 0
(
mod то p ≡ 1 (mod 5). Выведите отсюда бесконечность множества простых чисел вида 5n + Определение. Функция Эйлера ϕ(n) определяется как количество чисел от 1 до n, взаимно простых с n.
4.132. Найдите a) б) в) г) ϕ(p
α
)
4.133. Чему равна сумма) + ϕ(p) + ϕ(p
2
) + . . . + где α — некоторое натуральное число (См. также. Основным свойством функции Эйлера ϕ(n) является ее мультипликативность. Для взаимно простых a и b рассмотрим таблицу. . . ,
b b + 1,
b + 2,
b + 3,
. . . ,
2b
. . . ,
(a − 1)b + 1,
(a − 1)b + 2,
(a − 1)b + 3,
. . . В каких столбцах этой таблицы находятся числа взаимно простые с числом b? Сколько в каждом из этих столбцов чисел взаимно простых с a? Докажите мультипликативность функции Эйлера, ответив на эти вопросы.
Определение. Приведенной системой вычетов по некоторому модулю называется система чисел, взятых по одному из каждого класса

4. Теоремы Ферма и Эйлера
61
взаимно простого с модулем. (Говорят, что класс ¯
a взаимно прост с модулем m, если само число a взаимно просто с m.)

4.135. Сколько классов составляют приведенную систему вычетов по модулю m?
4.136. Пусть числа x
1
, x
2
, . . . , x образуют приведенную систему вычетов по модулю m. Для каких a и b числа y j
= ax j
+ b

(j = 1, . . . , также образуют приведенную систему вычетов по модулю m?
4.137. Пусть (m, n) = 1, а числа x и y пробегают приведенные системы вычетов по модулями соответственно. Докажите, что число A = xn+ym пробегает при этом приведенную систему вычетов по модулю mn. Выведите отсюда мультипликативность функции Эйлера. Пусть n = p
α
1 1
. . . p
α
s s
. Докажите равенство) = n(1 − 1/p
1
) . . . (1 − 1/p а) пользуясь мультипликативностью функции Эйлера;
б) пользуясь формулой включений и исключений (см. Решите уравнения а) ϕ(x) = б) ϕ(x) = в) ϕ(x) = г) ϕ(x) = 14.
4.140. По какому модулю числа 1 и 5 составляют приведенную систему вычетов. Решите уравнения а) ϕ(x) = б) ϕ(x) = в) ϕ(x) = x/4.
4.142. Для каких n возможны равенства) ϕ(n) = n − б) ϕ(2n) = в) ϕ(n k
) = n k−1
ϕ(n)
?
4.143. Решите уравнения а) ϕ(5
x
) = б) ϕ(7
x
) = в) ϕ(3
x
· 5
y
) = 600 4.144. Известно, что (m, n) > 1. Что больше ϕ(m · n) или ϕ(m) ×
× ϕ(n)? (См. также. Решите уравнение a = 2τ(a).
4.146. Докажите, что если n > 2, то число всех правильных несократимых дробей со знаменателем n — четно. Найдите сумму всех правильных несократимых дробей со знаменателем n.
4.148. Выпишем вряд все правильные дроби со знаменателем n и сделаем возможные сокращения. Например, для n = 12 получится следующий ряд чисел 1
,
1 12
,
1 6
,
1 4
,
1 3
,
5 12
,
1 2
,
7 12
,
2 3
,
3 4
,
5 6
,
11 12

62 4. Арифметика остатков