Прежде чем излагать новый материал, необходимо договориться о терминологии. Понятие остатка от деления положительного целого числа $ B_{} $ на положительное целое число $ A_{} $ не вызывает затруднений. А как определить остаток от деления отрицательного числа на положительное, например, числа $ (-5)_{} $ на число $ 3_{} $ ? Можно действовать по схеме $$5=1\cdot 3 + 2 \ \Rightarrow \ -5=-1\cdot 3 - 2 \ ,$$ и за остаток от деления $ (-5)_{} $ на $ 3_{} $ принять отрицательное число $ (-2) $. Можно действовать по схеме $$5=1\cdot 3 + 2 \ \Rightarrow \ -5=-2\cdot 3 +1 \ ,$$ и за остаток от деления $ (-5)_{} $ на $ 3_{} $ взять положительное число $ 1_{} $. Так вот, мы условимся находить остаток по второй схеме — т.е. всегда считать его неотрицательным числом.

Теорема. Всякое целое $ B_{} $ представляется единственным образом с помощью целого $ A>0 $ равенством вида

$$ B=Aq+r\, , \quad npu \ \{q,r\} \subset \mathbb Z \ \ u \quad 0\le r<A \ . $$

Доказательство. Возьмем $ q = \lfloor B/A \rfloor $. Тогда по определению целой части числа будет выполнено $$q \le \frac{B}{A}< q+1 \ \Rightarrow \ Aq \le B < Aq + A \ \Rightarrow \ 0 \le B- Aq< A \ .$$ Положим $ r= B- Aq $, тогда получившаяся пара $ q_{} $ и $ r_{} $ удовлетворяет условиям теоремы.

Для доказательства единственности представления допустим существование еще одного: $$B=A \tilde{q}+\tilde{r} \quad npu \quad \{\tilde{q},\, \tilde{r}\} \subset \mathbb Z \ , \ 0\le \tilde{r}<A \ \ u \ \ \tilde{r} \ne r \ .$$ Предположив для определенности, что $ \tilde{r}>r $, вычтем это представление из предыдущего. Приходим к равенству $ A \left(q-\tilde{q} \right)=\tilde{r}-r $. Поскольку в нем все числа целые и $ \tilde{r}-r<A $, то оно возможно лишь при $ q-\tilde{q}=0 $, но тогда и $ \tilde{r}-r=0 $. Пришли к противоречию с предположением о неединственности представления числа $ B_{} $. ♦

В представлении $$ B=Aq+r\, , \quad \mbox{при} \ \{q,r\} \subset \mathbb Z \ \mbox{и} \quad 0\le r<A $$ число $ q_{} $ называется частным, а $ r_{} $ — остатком¹⁾ от деления $ B_{} $ на $ A_{} $. Если $ r=0_{} $, то говорят, что число $ B_{} $ делится нацело на $ A_{} $ или что $ B_{} $ кратно $ A_{} $, а число $ A_{} $ называется делителем $ B_{} $. Тривиальными делителями числа $ A\ne 0 $ называют $ 1_{} $ и само число $ A_{} $.

Пример. Для $ A=17 $ и $ B=232 $ имеем $ q=13,\, r=11 $; для $ A=17 $ и $ B=-15 $ имеем $ q =-1,\, r=2 $.

Пусть $ A_{} $ и $ B_{} $ — два целых числа, из которых по крайней мере одно отлично от нуля.

Наибольшим общим делителем чисел $ A_{} $ и $ B_{} $ называется наибольшее натуральное число $ d_{} $, являющееся делителем как для $ A_{} $, так и для $ B_{} $: $$ d = \operatorname{HOD} (A,B)=\max \big\{d_1\in \mathbb N \big| A \ \mbox{ делится на } \ d_1,\ B \ \mbox{ делится на } \ d_1 \big\} \ .$$ Понятие $ \operatorname{HOD} $ обобщается на произвольный набор целых чисел: $$d = \operatorname{HOD} (A_1,\dots,A_K)=\max \big\{ d_1\in \mathbb N \big| A_j \ \mbox{ делится на } \ d_1,\ \forall j\in\{1,\dots,K \} \big\} .$$ Наименьшим общим кратным отличных от нуля чисел $ A_1,\dots,A_K $ называют наименьшее положительное число, кратное всем этим числам $$ \operatorname{HOK} (A_1,\dots,A_K)=\min \big\{d_1\in \mathbb N \big| d_1 \ \mbox{ делится на } \ A_j,\ \forall j\in\{1,\dots,K \} \big\} \ .$$

Пример.

$ \operatorname{HOD} (-6,15)=3,\, \operatorname{HOD} (-6,0)=6,\, \operatorname{HOD} (-6,5)=1 , \operatorname{HOD} (6,10,15)=1 $; $ \operatorname{HOK} (6,10,15)=30 $.

Философ Платон считал, что наилучший размер для государства — $ 5040 $ семейств. Одним из обоснований этого числа он выдвигал его делимость на все числа от $ 1_{} $ до $ 10_{} $. Является ли это число наименьшим натуральным с таким свойством?

Для нахождения $ \operatorname{HOD} $ используется следующий алгоритм.

Алгоритм Евклида.

Пусть $ A_{} $ и $ B_{} $ — положительные целые. Поделим $ B_{} $ на $ A_{} $: $ B=Aq_1+r_1 $, пусть остаток $ r_1\ne 0 $: $ 0<r_1<A $. Поделим делитель на этот остаток: $ A=r_1q_2+r_2 $, предположим, что остаток $ r_2\ne 0 $: $ 0<r_2<r_1 $. Снова разделим делитель на остаток и продолжим процесс далее до тех пор, пока на каком-то шаге не произойдет деление нацело, т.е. остаток будет равен нулю²⁾. Запишем процедуру в виде схемы: $$ \begin{array}{lcl} B&=&Aq_1+r_1 \ , \quad 0<r_1<A\ , \\ A&=&r_1q_2+r_2 \ , \quad 0<r_2<r_1, \\ r_1&=&r_2q_3+r_3 \ , \quad 0<r_3<r_2, \\ \dots && \dots \\ r_{j-2}&=&r_{j-1}q_{j}+r_{j} \ , \quad 0<r_{j}<r_{j-1}, \\ \dots && \dots \\ r_{k-2}&=&r_{k-1}q_{k}+r_{k} \ , \quad 0<r_{k}<r_{k-1}, \\ r_{k-1}&=&r_{k}q_{k+1} . \end{array} $$

Теорема. Последний не равный нулю остаток в алгоритме Евклида совпадает с $ \operatorname{HOD}(A,B) $.

Доказательство. Если $ d = \operatorname{HOD}(A,B) $, то из первого равенства алгоритма Евклида следует, что $ r_{1} $ делится на $ d_{} $, тогда из второго равенства следует, что и $ r_{2} $ делится на $ d_{} $, и т.д., из предпоследнего равенства — что $ r_{k} $ делится на $ d_{} $.

С другой стороны, покажем теперь, что остаток $ r_{k} $ сам является общим делителем $ A_{} $ и $ B_{} $. Из последнего равенства алгоритма Евклида следует, что $ r_{k-1} $ делится на $ r_{k} $, тогда из предпоследнего — что $ r_{k-2} $ делится на $ r_{k} $, и т.д., из второго — что $ A_{} $ делится на $ r_{k} $, и, наконец, из первого — что $ B_{} $ делится на $ r_{k} $.

Итак, $ r_{k} $ делится на $ \operatorname{HOD} (A,B) $ и является общим делителем $ A_{} $ и $ B_{} $. Следовательно, по определению $ r_{k}=\operatorname{HOD} (A,B) $. ♦

Биографические заметки об Евклиде ☞ ЗДЕСЬ.

Пример. Найти $ \operatorname{HOD} (5797,7038) $.

Решение. $$ \begin{array}{rr|l} 7038 &&\,5797\\ \hline 5797 &&\,1\\ \hline 1241 \end{array} \quad \begin{array}{rr|l} 5797 &&\, 1241\\ \hline 4964 &&\,4\\ \hline 833 \end{array} \quad \begin{array}{rr|l} 1241 &&\, 833\\ \hline 833 &&\,1\\ \hline 408 \end{array} \quad \begin{array}{rr|l} 833 &&\, 408\\ \hline 816 &&\,2\\ \hline 17 \end{array} \quad \begin{array}{rr|l} 408 &&\, 17\\ \hline 408 &&\,24\\ \hline 0 \end{array} \ . $$ Ответ. $ \operatorname{HOD} (5797,7038)=17 $.

Доказать, что $ \operatorname{HOD}(A,B) $ совпадает с $ \operatorname{HOD} $ любой пары последовательных остатков алгоритма Евклида, т.е.

$$ \operatorname{HOD} (A,B)= \operatorname{HOD} (A,r_1)= \operatorname{HOD} (r_1,r_2)=\dots = \operatorname{HOD} (r_{k-1},r_{k}) \ . $$

Сколько операций содержится в алгоритме Евклида? — Ответ на этот вопрос дается следующей теоремой:

Теорема [Ламе]. Пусть $ B>A>0 $. Количество делений, необходимых для вычисления $ \operatorname{HOD} (A,B) $ (обозначено в приведенной выше схеме через $ k_{} $), не превосходит умноженного на $ 5_{} $ количества цифр в десятичном представлении $ A_{} $.

Доказательство ☞ ЗДЕСЬ.

Теорема. Существуют целые числа $ u_{} $ и $ v_{} $, удовлетворяющие уравнению линейного представления $ \operatorname{HOD} $: $$ uA+vB= \operatorname{HOD} (A,B) \ . $$

Доказательство. Выражения для чисел $ u_{} $ и $ v_{} $ можно найти с помощью частных $ q_{j} $ из алгоритма Евклида. Из первого равенства алгоритма Евклида следует, что $ r_{1}=B-Aq_1 $, т.е. $$r_1=u_1A+v_1B \quad npu \quad u_1=-q_1,\ v_1=1 \ .$$ Подставляя это выражение во второе равенство алгоритма, получим $$r_2=A-r_1q_2=A-(u_1A+v_1B )q_2=u_2A+v_2B $$ при $$ u_2=-q_2u_1+1=1+q_1q_2,\ v_2=-q_2v_1=-q_2 \ . $$ Подставляя найденные выражения в третье равенство, получим $$r_3=r_1-r_2q_3=(u_1A+v_1B)-(u_2A+v_2B)q_3=u_3A+v_3B $$ при $$ u_3=-q_3u_2+u_1,\ v_3=-q_3v_2 +v_1\ .$$ Выдвинув индукционное предположение о справедливости представления «промежуточного» остатка $$r_j=u_jA+v_jB $$ при $$ u_j=-q_ju_{j-1}+u_{j-2} \ , \quad v_j=-q_jv_{j-1}+v_{j-2} $$ для всех $ j\in \{4,\dots,k-1\} $, из предпоследнего равенства алгоритма Евклида получим $$r_k=-q_kr_{k-1}+r_{k-2}=-q_k(u_{k-1}A+v_{k-1}B)+(u_{k-2}A+v_{k-2}B)= u_kA+v_kB $$ $$\quad npu \quad u_k=-q_ku_{k-1}+u_{k-2},\ v_k=-q_kv_{k-1}+v_{k-2} \ , $$ т.е. закон формирования коэффициентов при $ A_{} $ и $ B_{} $ остается прежним. Но поскольку $ r_{k} $ совпадает с $ \operatorname{HOD}(A,B) $, то последнее равенство и дает требуемое линейное представление $ \operatorname{HOD} $: $ u=u_k, v=v_k $. ♦

Пример. Найти явные выражения для $ u_{j} $ и $ v_{j} $ через $ q_{1},q_{2},\dots $ при $ j\in \{3,4,5,6\} $.

Решение. $$ \begin{array}{lcl} u_3&=&-q_3u_2+u_1=-q_3(1+q_1q_2)-q_1=-(q_1+q_3+q_1q_2q_3) \ , \ v_3=1+q_2q_3 \ , \\ u_4&=&1+q_3q_4+q_1q_2+q_1q_4+q_1q_2q_3q_4, \ v_4=-(q_2+q_4+q_2q_3q_4) \ , \\ u_5&=&-(q_1+q_3+q_5+q_1q_4q_5+q_1q_2q_3+q_1q_2q_5+q_3q_4q_5+q_1q_2q_3q_4q_5) \ , \\ v_5&=&1+q_4q_5+q_2q_3+q_2q_5+q_2q_3q_4q_5 \ , \\ u_6&=&1+q_1q_2+q_1q_4+q_3q_4+q_1q_6+q_3q_6+q_5q_6+q_1q_2q_3q_4+q_1q_2q_5q_6+ \\ & &+q_1q_2q_3q_6+ q_1q_4q_5q_6+q_3q_4q_5q_6+q_1q_2q_3q_4q_5q_6 \ ,\\ v_6&=&-(q_2+q_4+q_6+q_2q_3q_4+q_2q_3q_6+q_2q_5q_6+q_4q_5q_6+ q_2q_3q_4q_5q_6) \ . \end{array} $$ Трудно уловить закономерность в формировании этих выражений из $ q_{j} $, тем не менее мы ее сейчас выявим. ♦

По какому закону формируется число слагаемых в каждом представлении?

Пусть имеется произвольная числовая последовательность $ x_1,x_2,\dots,x_j,\dots $ (не обязательно целочисленная). Числа $ K_{j} $, задаваемые соотношениями $$ K_0= 1,\ K_1 = x_1,\ K_j= K_{j-1}x_j+K_{j-2} \quad npu \ j\ge 2, $$ называются континуантами. Иногда то обстоятельство, что $ K_{j} $ зависит от $ x_1,\dots,x_j $ подчеркивают, записывая континуанту в виде $ K_j(x_1,\dots,x_j) $.

Теорема. Величина континуанты $ K_j(x_1,\dots,x_j) $ равна сумме произведения $ x_1\cdot x_2 \times \dots \times x_j $ и всевозможных произведений, получающихся из него вычеркиванием пар соседних множителей (и добавлением $ 1_{} $ в случае четного $ j_{} $).

Пример.

$$ \begin{array}{lcl} K_2(x_1,x_2)&=&x_1x_2+1 \ , \\ K_3(x_1,x_2,x_3)&=& x_1x_2x_3+x_3+x_1 \ , \\ K_6(x_1,x_2,x_3,x_4,x_5,x_6)&=&x_1x_2x_3x_4x_5x_6+x_3x_4x_5x_6 +x_1x_4x_5x_6+\\ &&+ x_1x_2x_5x_6+x_1x_2x_3x_6+x_1x_2x_3x_4+ \\ &&+x_5x_6+x_1x_6+x_1x_2+x_1x_4+x_3x_4+x_3x_6+1 \ . \end{array} $$ ♦

Легко видеть, что числа $ u_{j} $ и $ v_{j} $, введенные выше равенствами $$ u_j=-q_ju_{j-1}+u_{j-2} \ , \quad v_j=-q_jv_{j-1}+v_{j-2} \ , $$ являются континуантами: $$ \begin{array}{lll} u_j&=K_j(-q_1,-q_2,\dots,-q_j) & = (-1)^{j}K_j(q_1,q_2,\dots,q_j) \ , \\ v_j&=K_{j-1}(-q_2,\dots,-q_{j}) & = (-1)^{j-1}K_{j-1}(q_2,\dots,q_{j}) \ . \end{array} $$ Приведенные выше формулы явных выражений для этих величин с увеличением $ j_{} $ становятся слишком громоздкими. Для практических расчетов более просты вычисления континуант непосредственно по рекурсивным формулам. Поскольку выполняемые операции однотипны, вычисления удобно оформить в виде таблицы. Так, стартовое состояние таблицы для вычисления $ K_j(q_1,q_2,\dots,q_j) $ следующее:

и значение для $ K_2(q_1,q_2)=1+q_1q_2 $ вычисляется по схеме, указанной стрелками. Следующее состояние таблицы —

и очередное значение $ K_3(q_1,q_2,q_3)=K_1(q_1)+K_2(q_1,q_2)q_3 $ снова вычисляется по схеме, указанной стрелками.

Таблица для вычисления $ K_{j-1}(q_2,\dots,q_j) $ строится по тому же принципу, только с иными стартовыми значениями:

Обычно таблицы для вычисления обеих континуант объединяют.

Пример. Найти линейное представление $ \operatorname{HOD} (5797,7038) $.

Решение. Алгоритм Евклида для данного примера приведен в предыдущем пункте, он дает последовательность частных $ q_1=1,\, q_2=4,\, q_3=1,\, q_4=2 $, завершаясь при $ k=4_{} $. $$ \begin{array}{|c|c|c|c|c|c|} \hline j & 0 & 1 & 2 & 3 & 4 \\ \hline q_j & - & 1 & 4 & 1 & 2 \\ \hline K_j(q_1,q_2,\dots,q_j) & 1 & 1 & 5 & 6 & 17 \\ \hline K_{j-1}(q_2,\dots,q_j) & - & 1 & 4 &5 & 14 \\ \hline \end{array} $$ По формулам получаем $ u=17,v=-14 $.

Проверка. $ 17\times 5797 -14 \times 7038=98\,549-98\, 532=17= \operatorname{HOD} (5797,7038) $.

Существует бесконечное число линейных представлений $ \operatorname{HOD} $.

Доказательство. Действительно, если пара $ \tilde u, \tilde v $ — какое-то из решений уравнения $ uA+vB= \operatorname{HOD} (A,B) $, то при $ \forall t\in \mathbb Z $ пара $ \tilde{\tilde u}=\tilde u+tB,\tilde{\tilde v} =\tilde v-tA $ также является решением. Можно, например, подобрать число $ t_{} $ так, чтобы было выполнено $ 0\le \tilde{\tilde u}<B $. ♦

Биографические заметки об Евклиде ☞ ЗДЕСЬ.

Два целых числа $ A_{} $ и $ B_{} $ называются взаимно простыми, если $ \operatorname{HOD}(A,B)=1 $. Целые числа $ A_1,\dots,A_K $ называются взаимно простыми, если $ \operatorname{HOD}(A_1,\dots,A_K)=1 $.

Пример. Числа $ 6, 10, 15 $ являются взаимно простыми, но не являются попарно взаимно простыми.

Теорема 1. Для того чтобы положительные целые числа $ A_{} $ и $ B_{} $ были взаимно простыми, необходимо и достаточно существование целых чисел $ u_{} $ и $ v_{} $ таких, что $$ uA+vB=1 \ . $$

Доказательство. Если $ \operatorname{HOD}(A,B)=1 $, то справедливость равенства следует из теоремы предыдущего пункта. Обратно, если $ u_0A+v_0B=1 $ при некоторых $ u_0,v_0 $ и $ d= \operatorname{HOD}(A,B) $, то $ u_0A $ делится на $ d_{} $ и $ v_0B $ делится на $ d_{} $. Тогда их сумма, т.е. $ 1_{} $, делится на $ d_{} $. Это возможно тогда и только тогда, когда $ d=1 $. ♦

Теорема 2. Если каждое из чисел $ A_1,\dots,A_K $ взаимно просто с $ B_{} $, то и их произведение $ A_1\times \dots \times A_K $ взаимно просто с $ B_{} $.

Доказательство. Применим метод индукции по числу сомножителей. Пусть $ \operatorname{HOD} (A_j,B)=1 $ для всех рассматриваемых индексов $ j_{} $. По теореме $ 1 $ это условие эквивалентно выполнению равенств $$ u_1A_1+v_1B=1, \ u_2A_2+v_2B=1, \dots $$ при некоторых целых $ u_j,v_j $. В случае $ K=2 $, перемножая первые два равенства, получим $$ u_1u_2A_1A_2+\left(u_1v_2A_1 + u_2v_1A_2+v_1v_2B\right) B = 1 \ . $$ По теореме $ 1 $, числа $ A_1A_2 $ и $ B_{} $ взаимно простые.

Предположим теперь справедливость утверждения теоремы для $ K_{} $ сомножителей и докажем его для произведения $ A_1\times \dots \times A_KA_{K+1} $. Это произведение можно представить состоящим из двух множителей $ (A_1\times\dots \times A_K) $ и $ A_{K+1} $. Второй из этих множителей взаимно прост с $ B_{} $ по условию теоремы, а первый — по индукционному предположению. Их произведение взаимно просто с $ B_{} $ на основании доказанного выше. ♦

Теорема 3. Если произведение $ A\cdot B_{} $ целых чисел делится на целое число $ C_{} $ и $ \operatorname{HOD}(A,C)=1 $, то $ B_{} $ делится на $ C_{} $.

Доказательство. Поскольку $ \operatorname{HOD}(A,C)=1 $, то, по теореме $ 1 $, существуют целые числа $ u_0 $ и $ v_0 $ такие, что $ u_0A+v_0C=1 $. Умножив это равенство на $ B_{} $, получим $ u_0AB+v_0CB=B $. В левой части последнего равенства первое слагаемое делится на $ C_{} $ по условию, второе также делится на $ C_{} $, следовательно, и их сумма делится на $ C_{} $. ♦

Теорема 4. Если число $ A_{} $ делится на каждое из попарно взаимно простых чисел $ C_1,\dots,C_K $, то оно делится и на их произведение $ C_1\times \dots \times C_K $.

Доказательство. Поскольку $ A_{} $ делится на $ C_{1} $, то $ A=A_1C_1 $ при $ A_1\in \mathbb Z $. Поскольку $ A_{} $ делится на $ C_2 $ и $ \operatorname{HOD}(C_1,C_2)=1 $, то, по теореме $ 3 $, $ A_{1} $ делится на $ C_2 $ и, следовательно, $ A=A_2C_1C_2 $ при $ A_2\in \mathbb Z $. Поскольку $ A_{} $ делится на $ C_3 $ и $ \operatorname{HOD}(C_1C_2,C_3)=1 $ (по теореме $ 2 $), то $ A_{2} $ делится на $ C_3 $. Используя индукцию, через $ K $ шагов получим $ A=A_K\,C_1C_2\times \dots \times C_K $ при $ A_K \in \mathbb Z $. ♦

Довольно интересен ответ на следующий вопрос: какова вероятность того, что два случайным образом выбранных натуральных числа будут взаимно просты? Будем считать вероятность числом из интервала $ [0,1] $.

Теорема 5 [Чезаро]. Обозначим $ P_N $ вероятность того, что два числа случайно выбранные из множества $ \{1,2,\dots, N \} $, взаимно просты. Тогда

$$ \lim_{N\to \infty} P_N = \frac{6}{\pi^2} \approx 0.607927 \ . $$

Доказательство (набросок) ☞ ЗДЕСЬ.

Число $ 1_{} $ имеет только один положительный делитель, именно $ 1_{} $. В этом отношении число $ 1_{} $ в ряду натуральных чисел стоит совершенно особо. Всякое целое, большее $ 1_{} $, имеет не менее двух делителей: по крайней мере тривиальные делители (само число и $ 1_{} $) у него всегда существуют.

Если число $ A>1 $ имеет только тривиальные делители, то оно называется простым. Целое $ A>1 $, имеющее кроме тривиальных другие положительные делители, называется составным. В дальнейшем за простым числом закрепим обозначение $ p_{} $.

Теорема [Евклид]. Множество простых чисел бесконечно.

Доказательство проводится от противного. Предположим, что существует конечное число простых чисел и наибольшее из них равно $ p_{} $. Если мы рассмотрим все эти простые числа $ 2,3,5,7,11,\dots, p $, то всякое число $ A_{} $, большее $ p_{} $, должно быть составным и должно делиться по крайней мере на одно из этих простых чисел. Однако число $$ A=2\cdot 3 \cdot 5\times \dots \times p +1 $$ не делится нацело ни на одно из указанных чисел (дает в остатке $ 1_{} $). Противоречие доказывает ошибочность нашего предположения. ♦

Для составления таблицы простых чисел, не превосходящих данного целого $ A_{} $, существует простой способ, называемый

Решето Эратосфена.

Он заключается в следующем: выписываем числа $ 1,2,\dots,A $. Первое, большее $ 1_{} $, число этого ряда есть $ 2_{} $. Оно делится только на $ 1_{} $ и на само себя, и, следовательно, оно простое. Вычеркиваем из рассматриваемого ряда чисел все числа, кратные $ 2_{} $, кроме самого $ 2_{} $. Первое следующее за $ 2_{} $ невычеркнутое число есть $ 3_{} $. Оно не делится на $ 2_{} $ (иначе оно оказалось бы вычеркнутым). Следовательно, $ 3_{} $ делится только на $ 1_{} $ и на самого себя, а потому оно также будет простым. Вычеркиваем из рассматриваемого ряда чисел все числа кратные $ 3_{} $, кроме самого $ 3_{} $. Первое, следующее за $ 3_{} $, невычеркнутое число есть $ 5_{} $. Оно не делится ни на $ 2_{} $, ни на $ 3_{} $ (иначе оно оказалось бы вычеркнутым). Следовательно, $ 5_{} $ делится только на $ 1_{} $ и на самого себя, а потому оно также будет простым. Когда указанным способом уже вычеркнуты все числа, кратные простым, меньшим простого $ p_{} $, то все невычеркнутые, меньшие $ p^{2} $, будут простыми. Действительно, всякое составное число $ A_{1} $, меньшее $ p^{2} $, нами уже вычеркнуто, как кратное его наименьшего простого делителя, который $ \le \sqrt {A} <p $. Составление таблицы простых чисел, не превосходящих $ A_{} $, закончено, как только вычеркнуты все составные кратные простых, не превосходящих $ \sqrt {A} $.

Анимационная схема работы решета ☞ ЗДЕСЬ

Можно заметить, что относительная плотность простых чисел убывает: на первый десяток их приходится $ 4_{} $, т.е. $ 40_{} \% $, на сотню — $ 25_{} $ , т.е. $ 25 \% $, на тысячу — $ 168 $, т.е. $ \approx 17 \% $, на миллион — $ 78\, 498 $, т.е. $ \approx 8 \% $.

Теорема [Чебышев]. Обозначим количество простых чисел, не превосходящих $ N_{} $, через³⁾ $ \pi(N) $. Справедливы оценки

$$ \frac{\ln 2}{2} \frac{N}{\ln N} < \pi(N) < 2\ln 2 \frac{N}{\ln N} \ . $$ Здесь $ \ln $ означает натуральный логарифм, т.е. логарифм по основанию числа Эйлера $$e= \lim_{n\to +\infty} \left(1+ \frac{1}{n} \right)^n \approx 2.7182818284590452353\dots $$

На рисунке виден сравнительный рост количества простых чисел

Общей закономерности в распределении простых чисел среди всего ряда натуральных чисел не установлено, несмотря на то, что этой проблемой математика занимается уже более 2000 лет. Существуют пары простых чисел с минимальным расстоянием друг от друга: $$ (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), \dots ; $$ их называют близнецами⁴⁾. С другой стороны, существуют сколь угодно длинные отрезки натурального ряда, свободные от простых чисел:

Теорема. Для любого натурального $ k_{} $ существует натуральное число $ N_{} $ такое, что все числа

$$ N+1, N+2,\dots, N+k $$ являются составными.

Доказательство. Числа $$ (k+1)!+2, (k+1)!+3,\dots, (k+1)!+(k+1) $$ являются составными, поскольку первое делится на $ 2_{} $, второе — на $ 3_{} $, и т.д., последнее — на $ k+1 $. ♦

Отдельной задачей является вопрос о «генераторах» простых чисел — аналитически заданных последовательностях, все элементы которых являются простыми. Такие последовательности искались среди арифметических прогрессий, а, в общем случае, среди последовательностей вида $$ \left\{ a_0n^m+a_1n^{m-1}+\dots + a_m \right\}_{n=1}^{\infty} \quad \mbox{ при } \ \{a_0,\dots,a_m\} \subset \mathbb Z \, ; $$ а также среди чисел, близко расположенных к степеням $ 2_{} $. Так, например, доказано, что последовательности $$ \left\{4n+1 \right\}_{n=1}^{\infty} \quad \mbox{ и } \quad \left\{6n+1 \right\}_{n=1}^{\infty} $$ содержат бесконечно много простых чисел. Первые $ 40_{} $ чисел последовательности Эйлера $$ \left\{n^2-n+41 \right\}_{n=1}^{\infty} $$ являются простыми, но $ 41 $-е является составным; первые $ 79 $ чисел последовательности $$ \left\{n^2-79\,n+1601 \right\}_{n=1}^{\infty} $$ будут простыми, но $ 80 $-е является составным. Числа Ферма $$ 2^{2^n}+1 $$ будут простыми при $ n\in \{1,2,3,4,13,14,\dots \} $, но составными при $ n\in \{5,6,7,\dots,12,15,16,\dots\} $.

Сравнить плотности простых чисел в последовательностях Эйлера

$$ \left\{n^2-n+41 \right\} \quad \mbox{ и } \quad \left\{n^2+n+72\,491 \right\} $$ и в последовательности $$ \left\{n^2-79\,n+1601 \right\} $$ при $ n\in \{1,\dots, N \} $, где $ N\in \{ 10^2,10^3,10^6 \} $.

Геометрию последовательностей вида $ \left\{n^2-n+a \right\} $ при $ a\in \mathbb Z $ см. ☞ ЗДЕСЬ.

[2]. Проверить, что в последовательности

$$ \left\{n^2-2999\,n+2\,248\,541 \right\} $$ имеется $ 79 $ подряд идущих простых чисел.

Наибольшим числом, для которого — по состоянию на декабрь 2018 г. — установлена простота, является число $ 2^{82\,589\,933} -1 $, состоящее из $ 24\,862\,048 $ цифр. Числа вида $ 2^{n}-1 $ называются числами Мерсенна.

Критерии простоты числа $ p_{} $ в настоящем ресурсе:

☞ ТЕОРЕМА ВИЛЬСОНА;

☞ КРИТЕРИЙ, ОСНОВАННЫЙ НА ЗНАНИИ КАНОНИЧЕСКОГО РАЗЛОЖЕНИЯ ЧИСЛА $ p-1 $.

Теорема 1. Всякое целое $ A_{} $ или взаимно просто с данным простым $ p_{} $, или же делится на $ p_{} $.

Теорема 2. Если произведение нескольких сомножителей делится на данное простое $ p_{} $, то по крайней мере один из сомножителей делится на $ p_{} $.

Теорема 3 [основная теорема арифметики]. Всякое целое $ A>1_{} $ разлагается на произведение простых сомножителей и притом единственным образом (с точностью до порядка сомножителей).

В разложении числа $ A_{} $ на простые сомножители некоторые из последних могут повторяться. Пусть $ p_1,p_2,\dots,p_{\mathfrak r} $ — все различные простые сомножители числа $ A_{} $, а $ {\mathfrak m}_1, {\mathfrak m}_2, \dots, {\mathfrak m}_{\mathfrak r} $ —соответствующие показатели их вхождения в $ A_{} $. Представление $$ A=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}}= \prod_{j=1}^{{\mathfrak r}} p_j^{{\mathfrak m}_j} $$ называется каноническим разложением числа $ A_{} $ на сомножители, а сам процесс нахождения канонического разложения — факторизацией⁵⁾ числа $ A_{} $.

Пример. $ 18225625000=2^3\cdot 5^{7}\cdot 11^{2}\cdot 241 $.

Теорема 4. Если

$$ A=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} $$ — каноническое разложение числа $ A_{} $, то все делители этого числа заключены во множестве $$ \left\{p_1^{\ell_1}p_2^{\ell_2}\times \dots \times p_{\mathfrak r}^{\ell_{\mathfrak r}} \, \Big| \, 0\le \ell_1 \le {\mathfrak m}_1, 0\le \ell_2 \le {\mathfrak m}_2, \dots , 0\le \ell_{\mathfrak r} \le {\mathfrak m}_{\mathfrak r} \right\} \ . $$

Сколько чисел содержится в этом множестве?

Сумма различных делителей числа $ A_{} $ равна

$$ \frac{p_1^{{\mathfrak m}_1+1}-1}{p_1-1}\frac{p_2^{{\mathfrak m}_2+1}-1}{p_2-1} \times \dots \times \frac{p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}+1}-1}{p_{\mathfrak r}-1} \ . $$

Теорема 5. Пусть множество $ \{ p_1,\dots,p_{\mathfrak r} \} $ представляет собой объединение множеств простых сомножителей целых чисел $ A_1,\dots,A_K $. Выпишем «универсальное» каноническое разложение для каждого $ A_{j} $:

$$A_j=p_1^{{\mathfrak m}_{1j}}p_2^{{\mathfrak m}_{2j}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{{\mathfrak r}j}} $$ (здесь возможно, что некоторые из показателей $ {\mathfrak m}_{\ell j} $ равны нулю). Тогда$$ \operatorname{HOD} (A_1,\dots,A_K)= p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ , \quad \mbox{ где } \ {\mathfrak m}_{\ell} = \min_{j=1,\dots,K} {\mathfrak m}_{\ell j} \ , $$ $$ \operatorname{HOK} (A_1,\dots,A_K)= p_1^{{\mathfrak M}_1}p_2^{{\mathfrak M}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak M}_{\mathfrak r}}\ , \quad \mbox{ где } \ {\mathfrak M}_{\ell} = \max_{j=1,\dots,K} {\mathfrak m}_{\ell j} \ . $$

Пример.

$$ \operatorname{HOD} (20099016,\, 9900,\, 3690) = $$ $$ =\operatorname{HOD} (2^3\cdot 3^5\cdot 7^2\cdot 211,\ 2^2\cdot 3^2\cdot 5^2\cdot 11,\ 2\cdot 3^2\cdot 5\cdot 41)=2\cdot 3^2=18 \ ; $$ $$\operatorname{HOK} (20099016,\, 9900,\, 3690) =2^3\cdot 3^5 \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 41 \cdot 211 = 226616405400 \ . $$

Доказать, что для любых натуральных $ A_{} $ и $ B_{} $:

$$ \operatorname{HOD} (A,B) \cdot \operatorname{HOK} (A,B) = A\cdot B \ . $$

Результат предыдущего упражнения позволяет выразить $ \operatorname{HOK} (A,B) $ через $ \operatorname{HOD} (A,B) $. Как обобщить эту формулу — выразить $ \operatorname{HOK} $ произвольного набора чисел через $ \operatorname{HOD} $?

Ответ ☞ ЗДЕСЬ.

Теорема [Лежандр]. Простое число $ p_{} $ входит в каноническое разложение числа $ n!_{} $ с показателем

$$ {\mathfrak m}=\left\lfloor \frac{n}{p}\right\rfloor +\left\lfloor \frac{n}{p^2}\right\rfloor +\left\lfloor \frac{n}{p^3}\right\rfloor +\dots+\left\lfloor \frac{n}{p^K} \right\rfloor \ . $$ Здесь $ \lfloor A \rfloor $ обозначает целую часть числа $ A_{} $, а число $ K \in \mathbb N $ определяется как показатель максимальной степени $ p_{} $, умещающейся в $ n_{} $: $$ p^K\le n < p^{K+1} \ ; \ \mbox{ очевидно, } \ K=\lfloor \log_{p} n \rfloor \ . $$

Показать, что

$$ \left\lfloor \frac{n}{p^2}\right\rfloor = \left\lfloor \frac{\left\lfloor \frac{n}{p}\right\rfloor }{p} \right\rfloor \ . $$

Пример. Сколькими нулями оканчивается десятичное представление числа $ 153! $ ?

Решение. Вопрос равнозначен поиску максимального $ K\in \mathbb N $ такого, что $ 153! $ делится на $ 10^K=2^K\cdot 5^K $. Очевидно, что в каноническом разложении $ n!_{} $ показатель двойки будет больше показателя любого другого простого числа, и для ответа на наш вопрос достаточно подсчитать показатель пятерки. $$\left\lfloor\frac{153}{5}\right\rfloor +\left\lfloor\frac{153}{25}\right\rfloor+ \left\lfloor\frac{153}{125}\right\rfloor=30+6+1=37 \ .$$

Ответ. Десятичное представление оканчивается $ 37_{} $-ю нулями.

Теорема. Мультиномиальный коэффициент $$ \frac{n!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad n_1+ n_2+\dots +n_K=n $$ является целым числом.

Доказательство ☞ ЗДЕСЬ.

Задача нахождения канонического представления числа становится достаточно трудоемкой при больших $ A_{} $ : в худшем случае приходится проверять $ A_{} $ на делимость со всеми простыми числами $ 2,3,5,\dots $, не превосходящими $ \sqrt {A} $. В связи с этим представляют интерес косвенные признаки делимости на данное простое $ p_{} $, т.е. такие, которые не требуют явного выполнения деления $ A_{} $ на $ p_{} $. Из школьного курса известны признаки делимости на $ 2,3 $ и $ 5 $, когда исключительно по цифрам десятичного представления $ (s+1) $-значного числа $$ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} = {\mathfrak a}_1\times 10^s+{\mathfrak a}_2 \times 10^{s-1} + \dots +{\mathfrak a}_s \times 10 + {\mathfrak a}_{s+1} $$ можно установить, делится или не делится $ A_{} $ на $ p_{} $. Такие признаки можно установить и для других простых чисел. Проиллюстрируем на примерах $ p\in \{11,13,37\} $.

Представим число $ A_{} $ в виде $$A=10\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + {\mathfrak a}_{s+1}= 11\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + \left({\mathfrak a}_{s+1}- \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \right) . $$ Первое слагаемое в правой части делится на $ 11_{} $, поэтому для того чтобы $ A_{} $ делилось на $ 11_{} $, необходимо и достаточно, чтобы делилось на $ 11_{} $ число $$A_1 = {\mathfrak a}_{s+1} - \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \ .$$ Очевидно, что $ A_1<A $ и к этому новому числу мы можем применить тот же прием: $$A_1={\mathfrak a}_{s+1} -({\mathfrak a}_{s}-\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} +11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}) \ . $$ Число $ A_{} $ делится на $ 11_{} $ тогда и только тогда, когда делится на $ 11_{} $ число $$A_2= {\mathfrak a}_{s+1} -{\mathfrak a}_{s} + \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} \ . $$ С помощью интуиции и индукции получаем следующий критерий.

Теорема. Для того чтобы число $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $ делилось на $ 11_{} $, необходимо и достаточно, чтобы делилось на $ 11_{} $ число

$${\mathfrak a}_1-{\mathfrak a}_2 + {\mathfrak a}_3 - \dots +(-1)^{j-1}{\mathfrak a}_j +\dots + (-1)^{s-1}{\mathfrak a}_s+ (-1)^{s}{\mathfrak a}_{s+1} \ ,$$ т.е. разность между суммой цифр числа $ A_{} $, стоящих на нечетных местах, и суммой цифр, стоящих на четных местах.

Тот же прием срабатывает и для $ p=13 $: $$A= 13\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + \left({\mathfrak a}_{s+1}- 3\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \right) $$ и т.д.

Теорема. Для того чтобы число

$$ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $$ делилось на $ 13_{} $, необходимо и достаточно, чтобы делилось на $ 13_{} $ число

$$B= {\mathfrak a}_1\times 3^s-{\mathfrak a}_2 \times 3^{s-1} + \dots +(-1)^{j-1}{\mathfrak a}_j \times 3^{s-j+1} + \dots + $$ $$ +(-1)^{s-1}{\mathfrak a}_s \times 3 +(-1)^{s} {\mathfrak a}_{s+1} \ . $$

Пример. Делится ли число $ 1\,601\,197 $ на $ 13_{} $?

Решение. $$ 3^6-6\times 3^5+0\times 3^4-1\times 3^3+1\times 3^2-9\times 3+7 =-767 ,\ 7\times 3^2-6\times 3+7=52 \ .$$

Ответ. Делится.

Ситуация с числом $ 37_{} $ несколько сложнее. Можно попробовать оперировать с двузначными числами: $$A=100\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}+ \underline{{\mathfrak a}_s {\mathfrak a}_{s+1}}=3\times 37 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}+ (\underline{{\mathfrak a}_s {\mathfrak a}_{s+1}}-11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}) , $$ и связать делимость на $ 37_{} $ числа $ A_{} $ с делимостью числа $$B_1= \underline{{\mathfrak a}_s {\mathfrak a}_{s+1}} -11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} \ . $$ Однако более изящный результат получится, если посчастливилось подметить, что $ 1000=37\times 27+1 $. Разобьем десятичное представление числа $ A_{} $ на триплеты, начиная с конца: $$ A= \underline{{\mathfrak a}_{s-1}{\mathfrak a}_s {\mathfrak a}_{s+1}}+10^3\times \underline{{\mathfrak a}_{s-4}{\mathfrak a}_{s-3} {\mathfrak a}_{s-2}} +10^6\times \underline{{\mathfrak a}_{s-7}{\mathfrak a}_{s-6} {\mathfrak a}_{s-5}}+\dots $$

Теорема. Для того чтобы число

$$ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $$ делилось на $ 37_{} $, необходимо и достаточно, чтобы делилось на $ 37_{} $ число

$$B_2= \underline{{\mathfrak a}_{s-1}{\mathfrak a}_s {\mathfrak a}_{s+1}}+ \underline{{\mathfrak a}_{s-4}{\mathfrak a}_{s-3} {\mathfrak a}_{s-2}}+ \underline{{\mathfrak a}_{s-7}{\mathfrak a}_{s-6} {\mathfrak a}_{s-5}}+ \dots $$

Пример. Делится ли число $ 31\,222\,496\,509 $ на $ 37 $?

Решение. $ 509+496+222+31=1258 $, $ 258+1=259=37\times 7 $.

Ответ. Делится.

Можно ли применить использованный в настоящем пункте подход к решению более общей задачи: определить остаток от деления числа $ A_{} $ на заданное простое $ p_{} $?

Ответ оказывается положительным.

Теорема. Остаток от деления числа

$$ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $$ на $ 11_{} $ совпадает с остатком от деления на $ 11_{} $ числа

$$ {\mathfrak a}_{s+1}-{\mathfrak a}_s +{\mathfrak a}_{s-1}+\dots+ (-1)^{s-1} {\mathfrak a}_2+ (-1)^{s} {\mathfrak a}_1 \ . $$

Доказательство фактически повторяет доказательство критерия делимости. ♦

Пример. Остаток от деления числа $ 50298346974357 $ на $ 11_{} $ равен $ 9_{} $. Cумма его цифр с чередующимися знаками из теоремы:

$$ 7-5+3-4+7-9+6-4+3-8+9-2+0-5=-2 \ . $$ Согласно определению остатка: $ -2 $ при делении на $ 11 $ дает в остатке $ 9 $. ♦

Доказать, что число

$$ \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} \quad \mbox{ делится на } 11 $$ тогда и только тогда, когда число $$ \underline{{\mathfrak a}_s {\mathfrak a}_{s+1}}+\underline{{\mathfrak a}_{s-2} {\mathfrak a}_{s-1}}+\dots \quad \mbox{ делится на } 11 $$.

Критерий делимости числа на $ 7_{} $ ☞ ЗДЕСЬ

Как уже отмечалось в начале ☞ ПУНКТА, общий метод факторизации данного числа $ A_{} $ заключается в том, что $ A_{} $ пробуют делить последовательно на простые числа, не превосходящие $ \sqrt {A} $. Для некоторых классов чисел известны более быстрые способы факторизации, не требующие такого перебора. Например, число $ A=N^4-4 $ при $ N\in \mathbb N $ факторизуется очевидным способом; несколько труднее установить справедливость следующего результата.

[Софи Жермен] Доказать, что при $ N>1 $ число $ N^4+4 $ всегда составное.

Очевидно также, что любое число вида $ A=S^2-T^2 $ при $ \{S,T \}\subset \mathbb N $ всегда составное. Это утверждение допускает и обращение: если нечетное число $ A>0 $ — составное, т.е. $ A={\mathcal A}_1{\mathcal A}_2 $ и $ {\mathcal A}_1>{\mathcal A}_2 $, то его можно представить в виде разности двух квадратов целых чисел: $$ A=\left(\frac{{\mathcal A}_1+{\mathcal A}_2}{2} \right)^2 - \left(\frac{{\mathcal A}_1-{\mathcal A}_2}{2} \right)^2 \ . $$ Этот факт, замеченный еще Ферма, можно развить до следующего критерия.

Теорема. Пусть число $ A\ge 9 $ нечетно. Рассмотрим последовательность натуральных чисел

$$ A_0 = A, \ A_1=A_0+1,\ A_2=A_1+3,\ \dots,\ $$ $$ A_n = A_{n-1}+(2n-1) \quad npu \quad 1\le n \le \left\lfloor \frac{A-9}{6} \right\rfloor \ . $$ Число $ A_{} $ будет составным тогда и только тогда, когда среди этих чисел имеется полный квадрат: $ \exists t\in \mathbb N $ такое, что $ A_j=t^2 $. В этом случае $$ A=(t-j)(t+j) \ . $$

Доказательство. Очевидно, $$A_1=A+1,\ A_2=A+1+3=A+4,\ A_3=A+1+3+5=A+9,\dots, $$ $$ A_j=A+\left[1+3+\cdots +(2j-1) \right]=A+j^2 \ .$$

Достаточность. Пусть $ A_j=t^2 $, тогда $ A=(t-j)(t+j) $. Покажем, что при ограничении из условия теоремы: $ j \le \left\lfloor (A-9)/6 \right\rfloor $ будет выполнено $ t-j>1 $, т.е. $ A_{} $ раскладывается на два нетривиальных множителя. Имеем $$j\le \left\lfloor (A-9)/6 \right\rfloor \ \Rightarrow A\ge 6j+9>2j+1 \ .$$ Используем эту оценку в равенстве $ t^2=A+j^2 $: $ t^2>j^2+2j+1=(j+1)^2 $, т.е. $ t>j+1 $.

Необходимость. Если число $ A_{} $ — нечетное составное: $ A={\mathcal A}_1{\mathcal A}_2 $, то имеет место представление $ A=\left( ({\mathcal A}_1+{\mathcal A}_2)/2 \right)^2 - \left( ({\mathcal A}_1-{\mathcal A}_2)/2 \right)^2 $, которое соответствует формуле $ A=(t-j)(t+j) $ при $ t=1/2 ({\mathcal A}_1+{\mathcal A}_2) $, $ j=1/2({\mathcal A}_1-{\mathcal A}_2) $. Покажем, что найденное значение для $ j_{} $ удовлетворяет неравенству из условия теоремы.

Если $ {\mathcal A}_1>{\mathcal A}_2 $, то $$3\le {\mathcal A}_2 \le \sqrt{A} \le {\mathcal A}_1 \le \frac{A}{3}\ \Rightarrow \ {\mathcal A}_1 -{\mathcal A}_2 \le \frac{A}{3} -3 \ \Rightarrow \ 0 \le j \le \frac{A/3 -3}{2} \ , $$ т.е. целое число $ j_{} $ удовлетворяет ограничению $ j \le \left\lfloor (A-9)/6 \right\rfloor $. ♦

Пример. Факторизовать число $ A=792019 $.

Решение. Заметим, что число, составляющее полный квадрат, не может оканчиваться на $ 2,3,7 $ или $ 8_{} $; если оканчивается на $ 5_{} $, то должно оканчиваться на $ 25_{} $; если оканчивается на $ 0_{} $, то должно оканчиваться на $ 00_{} $. Эти тривиальные соображения позволяют сразу же отбросить из рассмотрения первые числа последовательности $ \{A_j\} $: $$ A_1=792020,\ A_2=792023,\ A_3=792028, A_4=792035 \ .$$ Далее, $ A_5=792044=2^2\cdot 198011 $, и число $ 198011 $ не может быть полным квадратом, так как не существует двузначного числа, квадрат которого оканчивается на $ 11_{} $. Числа $ A_6=792055,\ A_7=792068,\ A_8=792083 $ не могут быть квадратами. Число $ A_9=792100=890^2 $. Согласно теореме : $ j=9,t=890 $ и $ A=881\times 899 $. К числу $ 899 $ снова применяем теорему. Удача ожидает нас уже на первом шаге: $ 899+1=30^2 $ и, следовательно, $ 899=29\times 31 $. С числом $ 881 $ дело обстоит не так хорошо: забегая вперед, скажем, что оно — простое. Если бы мы организовали проверку этого факта по теореме, то нам пришлось бы анализировать на равенство полному квадрату $ \lfloor (881-9)/6 \rfloor = 145 $ чисел. Понятно, что проще было бы установить факт простоты последовательным перебором возможных простых делителей в пределах до $ \sqrt{881}<30 $. ♦

Регулярный метод проверки числа на равенство полному квадрату, а также вычисления $ \lfloor \sqrt{A} \rfloor $ ☞ ЗДЕСЬ.

Функция Эйлера (или тотиент) натурального числа $ A_{} $ обозначается $ \phi (A) $ и представляет собой количество чисел ряда $$ 0,1, \dots, A-1 \ , $$ взаимно простых c $ A_{} $.

Пример.

$$ \phi (1)=1, \, \phi (2)=1, \, \phi (3)=2, \, \phi (4)=2, \, \phi (5)=4, \, \phi (6)=2, \phi (7)=6 ,\, $$ $$ \phi (8)=4 , \, \phi (12)=4 \, . $$

Очевидно, что для простого $ p_{} $ будет: $ \phi (p)=p-1 $. В общем же случае имеет место следующий результат.

Теорема [Эйлер]. Если

$$ A= p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} $$ — каноническое разложение числа $ A_{} $, то $$ \begin{array}{rcl} \phi (A) &=& A \displaystyle \left( 1-\frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \times \dots \times \left( 1-\frac{1}{p_{\mathfrak r}} \right)= \\ &=& \left( p_1^{{\mathfrak m}_{_1}}-p_1^{{\mathfrak m}_{_1}-1} \right) \left(p_2^{{\mathfrak m}_{_2}}- p_2^{{\mathfrak m}_{_2}-1} \right)\times \dots \times \left( p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}}-p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}-1} \right) \ . \end{array} $$

Пример.

$$ \phi (60) = 60\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{3}\right) \left( 1-\frac{1}{5} \right)=16 , $$ $$ \phi (81)=81-27=54 , \quad \phi (481) = 432 \ . $$

Если числа $ A_1,\dots ,A_K $ попарно взаимно просты, то

$$\phi (A_1A_2\times \dots \times A_K)=\phi (A_1) \phi (A_2) \times \dots \times \phi (A_K) \ ;$$ в частности, если числа $ p_1,p_2,\dots,p_{\mathfrak r} $ — различные простые, то $$ \phi (p_1p_2\times \dots \times p_{\mathfrak r})=(p_1-1)(p_2-1)\times \dots \times (p_{\mathfrak r}-1) \ . $$

$ \phi(A^m)=A^{m-1}\phi(A) $.

Пусть $ N \in \mathbb N $. Определить вероятность того, что число, случайным образом выбранное из множества $ \{1,2,\dots,N\} $, будет взаимно просто с $ N_{} $.

Еще пара результатов для функции Эйлера, не совсем тривиально доказываемых.

Теорема. $ \displaystyle \sum_{d} \phi(d) = n $; здесь суммирование производится по всем числам $ d_{} $, являющимся делителями числа $ n_{} $.

Доказательство ☞ ЗДЕСЬ.

Пример. Для $ n=30 $ имеем:

$$ \phi(1)+\phi(2)+\phi(3)+\phi(5)+\phi(6)+\phi(10)+\phi(15)+\phi(30)= $$ $$ =1+1+2+4+2+4+8+8=30 \ . $$

Теорема. Для любого $ A_{} $ и $ m_{}>1 $ число $ \phi (A^m-1) $ делится на $ m_{} $.

Доказательство ☞ ЗДЕСЬ.

Раздел ☞ ЗДЕСЬ.

☞ ЗДЕСЬ.

[1]. Бухштаб А.А. Теория чисел. М. Просвещение. 1966

[2]. Honsberger R. Mathematical Gems II. Mathematical Assn. of Amer. 1976

[3]. Чебышев П. Теорiя сравненiй. СПб. Типографiя Императорской Академiи Наукъ. 1901