О. ОРЕ - Приглашение в теорию чисел Страница 23

[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.

А. Я. Хинчин. Три жемчужины теории чисел. — М.: Наука, 1979.

М. М. Постников. Теорема Ферма. — М.: Наука, 1978.

Примечания

1

Игра с передвижением фишек по размеченной доске. (Прим. перев.)

2

Бенджамин Франклин (1706–1790) — выдающийся американский общественный деятель, дипломат и ученый. (Прим. перев.)

3

The Papers of Benjamin Franclin, Yale University Press, т. 4, c. 392–402.

4

Формат кварто — формат в 1/4 долю листа, т. е. 450 мм × 300 мм. (Прим. перев.)

5

Леонард Эйлер (1707–1783) — выдающийся математик, родившийся в Швейцарии, большую часть жизни провел в России, являясь членом Петербургской Академии наук. (Прим. перев.)

6

Аликвотные дроби — дроби вида 1/n; в древности было принято всякую дробь представлять в виде суммы аликвотных дробей. Например, 5/12 = 1/12 + 1/3. (Прим. перев.)

7

Американская фирма, выпускающая вычислительное оборудование. (Прим. перев.)

8

Последователи философской школы Пифагора. (Прим. перев.)

9

На счетах, принятых в СССР, на каждой спице располагается 10 косточек. (Прим. перев.)

10

При игре в «Ним» раскладывается некоторое количество камешков в несколько кучек. Двое играющих по очереди берут камешки из кучек, при ходе можно брать произвольное количество камней, но только из одной кучки. Выигрывает игрок, взявший последний камень. (Прим. перев.)

11

Вышлите побольше денег.

12

День нападения японского флота на американскую военную базу Пирл-Харбор, начало войны США и Японии. (Прим. перев.)

13

Это распространенная ошибка. Первым днем следующего столетия будет 1 января 2001 года, который будет понедельником. (Прим. перев.)

14

У нас переход на григорианский календарь произошел в 1918 году; вместо 1 февраля старого стиля стали считать 14 февраля нового стиля. (Прим. перев.)