Книги по разным темам Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 30 |

4.55. Пусть числа x1, x2,..., xm образуют полную систему вычетов по модулю m. Для каких a и b числа yj = axj + b (j = 1,..., m) также образуют полную систему вычетов по модулю m 4.56. Из свойств сравнений следует, что с классами вычетов можно делать все операции, которые допустимы для целых чисел: складывать, вычитать, умножать, возводить в степень. Отличие будет лишь в том, что построенная арифметика действует на конечном множестве классов 54 4. Арифметика остатков вычетов. Например, для m = 6 получаются такие таблицы сложения и умножения:

+ 0 1 2 3 4 5 0 1 2 3 4 0 0 1 2 3 4 5 0 0 0 0 0 0 1 1 2 3 4 5 0 1 0 1 2 3 4 2 2 3 4 5 0 1 2 0 2 4 0 2 3 3 4 5 0 1 2 3 0 3 0 3 0 4 4 5 0 1 2 3 4 0 4 2 0 4 5 5 0 1 2 3 4 5 0 5 4 3 2 Постройте аналогичные таблицы сложения и умножения для модулей 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.81.) 4.60. Разочарованный вкладчик фонда Нефтьалмазинвест разорвал акцию на 8 кусков. Не удовлетворившись этим, он разорвал один из кусков еще на 8, и т. д. Могло ли у него получиться 2002 куска 4.61. Иван-царевич имеет два волшебных меча, один из которых может отрубить Змею Горынычу 21 голову, а второй Ч 4 головы, но тогда у Змея Горыныча вырастает 1999 голов. Может ли Иван отрубить Змею Горынычу все головы, если в самом начале у него было голов (Примечание: если, например, у Змея Горыныча осталось лишь 3 головы, то рубить их ни тем, ни другим мечом нельзя.) 4.62. В магазине было 6 ящиков яблок, массы которых соответственно 15, 16, 18, 19, 20 и 31 килограммов. Две фирмы приобрели 5 ящиков, причем одна из них взяла по массе яблок в два раза больше, чем другая.

Какой ящик остался в магазине 4.63. Составьте список всевозможных остатков, которые дают числа n2 при делении на 3, 4, 5,..., 9.

4.64. Докажите, что если все коэффициенты уравнения ax2 + bx + c = Ч целые нечетные числа, то ни один из корней этого уравнения не может быть рациональным.

3. Сравнения 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. Найдите конечную арифметическую прогрессию с разностью максимальной длины, состоящую из простых чисел.

4.73. Найдите последнюю цифру числа 77.

n2 + 4.74. Может ли число быть целым при натуральных n 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.

.

.

.

Докажите, что abcd. 625.

.

4.77. Целые числа a, b и c таковы, что a3 + b3 + c3. 7. Докажите,.

.

.

что abc. 343.

4.78. Найдите остаток от деления на 17 числа 21999 + 1.

4.79. Встретится ли каждое простое число в качестве сомножителя некоторого числа Евклида en (См. также 3.25.) 4.80. Пусть в прямоугольном треугольнике длины сторон выражаются целыми числами. Докажите, что длина одного из катетов кратна 3, и длина одной из трех сторон делится на 5.

4.81. Пусть m Ч произведение первых n простых чисел (n > 1).

Докажите, что ни одно из чисел а) m + 1; б) m - не является полным квадратом.

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), x 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) = anxn +... + a1x + aпринимает при x = 0 и x = 1 нечетные значения, то уравнение P(x) = не имеет целых корней.

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. Сравнения 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 и a1a2 + a2a3 +... + an-1an + ana1 = 0.

.

.

Докажите, что n. 4.

Пусть F(x1,..., xn) Ч многочлен с целыми коэффициентами от переменных x1,..., xn. Очевидно, что каждое решение уравнения F(x1,..., xn) = 0 (4.1) в целых числах является и решением сравнения F(x1,..., xn) 0 (mod m) (m 1). (4.2) Поэтому, если хотя бы при одном 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 г) x2 + y2 + z2 = 1999; з) 8x3 - 13y3 = 17.

58 4. Арифметика остатков 4.103. Докажите, что сумма пяти последовательных целых чисел не может быть полным квадратом.

4.104. Гармонические числа. Докажите, что числа 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 Малая теорема Ферма. Пусть 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. Теоремы Ферма и Эйлера 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. Теоремы Ферма и Эйлера взаимно простого с модулем. (Говорят, что класс взаимно прост с модулем 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. Выведите отсюда мультипликативность функции Эйлера.

s 4.138. Пусть n = p... p. Докажите равенство 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 1 1 1 5 1 7 2 3 5,,,,,,,,,,,.

1 12 6 4 3 12 2 12 3 4 6 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).

Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 30 |    Книги по разным темам