Как найти линейную форму нод

Содержание

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

Зачем нужен такой занудный формализм? См. последний пример

☞

ПУНКТА.

Т

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

$$
B=Aq+r, , quad npu {q,r} subset mathbb Z u quad 0le 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 , 0le 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 npu {q,r} subset mathbb Z u quad 0le r<A
$$
число $ q_{} $ называется частным,
а $ r_{} $ — остатком¹⁾
от деления $ B_{} $ на $ A_{} $.
Если $ r=0_{} $, то говорят, что число $ B_{} $ делится нацело на $ A_{} $ или что $ B_{} $ кратно $ A_{} $, а число $ A_{} $ называется делителем $ B_{} $. Тривиальными делителями
числа $ Ane 0 $ называют $ 1_{} $ и само число $ A_{} $.

Для обозначения факта делимости $ B_{} $ на $ A_{} $ используют обозначение $ A | B $ (в смысле, что число $ A_{} $ является делителем числа $ B_{} $). Мне это обозначение кажется неудобным и больше нравится $ B vdots 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_1in 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_1in mathbb N big| A_j mbox{ делится на } d_1,
forall jin{1,dots,K } big} .$$
Наименьшим общим кратным отличных от нуля чисел $ A_1,dots,A_K $
называют наименьшее положительное число, кратное всем этим числам
$$ operatorname{HOK} (A_1,dots,A_K)=min big{d_1in mathbb N big| d_1 mbox{ делится на } A_j,
forall jin{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_1ne 0 $: $ 0<r_1<A $. Поделим делитель на
этот остаток: $ A=r_1q_2+r_2 $, предположим, что остаток $ r_2ne 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}
$$
для всех $ jin {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 $ при
$ jin {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 jge 2,
$$
называются континуантами. Иногда то обстоятельство, что $ K_{j} $ зависит от $ x_1,dots,x_j $ подчеркивают, записывая континуанту в виде $ K_j(x_1,dots,x_j) $.

Континуанта является примером рекуррентной последовательности, задаваемой линейным однородным разностным уравнением с переменными коэффициентами. То, что континуанта определяется как число — не существенно; можно говорить о $ K_j(x_1,dots,x_j) $ как о полиноме от $ x_1,dots,x_{j} $.

Т

Теорема. Величина континуанты $ K_j(x_1,dots,x_j) $
равна сумме произведения $ x_1cdot 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 $.

Проверка. $ 17times 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 tin mathbb Z $ пара $ tilde{tilde u}=tilde u+tB,tilde{tilde v}
=tilde v-tA $ также
является решением. Можно, например, подобрать число $ t_{} $ так, чтобы было
выполнено $ 0le 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_1times 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_2Bright) B = 1 . $$
По теореме $ 1 $, числа $ A_1A_2 $ и $ B_{} $ взаимно простые.

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

♦

Т

Теорема 3. Если произведение $ Acdot 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_1times dots times C_K $.

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

♦

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

Т

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

$$ lim_{Nto infty} P_N = frac{6}{pi^2} approx 0.607927 . $$

Доказательство (набросок)

☞

ЗДЕСЬ.

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

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

primus (лат.) — первый;
Евклид называл простое число $ pirhotilde{omega}tau{rm o}varsigma alpharhoiotavarthetamu {rm o} varsigma $, т.е. «первым числом». Еще в учебниках XIX века взаимно простые числа назывались «числами первыми между собой», а простые числа — «первоначальными».

Т

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

Доказательство проводится от противного. Предположим, что существует
конечное число простых чисел и наибольшее из них равно $ p_{} $. Если мы
рассмотрим все эти простые числа $ 2,3,5,7,11,dots, p $, то всякое
число $ A_{} $, большее $ p_{} $, должно быть составным и должно делиться по крайней
мере на одно из этих простых чисел. Однако число
$ A=2cdot 3 cdot 5times 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} $.

A

Анимационная схема работы решета

☞

ЗДЕСЬ

Таблица первых $ 500_{} $ простых чисел

☞

ЗДЕСЬ

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

Т

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

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

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

Общей закономерности в распределении простых чисел среди всего ряда натуральных чисел не установлено,
несмотря на то, что этой проблемой математика занимается уже более 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 $$
будут простыми при $ nin {1,2,3,4,13,14,dots } $, но составными при $ nin {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} $$
при $ nin {1,dots, N } $, где $ Nin { 10^2,10^3,10^6 } $.

§

Геометрию последовательностей вида $ left{n^2-n+a right} $ при $ ain 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 $ называются числами Мерсенна.

Значение математических работ Марена Мерсенна (Mersenne Marin, 1588-1648) сравнительно невелико, но его роль как организатора европейской науки Нового времени огромна, см.

☞

ЗДЕСЬ.

§

Критерии простоты числа $ 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^3cdot 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| , 0le ell_1 le {mathfrak m}_1, 0le ell_2 le {mathfrak m}_2, dots ,
0le 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^3cdot 3^5cdot 7^2cdot 211,
2^2cdot 3^2cdot 5^2cdot 11, 2cdot 3^2cdot 5cdot 41)=2cdot 3^2=18 ;
$$
$$operatorname{HOK} (20099016,, 9900,, 3690) =2^3cdot 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) = Acdot B . $$

?

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

Ответ

☞

ЗДЕСЬ.

Т

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

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

?

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

$$ leftlfloor frac{n}{p^2}rightrfloor = leftlfloor frac{leftlfloor frac{n}{p}rightrfloor }{p} rightrfloor .
$$

П

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

Решение. Вопрос равнозначен поиску максимального $ Kin mathbb N $ такого, что
$ 153! $ делится на $ 10^K=2^Kcdot 5^K $. Очевидно, что в каноническом разложении
$ n!_{} $ показатель двойки будет больше показателя любого другого простого числа, и
для ответа на наш вопрос достаточно подсчитать показатель пятерки.
$$leftlfloorfrac{153}{5}rightrfloor +leftlfloorfrac{153}{25}rightrfloor+
leftlfloorfrac{153}{125}rightrfloor=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}_1times 10^s+{mathfrak a}_2 times 10^{s-1} + dots +{mathfrak a}_s times
10 + {mathfrak a}_{s+1}
$$
можно установить, делится или не делится $ A_{} $ на $ p_{} $. Такие признаки можно
установить и для других простых чисел. Проиллюстрируем на примерах $ pin {11,13,37} $.

Представим число $ A_{} $ в виде
$$A=10times underline{{mathfrak a}_1{mathfrak a}_2 dots {mathfrak a}_s} + {mathfrak a}_{s+1}=
11times 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=
13times underline{{mathfrak a}_1{mathfrak a}_2 dots {mathfrak a}_s} +
left({mathfrak a}_{s+1}- 3times 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}_1times 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-6times 3^5+0times 3^4-1times 3^3+1times 3^2-9times 3+7
=-767 , 7times 3^2-6times 3+7=52 .$$

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

Ситуация с числом $ 37_{} $ несколько сложнее. Можно попробовать оперировать с
двузначными числами:
$$A=100times
underline{{mathfrak a}_1{mathfrak a}_2 dots {mathfrak a}_{s-1}}+
underline{{mathfrak a}_s {mathfrak a}_{s+1}}=3times 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=37times 27+1 $. Разобьем десятичное представление числа $ A_{} $ на триплеты,
начиная с конца:
$$
A=
underline{{mathfrak a}_{s-1}{mathfrak a}_s {mathfrak a}_{s+1}}+10^3times
underline{{mathfrak a}_{s-4}{mathfrak a}_{s-3} {mathfrak a}_{s-2}}
+10^6times
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=37times 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 $ при $ Nin 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 .
$$
Этот факт, замеченный еще Ферма, можно развить до следующего критерия.

Т

Теорема. Пусть число $ Age 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 1le n le
leftlfloor
frac{A-9}{6} rightrfloor .
$$
Число $ A_{} $ будет составным тогда и только тогда, когда среди этих чисел имеется
полный квадрат: $ exists tin 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 leftlfloor (A-9)/6 rightrfloor $
будет выполнено $ t-j>1 $, т.е. $ A_{} $ раскладывается на два нетривиальных
множителя. Имеем
$$jle leftlfloor (A-9)/6 rightrfloor Rightarrow
Age 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 $, то
$$3le {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 leftlfloor (A-9)/6 rightrfloor $.

♦

П

Пример. Факторизовать число $ 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^2cdot 198011 $, и число $ 198011 $ не может быть полным квадратом,
так как не существует двузначного числа, квадрат которого оканчивается на $ 11_{} $.
Числа $ A_6=792055, A_7=792068, A_8=792083 $ не могут быть квадратами.
Число $ A_9=792100=890^2 $. Согласно теореме : $ j=9,t=890 $ и
$ A=881times 899 $. К числу $ 899 $ снова применяем теорему.
Удача ожидает нас уже на первом шаге: $ 899+1=30^2 $ и,
следовательно, $ 899=29times 31 $. С числом $ 881 $ дело обстоит не так хорошо:
забегая вперед, скажем, что оно — простое. Если бы мы организовали
проверку этого факта по теореме, то нам пришлось бы анализировать
на равенство полному квадрату $ lfloor (881-9)/6 rfloor = 145 $ чисел.
Понятно, что проще было бы установить факт простоты последовательным перебором возможных
простых делителей в пределах до $ sqrt{881}<30 $.

♦

§

Регулярный метод проверки числа на равенство полному квадрату, а также вычисления
$ lfloor sqrt{A} rfloor $

☞

ЗДЕСЬ.

Метод факторизации из теоремы эффективен, если факторизуемое число близко к полному квадрату, т.е. раскладывается на два сомножителя $ {mathcal A}_1 $ и $ {mathcal A}_2 $, близких по величине.
Фактически в этом случае удается свести задачу факторизации к задаче проверки нового числа на равенство полному квадрату и до положительного ответа удается дойти за небольшое количество шагов (итераций) $ j_{} $. Если же факторизуемое число далеко от полного квадрата,
то алгоритм может работать достаточно долго.
Например, для определения хотя бы
одного множителя числа $ 71299=37cdot 41 cdot 47 $ требуется проверить на равенство полному
квадрату $ 735 $ чисел последовательности из теоремы; в этом примере оказывается легче установить
простой множитель просеиванием сквозь решето Эратосфена.

Существуют другие методы факторизации, основанные на иных предположениях о структуре сомножителей числа $ A_{} $. Так, например, если $ A=p_1p_2 $, где $ p_1 $ и $ p_2 $ — различные простые числа, и при этом каноническое разложение хотя бы одного из $ p_j-1 $ имеет только небольшие простые сомножители, то факторизовать число $ A_{} $ эффективно возможно по алгоритму факторизации Полларда.

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

Имеется расхождение в определении функции Эйлера в различных учебниках. В некоторых из них число $ 0_{} $ не включается в состав рассматриваемого ряда чисел. С вычислительной точки зрения, это абсолютно правильно, поскольку $ 0_{} $ не является взаимно простым с любым числом $ A_{} >1 $, и поэтому его включение или невключение в рассматриваемый ряд неотрицательных чисел, меньших $ A_{} $, совершенно не влияет на значение $ phi (A) $. Тем не менее в различных применениях функции Эйлера приходится иметь дело именно с рядом неотрицательных чисел, меньших числа $ A_{} $, но включающих и $ 0_{} $. Для согласования результатов формально будем включать $ 0_{} $ в определение функции Эйлера.

П

Пример.

$$ 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) =
60left( 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_2times 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_2times 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

Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:

a=b·q1+r1, 0<r1<bb=r1·q2+r2, 0<r2<r1r1=r2·q3+r3, 0<r3<r2r2=r3·q4+r4, 0<r4<r3⋮rk-2=rk-1·qk+rk, 0<rk<rk-1rk-1=rk·qk+1

Первое равенство говорит нам о том, что r1=a−b·q1_. Обозначим 1=s1 и −q1=t1 и перепишем данное равенство в виде r1=s1·a+t1·b. Здесь числа s1 и t1 будут целыми. Второе равенство позволяет сделать вывод, что r2=b−r1·q2=b−(s1·a+t1·b) ·q2=−s1·q2·a+(1−t1·q2) ·b. Обозначим −s1·q2=s2 и 1−t1·q2=t2 и перепишем равенство как r2=s2·a+t2·b, где s2 и t2 также будут целыми. Это объясняется тем, что сумма целых чисел, их произведение и разность также представляют собой целые числа. Точно таким же образом получаем из третьего равенства r3=s3·a+t3·b, из следующего r4=s4·a+t4·b и т.д. В конце заключаем, что rk=sk·a+tk·b при целых sk и tk. Поскольку rk=НОД (a, b), обозначим sk=u0 и tk=v0, В итоге мы можем получить линейное представление НОД в требуемом виде: НОД (a, b) =a·u0+b·v0.