Приглашение в теорию чисел

РЕШЕНИЯ ИЗБРАННЫХ ЗАДАЧ

Система задач 1.3.

Ответы для обеих задач можно найти в табл. 3 на стр. 61.

Система задач 1.4.

1. Предположим, что верно соотношение

T_n-1 = 1/2 (n-1) n.

Можно проверить его для n= 2, 3, 4. Из рис. 4 видно, что Т_n получается из T_n-1 прибавлением числа n, поэтому

Т_n = Т_n-1 + n = 1/2 n (n + 1).

2. Из рис. 5 видно, что для того, чтобы получить Р_n, нужно прибавить к Р_n-1 число

1 +3 (n — 1) = Зn — 2.

Если мы уже знаем, что

P_n-1 = 1/2 (3 (n — 1)² — (n — 1))

(это справедливо для п = 2, 3, 4, в соответствии с последовательностью (1.4.3)), то отсюда следует, что

Р_n = P_n-1 + 3n — 2 = 1/2 (Зn² — n).

3. Мы можем получить n-е k-угольное число из (n — 1) — го, прибавив к нему

(k — 2) (n — 1) + 1

и выводя формулу таким же способом, как и в задаче 2. Задачи 2 и 3 могут быть решены иначе: делением точек на треугольники, как указано на рис. 5, и использованием формулы для Т_n. Проведите это доказательство во всех деталях.

Система задач 1.5.

1. Например, квадрат

16  3  2 13

 9  6  7 12

 5 10 11  8

 4 15 14  1

полученный перестановкой второй и третьей строк квадрата Дюрера, также является магическим. Менее тривиальным является квадрат

16  4  1 13

 9  5  8 12

 6 10 11  7

 3 15 14  2

2. Так как числа в квадрате 4 × 4 не превышают 16, возможны лишь два года, 1515 и 1516. Первый, очевидно, исключается, во втором случае построить квадрат оказывается невозможным.

Система задач 2.1.

2. 1979.

3. Числа от 114 до 126 все составные.

Система задач 2.3.

1. n = 3, 5, 15, 17,51,85

2. Имеем

360°/51 = 6 360°/17 — 360°/3.

3. Количество различных произведений чисел Ферма (от одного до пяти чисел в одном произведении) равно

5 + 10 + 10 + 5 + 1 = 31.

Таково количество чисел, для которых могут быть построены многоугольники. Наибольшим значением является

n = 3 • 5 • 17 • 257 • 65537 = 4 294 967 295.

Система задач 2.4.

1. В каждой из первых десяти сотен имеется соответственно 24, 20, 16, 16, 17, 14, 16, 14, 15, 14 простых чисел.

2. Существует 11 таких простых чисел.

Система задач 3.1.

1. 120 = 2³ • 3 • 5; 365 = 5 • 73; 1970 = 2 • 5 • 197.

3. 360 = 2 • 2 • 90 = 2 • 6 • 30 = 2 • 10 • 18 = 6 • 6 • 10.

Система задач 3.2.

1. Простое число имеет два делителя; р^α — степень простого числа, имеет а + 1 делитель.

2. τ(60) = 12, τ(366) = 8, τ(1970) = 8.

3. Наибольшим количеством делителей у числа, не превосходящего 100, является 12. Такое количество делителей имеют числа 72, 84, 90, 96.

Система задач 3 3.

1. 24; 48; 60; 10080.

2. 192; 180; 45360.

3. 24 и 36.

4. Пусть число делителей равно rs, где r и s — простые числа. Тогда

n = p^rs-1 или n = p^r-1 q^s-1,

где р и 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 не имеют общих множителей. Возводя в квадрат это соотношение, получаем 2b² = a.

По теореме о единственности разложения число а делится на 2, следовательно, а² делится на 4. И вновь по теореме о единственности разложения, примененней к числу b², получаем, что 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/5³] и т. д. Это показывает, что выражение для точной степени числа 5, делящей число n! таково:

[n/5] + [n/5²] + [n/5³] +… (*)

В этой сумме достаточно выписать лишь те члены, в которых у выражения в квадратных скобках числитель не меньше знаменателя.

Точно такие же рассуждения можно провести для нахождения соответствующей степени любого другого простого числа р. В частности, когда р = 2, получается выражение

[n/2] + [n/2²] + [n/2³] +…

Ясно, что это выражение не меньше, чем выражение (*), т. е. в числе n! каждому множителю 5 можно подобрать множитель 2. Таким образом, выражение (*) также дает и величину степени числа 10, делящей n! которая равна числу нулей, стоящих в конечной части записи числа.

Примеры. n = 10, [10/5] = 2, [10/5²] = 0, поэтому 10! оканчивается двумя нулями;

n = 31, [31/5] = 6, [31/5²] = 1, [31/5³] = 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 = 2m₁n₁, m² — n² = m₁² — n₁², m² + n² = m₁² + n₁²,

то отсюда следовало бы, что

m² = m₁², n² = n₁² или m = m₁, n = n₁.

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 играет с командой х.