Арифметика и принципы подсчёта

30

Арифметика и принципы подсчета

Н. Б. ВАСИЛЬЕВ,
В. Л. ГУТЕНМАХЕР

В основе математики лежит арифметика — теория натуральных чисел 1, 2, 3, … . В теории число глубоких и красных теорем. Немало в ней трудных и до сих пор не решенных проблем, в течение сотен лет не поддаюшихся усилиям самых выдающихся математиков. Цель разделы современной математики возникли из попыток решения и обобщения теоретико-числовых задач. К. Ф. Гаусс (1777—1855), сделавший много замечательных открытий в теории чисел и в других областях математики, сказал: «Matematika — царица наук; теория чисел — царица математики».

Цель этой статьи — познакомить читателей с простейшим понятиями этой увлекательной науки, основной теоремой арифметики, некоторых арифметических функций и принципами подсчета.

§ 1. Простые и составные числа

Всюду в дальнейшем мы будем иметь дело с натуральными числами. Мы говорим, что число $n$ делится на число $a$, если существует такое число $b$, что $n=ab$. В этом случае число $a$ называется делительem числа $n$, а число $n$ называется, в свою очередь, кратным числу $a$.

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

Каждее натуральное число можно разложить в произведение простых.

В самом деле, составное число $n$ можно разложить в произведение двух множителей, меньше $n$. Если среди них есть не простые (составные), можно каждае из них разложить в произведение двух меньше

31

и т. д. Очевидно этот процесс не может продолжаться бесконечно, потому что на каждом шагу мы получаем меньше множители, чем на предыдущем, а всего натуральных чисел, меньших $n$, конечное число: $n-1$. В результате мы приходим к разложению числа на простые множители.

Объчно одинаковые простые множители собирают вместе и записьют разложение в таком стандартном виде:

$$n = p_1^{a_1} \cdot p_2^{a_2} \cdot \dots \cdot p_k^{a_k},$$

где $p_1 < p_2 < \dots < p_k$ — различные простые числа, $a_1, a_2, \dots, a_k$ — натуральные числа. Например, $1350 = 2 \cdot 3^3 \cdot 5^2$.

Основная теорема арифметики. Всякое натуральное число, больше 1, разлагается на простые множители единственным образом.

Основной эта теорема называется потому, что практические все свойства делимости чисел являются ее следствиями.

Мы не будем останавливаться на доказательстве основной теоремы (его можно найти, например, в [1], [3]), а формулируем лишь одно ее следствие.

Для того чтобы число $a$ делилось на число $b$, необходимо и достаточно, чтобы каждый простый множитель, входящий в разложение числа $b$, входил в разложение $a$ в такой же или в более высокой степени.

А как разложить больше число на простые множители? В этом нам помогет такое полезное наблюдение.

Если число $n$ составляет, то у него есть делитель, не превышший $\sqrt{n}$ и больше 1.

Допустим противное. Пусть $n=ab$, и оба делителя $a$ и $b$ больше, чем $\sqrt{n}$. Поскольку $a > \sqrt{n}$ и $b > \sqrt{n}$, по лучем, что $ab > n$, что противоречит предположению.

Чтобы убедиться в простоте данного числа $n$ или, если $n$ составляет, найти его делитель, достаточно проверить, делится ли $n$ на простые числа, не больше $\sqrt{n}$.

Составить список простых чисел, не превышающих заданного числа $N$, можно таким образом. Надо выписать подряд все натуральные числа от 1 до $N$, вычернуть единицу, потом вычернуть все четные числа, кроме числа 2, затем вычернуть все числа, кратные 3, кроме самого числа 3, затем — кратные 5, и т. д. выплить до самого большого простого числа, не превышющего $\sqrt{N}$. После вычеркивания чисел, кратных какому-то простому числу $p$, первое не вычеркиvole число и будет следующего за $p$ простым числом. Этот метод просвищения чисел называется «решетом Эратосфена». Он не так плох, как кажется на первый взгляд: например, чтобы составить таблицу простых чисел до 2000, достаточно вычернуть все кратные первым четырнадцатим простым числом от 2 до 43 (так как $47^2 > 2000 > 43^2$). С помощью современных ЭВМ составлены очень больше таблицы простых чисел. Здесь, конечно, стоит заметить, что все простые числа выписать нельзя. Как умел доказывать еще Евклид,

Существует бесконечно много простых чисел.

Предположим, что простых чисел — конечное число и $p$ — самое большое из них. Расмотрим произведение $p! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot \dots \cdot p$ всех чисел от 1 до $p$ (пчетается «$p$ факторial»). Число $p!$ делится на все простые числа, так как, по предположению, в произведение $p!$ содержится все простые числа. Следующое за ним в натуральном ряду число $p! + 1$ должно раскладываться на простые множители, но это не возможно, так как $p! + 1$ не делится ни на одно из простых чисел! Противоречие.

Многие древние и до сих пор до конца не решенные проблемы теории чисел относятся к распределению простых чисел в натуральном ряду.

32

Например, наблюдаяя показывают, что встречаются рядом стоящие простые нечетные числа: 3 и 5, 5 и 7, 17 и 19, 29 и 31 и т.п. Такие числа называются простыми близкими. До них пор не известно, конечно или бесконечно количество пар простых близцев.

С другой стороны, между простыми числами могут встречаться сколь годно больше промежутки, точнее

Для любого $k$ в натуральном ряду существует $k$ последовательных составных чисел.

В самом деле, возьмем число $(k+1)!$ и рассмотрим ряд из $k$ последовательных чисел:

$$(k+1)!+2; (k+1)!+3; (k+1)!+4;...$$
…; $(k+1)!+k+1,$

Все они — составные: первое делится на 2, второе — на 3, …, последнее — на $k+1$.

Задачи

1. Разложите на простые множители числа $a$) 1981; $b$) 1982; $c$) 1983; $d$) 1984.
   Решение задачи 1$\theta$). Разделив 1983 на 3, получим 1983=3·661. Телер ищем делители числа 661. Так как $25^2<661<26^2$, нужно проверить делимость на простые числа 3, 5, 7, 11, 13, 17, 19, 23. Ни на одно из них 661 не делится, значит, 661 — простое число.

2. Укажите в натуральном ряду $a)$ шесть; $b)$ тринадцать последовательных составных чисел.
   $\theta)$ Существуют ли такие соседние простые числа, между которых в натуральном ряду помещаетсяровно шесть составных чисел?

3. Доказите, что если $d$ — наиболее делитель составного числа $n$, меньший $n$, то число $n/d$ — простое.

4. Доказите, что среди натуральных чисел от 1 до 30$m$ не более 10$m$ простых чисел (при каждой $m=1, 2, 3, ...$).

5. Найдите все такие числа $p$, что числа $p, p+2, p+4$ одновременно является простыми (такие числа можно назвать простыми «тройнями»).

6. Каким количество нулей кончается десятичная запись числа 30!?

7. Докажите, что среди чисел 2, 5, 8, 11, … (то есть чисел вида $3m+2$, где $m=0, 1, 2, ...$) бесконечно много простых.

§ 2. Количество делителей.
Комбинаторное правило произведения

На рисунке 1 ниже выписаны все натуральные делители чисел 96 и 144. Мы видим, что все делители числа 96 разбиаются на пары дополнительных друг друга делителей (на рисунке 1 они соединены двумми), а числа 144 один из делителей, 12, является дополнительным к самому себе, поскольку $144=12^2$. Из симметрики множества делителей следует такое утверждение:

Если число $n$ не является квадратом целого числа, то у него четное число делителей, а если является — то нечетное.

В самом деле, каждому делителю $a$ числа $n$, меньше $\sqrt{n}$, соответствует делитель $n/a$, больше $\sqrt{n}$. Поэтому делители, отличных от $\sqrt{n}$, всегда число. Если же $n=k^2$, то к ним добавляется еще один делитель $k$.

Пусть $d(n)$ — количество делителей числа $n$. Как показано выше, если $n$ — полный квадрат, то $d(n)$ — нечетное число (например, $d(144)=15$), а если нет, то $d(n)$ — четное число (например, $d(96)=12$). Покажем теперь, как, зная разложение числа $n$ на простые множители, находить значение $d(n)$.

Прежде всего, заметим, что при простом $p$ всегда $d(p^a)=a+1$.

Действительно, по определению, простое число $p$ имеет только два де-

Рис. 1. Делители и дополнительные к ним

33

Рис. 2. Правило произведение: делители $2^{\beta_1} \cdot 3^{\beta_2}$ числа $144 = 2^4 \cdot 3^2 (0 \leq \beta_1 \leq 4, 0 \leq \beta_2 \leq 2)$ размешаются в таблице $5 \times 3$.

литея: 1 и $p$, а, в силу следствия из основной теоремы арифметики, число $p^a$ имеет $(a+1)$ делители: 1, $p$, $p^2$, …, $p^a$ (считается, что $p^0 = 1$).

Рассмотрим теперь число $n$ с двумя различными простыми множителими, например $n = 144 = 2^4 \cdot 3^2$. Все его делители имеют вид $2^{\beta_1} \cdot 3^{\beta_2}$, где $\beta_1$ может принимать любое из пятей целых значений от 0 до 4, $\beta_2$ — одно из трех значений 0, 1 или 2. Значит, всего разных пар $(\beta_1; \beta_2)$ может быть $3 \cdot 5 = 15$, так что $d(144) = 15$ (см. рис. 2). Здесь мы воспользовались полезным принципом подчета.

Правило произведения. Если элемент $\beta_1$ можно выбрать $N_1$ способами, а элемент $\beta_2$ — незначimo от $\beta_1 - N_2$ способами, то всего можно составить $N_1 \cdot N_2$ различных пар $(\beta_1; \beta_2)$. Вообще, если нужно составить набор $(\beta_1; \beta_2; ..., \beta_k)$ из $k$ элементов, причем элемент $\beta_1$ можно выбрать $N_1$ способами, элемент $\beta_2$ — $N_2$ способами, …, элемент $\beta_k$ — $N_k$ способами, то всего можно составить $N_1 \cdot N_2 \cdots N_k$ различных наборов $(\beta_1; \beta_2; ...; \beta_k)$.

Это общее правило позволяет написать формулу для числа делителей любого $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$. В самом деле, согласно следствию из основной теоремы арифметики, любой делитель числа $n$ имеет вид $p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k}$, где $\beta_i$ принимает одно из $(\alpha_i + 1)$ значений 0, 1, …, $\alpha_i$. Следовательно, количество разных наборов $(\beta_1; \beta_2; ...; \beta_k)$, а значит, и различных делителей числа $n$, равно $d(n) = (\alpha_1 + 1)(\alpha_2 + 1) \cdots (\alpha_k + 1)$. (*)

Задание:
8. Найдите: a) $d(1000)$; 6) $d(1350)$; b) $d(5040)$; г) $d(84^{19})$.

Решение задачи 6). Ответ: 24. Так как $1350 = 2 \cdot 3^3 \cdot 5^2$, по формуле (*) получаем $d(2^1 \cdot 3^3 \cdot 5^2) = (1 + 1)(3 + 1)(2 + 1) = 24$.

9. Приведите пример числа, имеющего a)ровно 6 делителей; 6)ровно 7 делителей.

10. Докажите, что число $n$, дающее при делении на 3 остаток 2, имеет поровну делитель вида $3l + 1$ и $3s + 2$ и не является полным квадратом.

11. Окружность разбитка на 720 одинаковых дуг. Сколько существует различных (по числу сторон) правильных многоугольников с вершинами в точках разбиения?

12. Сколько у числа $n$ четных делителей (напишите общую формулу)? Для каких чисел $n$ количество таких делителей равно $\frac{1}{2} d(n)$?

13. В письменном столе имеется 9 ящков. Сколько способами можно разложить по ним пять разных книг?

Ответ: $9^5$ способов. Решение. Первую книгу мы можем положить 9 способами в тот или иной ящик, и, независяimo от этого выбора, есть 9 способов выбрать ящик для второй книги, и т. д. По правилам произведения, все способов $9^5$.

14. Сколько существует трехзначных чисел, у которых все цифры нечетные?

15. Сколько существует пятизначных чисел, в десятичной записьх хотя бы один раз встречается цифра 5?

§ 3. Функция Эйлера.
Включения и исключения

В § 2 мы познакомились с арифметической функцией Эйлера: $\varphi(n)$ — количество чисел, меньше числа $n$ и взаимно простых с ним, то есть таких чисел, которые не имеют с $n$ общих делителей (кроме 1).

На рисунке 3 для примера выписаны числа от 1 до 18. Мы видим, что все взаимно простые с 18 числа разбиаются на пары $(a; 18 - a)$.

Такая симметрия будет для любого $n > 2$: если число $a$ взаимно простое с $n$, то $(n - a)$ также будет взаимно простое с $n$ и не равно $a$. В самом деле, если бы $n - a$ и $n$ имели общий делитель $p > 1$, то их разность $n - (n - a) = a$ имела бы тот же делитель $p$, тем самым $n$ и $a$ не были бы взаимно просты.

Из этой симметрии $a \leftrightarrow (n - a)$ мы видим, что число $\varphi(n)$ всегда четно (при $n > 2$).

Показем теперь, как находится $\varphi(n)$, зная разложение числа $n$ на

34

Простые множители. Прежде всего, заметим, что если $p$ простое, то $\varphi(p) = p - 1$, так как все числа 1, 2, …, $(p - 1)$ взаимно просты с $p$ и меньше его. Пусть $n = p^\alpha$, где $p$ — простое число и $\alpha > 1$. тогда из $n$ чисел, не превысading их $n$, мы должны исключить те, которые делятся на $p$. Таким чисел

$$\frac{n}{p} = \frac{p^\alpha}{p} = p^{\alpha - 1},$$

позетом

$$\varphi(n) = n - \frac{n}{p} = n \left(1 - \frac{1}{p}\right).$$

Рассмотрим теперь числа $n = p_1^{\alpha_1} p_2^{\alpha_2}$ с двумя различными простыми множителими. Подсчет $\varphi(n)$ (для $n = 18$ он продолжан на рисунке 3) мы проиллюстрируем диаграммой на рисунке 4: квадрат избражает множество чисел от 1 до $n$, красный и голубой кругги — это множество чисел, деляшихся на $p_1$ и $p_2$ соответственно, пересечение кругов — множество чисел, деляшихся на $p_1 p_2$.

Числа, взаимно простые с $n$, изобраются заштрихованной частью квадрата. Для определения их числа мы должны исключить $N_1 = n/p_1$ «красных чисел», $N_2 = n/p_2$ «голубых» и прибавить $N_{12} = n/p_1 p_2$ чисел, лежащих в пересечении кругов. Таким образом,

$$\varphi(n) = N - N_1 - N_2 + N_{12} = n - \frac{n}{p_1} - \frac{n}{p_2} + \frac{n}{p_1 p_2} =$$

$$= n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right).$$

Разобрать случай числа $n = p_1^{\alpha_1} p_2^{\alpha_2}$ с темя различными множителими нам помогет рисунок 5: квадрат избражает множество чисел, не превысading их, а кругги — множество чисел, деляшихся на $p_1$, на $p_2$ и на $p_3$; тогда в кругах будет соответствено $N_1 = \frac{n}{p_1}, N_2 = \frac{n}{p_2}$ и $N_3 = \frac{n}{p_3}$ чисел, в их попарных пересечениях — $N_{12} = \frac{n}{p_1 p_2}, N_{13} = \frac{n}{p_1 p_3}$ и $N_{23} = \frac{n}{p_2 p_3}$ чисел, а в пересечении всех трех кругов — $N_{123} = \frac{n}{p_1 p_2 p_3}$ чисел (это числа, деляшиеся одновременно на $p_1, p_2$ и $p_3$, то есть на $p_1 p_2 p_3$).

Мы должны подсчитать, сколько чисел содержится в квадрате, но не попадает ни в один из кругов. Если мы вычитем из $n$ сумму $(N_1 + N_2 + N_3)$, то числа, попавшиеровно в два из трех кругов, мы вычитем два раза, а числа, попавшие во все три круга — даже три раза.

Теперь к разности $N - (N_1 + N_2 + N_3)$ добавим сумму $(N_{12} + N_{13} + N_{23})$. Тогда все числа, попающие только в одной в два круга, мы учтем правильно, и только числа,

Рис. 4.

Рис. 5. Если все это в квадрате $N$ элементов, то вне кругов их $N - N_1 - N_2 - N_3 + N_{12} + N_{23} + N_{31} - N_{123}$.

35

попавшие во все три круга одновременно — неправильно: их количество мы трижды вычли и вновь трижды прибавили. Придется из суммы $N - (N_1 + N_2 + N_3) + (N_{12} + N_{13} + N_{23})$ вычесть еще $N_{123}$. Теперь все числа, вошедшие в обедининие трех кругов, мы учили по разу и пришли к такой формуле:

$$\varphi(n) = n - \frac{n}{p_1} - \frac{n}{p_2} - \frac{n}{p_3} + \frac{n}{p_1 p_2} + \frac{n}{p_1 p_3} + \frac{n}{p_2 p_3} - \frac{n}{p_1 p_2 p_3} = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \left(1 - \frac{1}{p_3}\right).$$

Мы встретились здесь с частными случаями такого обещенного правила подсчета.

Правило включений и исключений. Пусть задано множество $A$ и выделено $k$ его подмножества. Количество элементов множество $A$, которые не входят ни в одной из выделенных подмножества, подсчитывается так: надо из общшего числа элементов $A$ вычесть количество элементов всех $k$ подмножества, прибавить количество элементов всех их попарных пересечений, вычесть количество элементов всех трейных пересечений, прибавить количество элементов всех пересечений по четыре и т. д. вплоть до пересечения всех $k$ подмножества.

Примения это правило к подсчету $\varphi(n)$, где

$$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k},$$

и использует алгебраические тожества

$$1 - x_1 - x_2 - \dots - x_k + x_1 x_2 + x_1 x_3 + \dots + x_{k-1} x_k - x_1 x_2 x_3 - \dots - x_{k-2} x_{k-1} x_k + \dots + (-1)^k x_1 x_2 \dots x_k = (1 - x_1) (1 - x_2) \dots (1 - x_k)$$

(его левая часть устройства как раз по правилам «включений и исключений»), можно получить общую формулу

$$\varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right).$$

Заметим, что написанное выше алгебраическое тожество можно использовать и при доказательстве общего правила включения и исключения: положив несколько $j$ из $k$ букв $x_1, x_2, \dots, x_k$ равными 1, а остальные $(k - j)$ — нулю, мы получим (при $0 < j \leq k$) в правой части 0, а левая часть показет, что элементы пересеченияровно $j$ подмножества одинаковое число раз прибавляются и вычитаются.

В заключение отмечим, что функция $\varphi(n)$ и функция $d(n)$ из предыдущего параграфа обладают таким важным свойством, которое в теории чисел называется мультипликативно:

Если $a$ и $b$ взаимно просты, то $\varphi(ab) = \varphi(a) \cdot \varphi(b)$ и $d(ab) = d(a) d(b)$

(Убедитесь в этом самостояльно.)

Задачи

16. Сколько существует правильных несократимых дробей со значением 288?

17. Найдите $a)$ $\varphi(96)$; $b)$ $\varphi(540)$; $b)$ $\varphi(1983)$.

18. Сколько существует чисел, не превысших 1000, которые $a)$ делятся одновременно на 6 и на 15; $b)$ делятся на 3, но не делятся на 7; $b)$ делятся на 6 или на 15.

19. Сколько существует натуральных чисел, не превысших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

20. Объединение множества $A$ и $B$ состоит из 25 элементов, пересечения — из 10 элементов. Сколько элементов в множестве $A$, если в $B$ 15 элементов; $6$ 21 элемент; $b)$ 10 элементов?

21. В декабре было 10 ясных и безветренных дней, 15 дней был ветер и 12 дней шелсен. Сколько дней была метель (и снег, и ветер)?

22. В группе из 25 студентов 12 изучают латынь, 10 — греческий и 9 — санскрит. Для каждой двух языков найдетсяровно 5 студентов, изучающих об этих языка. Сколько студентов изучает все три языка?

23. На каждой стороне треугольника $ABC$ отмечены по 9 точек, разбиаются ее на 10 равных частей. Расстоярим всевозможные треугольники с вершинами в отмещенных точках (по одной на каждой стороне). Сколько среди этих треугольников таких, у которых они одна из сторон не параллельна стороне треугольника $ABC$?

Литература

1. И. М. Виноградов. «Основы теории чисел» (М., «Наука», 1980).

2. И. И. Ежов, А. В. Скороход, М. И. Ядренко. «Элементы комбинаторики» (М., «Наука», 1977).

3. Л. А. Калужин. «Основная теорема алфметики» (М., «Наука», 1969).

4. О. Оре. «Приглашение в теории чисел» (М., «Наука», Библотечка «Квант», 1980).

5. Л. А. Басова, М. А. Шубин, Л. А. Эпштейн. «Лекции и задачи по математике» (М., «Просвещение», 1981).

6. Заочные математические оптимизации (М., «Наука», 1981).

7. Р. Курант, Г. Роббинс. «Что такое математика?» (М., «Просвещение», 1967).