где р и q — простые числа.
Система задач 3.4.
1. 8 128 и 33550 336.
Система задач 4.1.
1. а) D(360, 1970) = 10; б) D(30, 365) = 5.
2. Предположим, что √2 — рациональное число, т. е. √2 = a/b. Можем считать, что все сокращения произведены и числа а и b не имеют общих множителей. Возводя в квадрат это соотношение, получаем 2b2 = a.
По теореме о единственности разложения число а делится на 2, следовательно, а2 делится на 4. И вновь по теореме о единственности разложения, примененней к числу b2, получаем, что b делится на 2, что противоречит предположению о том, что числа а и b не имеют общих множителей. Полученное противоречие показывает, что √2 — число иррациональное.
Система задач 4.2.
1. Нечетные числа.
2. Если простое число р является делителем чисел n и n + 1, то оно будет делителем числа (n + 1) — n = 1.
3. Никакие из них не являются взаимно простыми.
4. Да.
Система задач 4.3.
2. D(220, 284) = 4, D(1184, 1210)=2, D(2620, 2924)= 4, D(5020, 5564) = 4.
3. Чтобы определить наибольшую степень числа 10, на которую делится число n = 12•3… n, мы должны сначала найти наибольшую степень числа 5, на которую оно делится. Каждое пятое число 5, 10, 15, 20, 25, 30 делится на 5, всего таких чисел, не превосходящих числа n, [n/5]. Однако некоторые из них делятся на вторую степень числа 5, а именно, 25, 50, 75, 100…; таких чисел существует [n/25]. Некоторые из них делятся на третью степень числа 5, т. е. на 125: 125, 250, 375; их существует [n/53] и т. д. Это показывает, что выражение для точной степени числа 5, делящей число n! таково:
[n/5] + [n/52] + [n/53] +… (*)
В этой сумме достаточно выписать лишь те члены, в которых у выражения в квадратных скобках числитель не меньше знаменателя.
Точно такие же рассуждения можно провести для нахождения соответствующей степени любого другого простого числа р. В частности, когда р = 2, получается выражение
[n/2] + [n/22] + [n/23] +…
Ясно, что это выражение не меньше, чем выражение (*), т. е. в числе n! каждому множителю 5 можно подобрать множитель 2. Таким образом, выражение (*) также дает и величину степени числа 10, делящей n! которая равна числу нулей, стоящих в конечной части записи числа.
Примеры. n = 10, [10/5] = 2, [10/52] = 0, поэтому 10! оканчивается двумя нулями;
n = 31, [31/5] = 6, [31/52] = 1, [31/53] = 0, поэтому 31! оканчивается 7 нулями.
Система задач 4.4.
1. К(360, 1970) = 70 920, К(30, 365) = 2190.
2. К(220, 284)= 15620, K(1184, 1210) = 716 320, К(2620, 2924) =1 915 220, К(5020, 5564) = 6 982 820.
Система задач 5.2.
1. m = 8, n = 1: (16, 63, 65), n = 3: (24, 55, 73), n = 5: (80, 39, 89), n = 7: (112, 15, 113),
m = 9, n = 2: (36, 77, 85), n = 4: (64, 65, 97), n = 8: (144, 17, 145),
m =10, n = 1: (20, 99, 101), n = 3: (60, 91, 109), n = 7: (140, 51, 149), n = 9: (180, 19, 181).
2. Нет. Если
2mn = 2m1n1, m2 — n2 = m12 — n12, m2 + n2 = m12 + n12,
то отсюда следовало бы, что
m2 = m12, n2 = n12 или m = m1, n = n1.
3. Если число с является величиной гипотенузы пифагорова треугольника, то произведение kс, где k — любое целое число, обладает теми же свойствами. Таким образом, достаточно рассмотреть лишь значения с ≤ 100, которые не имеют делителей и могут быть величиной гипотенузы. Соответствующие
[…]
Система задач 8.2.
2. Для с = 19 последние два члена в формуле (8.2.2) можно заменить числом 1, поскольку тогда [1/4 c] — 2c ≡ 1 (mod 7).
Система задач 8.3.
1. 1:2:3:4:5:6:7:8
7:6:5:8:3:2:1:4
8:7:6:5:4:3:2:1
2:1:7:6:8:4:3:5
3:8:1:7:6:5:4:2
4:3:2:1:7:8:5:6
5:4:8:2:1:7:8:3
6:5:4:3:2:1:8:7
2. Когда r = 2, исключительный случай попадает на х = 1, следовательно, 1 играет с 8, а 8 играет с 1.
Для других значений х = 2, 3…, 7
y ≡ 2 — х ≡ 9 — х (mod 7),
т. е. соответственно у = 7, 6…, 2.
3. Команда N — 1 играет с
y ≡ r — (N — 1) ≡ r (mod (N — 1))
в r-м туре. Команда N — 1 может быть исключительной командой, если
2(N— 1) ≡ (mod (N— 1)),
следовательно, r = N — 1 и тогда команда N — 1 играет с командой N.
4. Условие (8.3.2) симметрично относительно х и уr, когда х — обычная команда. Если х удовлетворяет условию (8.3.3), то эта команда играет с командой N и, по определению, команда N играет с командой х.
ЗАКЛЮЧЕНИЕ
Таково наше приглашение в теорию чисел. Если она заинтересовала вас и вы хотите познакомиться с ней поближе, то для этого следует прочесть какой-нибудь систематический курс теории чисел, например,
И. М. Виноградов. Основы теории чисел. — М: Наука, 1972.
Существует также ряд популярных книг, освещающих отдельные вопросы теории чисел. Из них мы рекомендуем вам следующие:
Н. Н. Воробьев. Признаки делимости. — М: Наука, 1980.
Л. А. Калужнин. Основная теорема арифметики. — М.: Наука, 1969.
В. Серпинский. О решении уравнений в целых числах. — М.: Физматгиз. 1963.
В. Серпинский. Что мы знаем и чего не знаем о простых числах. — М. — Л.: Физматгиз, 1961.
В. Серпинский. 250 задач по элементарной теории чисел. — М.: Просвещение, 1968.