Содержание
Начала теории целых чисел
Делимость с остатком
Прежде чем излагать новый материал, необходимо договориться о терминологии.
Понятие остатка от деления
положительного целого числа $ 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_{} $ — остатком1)
от деления $ 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 $. Снова разделим делитель на остаток и продолжим процесс далее
до тех пор, пока на каком-то шаге не произойдет деление нацело, т.е.
остаток будет равен нулю2). Запишем процедуру в виде схемы:
$$
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_{} $,
через3) $ 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 $$
На рисунке виден сравнительный рост количества простых чисел
П.Л.Чебышевым были получены и более тесные границы:
$$ 0.921 frac{N}{ln N} < pi(N) < 1.106 frac{N}{ln N} ; $$
обе приведенные оценки имеют следствием:
$$
lim_{Nto infty} frac{pi(N)}N= 0 ;
$$
что означает: вероятность того, что случайно выбранное число множества $ {1,2,dots,N } $ окажется простым, стремится к нулю при неограниченном росте $ N_{} $.
Общей закономерности в распределении простых чисел среди всего ряда натуральных чисел не установлено,
несмотря на то, что этой проблемой математика занимается уже более 2000 лет.
Существуют пары простых чисел с минимальным расстоянием друг от друга:
$$ (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), dots ; $$
их называют близнецами4). С другой стороны, существуют сколь угодно длинные отрезки натурального ряда, свободные от простых чисел:
Т
Теорема. Для любого натурального $ 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_{} $ на сомножители, а сам
процесс нахождения канонического разложения — факторизацией5)
числа $ 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) $.
Теорема Эйлера является частным случаем следующего, более общего результата,
известного как формула включений-исключений.
Теорема. Пусть даны подмножества6) $ A_1,A_2,dots,A_{mathfrak r} $ некоторого конечного множества. Тогда для мощности (числа элементов) их объединения
справедлива формула включений-исключений:
$$ operatorname{Card}(A_1 cup A_2 cup dots cup A_{mathfrak r}) = $$
$$ =sum_{j=1}^{mathfrak r} operatorname{Card}(A_j) – sum_{1le j_1 < j_2 le mathfrak r} operatorname{Card}(A_{j_1} cap A_{j_2}) +
$$
$$
+sum_{1le j_1 < j_2 < j_3 le mathfrak r} operatorname{Card}(A_{j_1} cap A_{j_2} cap A_{j_3}) – dots +
$$
$$
+ (-1)^{mathfrak r-1} operatorname{Card}(A_1 cap A_2 cap dots cap A_{mathfrak r}) . $$
Доказательство
☞
ЗДЕСЬ.
?
Пусть $ 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
2.1. Наибольший общий делитель.
2.1.1.
Определение.
Число a
называется общим
делителем чисел
a1,
a2,
…, ak,
если a
делит каждое из них. Наибольший из общих
делителей чисел называется их наибольшим
общим делителем.
Наибольший
общий делитель чисел a1,
a2,
…, ak
обозначается через (a1,
a2,
…, ak)
или НОД(a1,
a2,
…, ak).
Так
1 делит каждое из чисел a1,
a2,
…, ak
и из a
| ai
следует, что a|ai|
либо ai=0,
то (a1,
a2,
…, ak)
существует.
2.1.2.
Упражнение.
Найти наибольший общий делитель чисел:
а) 60 и 100;
б) 60, 100 и 125;
в) 24, 60, 100 и 125.
Решение.
б) Положительные общие делители чисел
60, 100 и 125
это 1 и 5. Поэтому (60, 100, 125)=5.
2.1.3.
Теорема.
Справедливы
следующие свойства
(a,
b):
1o.
Если
b
| a,
то множество
общих делителей чисел a
и b
совпадает с множеством делителей
b.
В частности,
(a,
b)=b.
2o.
Если
a=bq+c,
то множество
общих делителей чисел a
и b
совпадает с множеством общих делителей
чисел b
и c.
В частности,
(a,
b)=(b,
c).
3o.
Пусть дана
последовательность равенств,
которые
получаются при делении с остатком:
a=bq1+r1,
0r1<|b|,
b=r1q2+r2,
0r2<r1,
r1=r2q3+r3,
0r3<r2,
(2.1.1)
…………………..
rn2=rn1qn+rn,
0rn<rn1,
rn1=rnqn+1.
Тогда
(a,
b)=rn.
4o.
(a,b)делится на любой общий делитель чиселaиbи,обратно,любой общий делитель
числа(a,b)является общим делителем чиселaиb.
5o.
(am,bm)=(a,b)m.В частности,=1.
Равенства
(2.1.1) дают практический способ нахождения
(a,b).
Этот способ называетсяалгоритмом
Евклида.
2.1.4.
Упражнение.
Используя алгоритм Евклида, найти
наибольший общий делитель чисел:
а) 391 и 713;
б) 1641 и 1457;
в)
3731 и 4633;
г) 6188 и 4709;
д) 9817 и 10561.
Решение.
в) Разделим с остатком 4633 на 3731:
-
_4633
3731
3731
1
902
то есть
4633=37311+902.
Теперь с остатком
разделим 3731 на 902:
-
_3731
902
3608
4
123
то
есть 3731=9024+123.
Делим 902 на 123 с
остатком:
-
_902
123
861
7
41
то
есть 902=1237+41.
Наконец,
-
_123
41
123
3
0
Таким образом,
НОД(4633, 3731)=41.
2.1.5.
Упражнение. Найти
наибольший общий делитель чисел (nN):
а)
2n+13
и n+7;
б)
27n+4
и 18n+3.
Решение.
а) Выпишем равенства деления с остатком:
2n+13=(n+7)+(n+6)
(n+6
— остаток от деления 2n+13
на n+7),
n+7=(n+6)+1.
Очевидно,
1 — последний ненулевой остаток.
Следовательно, НОД(2n+13,
n+7)=1.
2.2. Линейное представление нод.
2.2.1.
Теорема.
Пусть
d=(a,
b).
Существуют
такие целые числа u
и v,
что
ua+vb=d.
(2.2.1)
2.2.2.
Упражнение.
Найти линейное представление НОД чисел
упражнения 2.1.4.
Решение.
в) Выпишем
равенства (2.1.1) алгоритма Евклида для
чисел 3731 и 4633:
4633=37311+902,
3731=9024+123,
902=1237+41,
Из последнего
равенства выражаем 41 через 123 и 902:
41=9021237. (2.2.2)
Из
предпоследнего равенства выражаем 123
через 902 и 3731 и подставляем это выражение
в (2.2.2): 41=902(37319024)7=37317+90229,
то есть
41=37317+90229.
(2.2.3)
Наконец,
выражая 902 через 3731 и 4633, и, подставляя
в (2.2.3), получаем
41=37317+(46333731)29=463329373136,
то есть
41=294633363731.
Ответ:
в) 41=294633363731.
Эта статья посвящена такому вопросу, как нахождение наибольшего общего делителя. Сначала мы объясним, что это такое, и приведем несколько примеров, введем определения наибольшего общего делителя 2, 3 и более чисел, после чего остановимся на общих свойствах данного понятия и докажем их.
Что такое общие делители
Чтобы понять, что из себя представляет наибольший общий делитель, сначала сформулируем, что вообще такое общий делитель для целых чисел.
В статье о кратных и делителях мы говорили, что у целого числа всегда есть несколько делителей. Здесь же нас интересуют делители сразу некоторого количества целых чисел, особенно общие (одинаковые) для всех. Запишем основное определение.
Общим делителем нескольких целых чисел будет такое число, которое может быть делителем каждого числа из указанного множества.
Вот примеры такого делителя: тройка будет общим делителем для чисел -12 и 9, поскольку верны равенства 9=3·3 и −12=3·(−4). У чисел 3 и -12 есть и другие общие делители, такие, как 1, −1 и −3. Возьмем другой пример. У четырех целых чисел 3, −11, −8 и 19 будет два общих делителя: 1 и -1.
Зная свойства делимости, мы можем утверждать, что любое целое число можно разделить на единицу и минус единицу, значит, у любого набора целых чисел уже будет как минимум два общих делителя.
Также отметим, что если у нас есть общий для нескольких чисел делитель b, то те же числа можно разделить и на противоположное число, то есть на -b. В принципе, мы можем взять лишь положительные делители, тогда все общие делители также будут больше 0. Такой подход также можно использовать, однако совсем игнорировать отрицательные числа не следует.
Что такое наибольший общий делитель (НОД)
Согласно свойствам делимости, если b является делителем целого числа a, которое не равно 0, то модуль числа b не может быть больше, чем модуль a, следовательно, любое число, не равное 0, имеет конечное число делителей. Значит, число общих делителей нескольких целых чисел, хотя бы одно из которых отличается от нуля, также будет конечным, и из всего их множества мы всегда можем выделить самое большое число (ранее мы уже говорили о понятии наибольшего и наименьшего целого числа, советуем вам повторить данный материал).
В дальнейших рассуждениях мы будем считать, что хотя бы одно из множества чисел, для которых нужно найти наибольший общий делитель, будет отлично от 0. Если они все равны 0, то их делителем может быть любое целое число, а поскольку их бесконечно много, выбрать наибольшее мы не сможем. Иначе говоря, найти наибольший общий делитель для множества чисел, равных 0, нельзя.
Переходим к формулировке основного определения.
Наибольшим общим делителем нескольких чисел является самое большое целое число, которое делит все эти числа.
На письме наибольший общий делитель чаще всего обозначается аббревиатурой НОД. Для двух чисел его можно записать как НОД (a, b).
Какой можно привести пример НОД для двух целых чисел? Например, для 6 и -15 это будет 3. Обоснуем это. Сначала запишем все делители шести: ±6, ±3, ±1, а потом все делители пятнадцати: ±15, ±5, ±3 и ±1. После этого мы выбираем общие: это −3, −1, 1 и 3. Из них надо выбрать самое большое число. Это и будет 3.
Для трех и более чисел определение наибольшего общего делителя будет почти таким же.
Наибольшим общим делителем трех чисел и более будет самое большое целое число, которое будет делить все эти числа одновременно.
Для чисел a1, a2, …, an делитель удобно обозначать как НОД (a1, a2, …, an). Само значение делителя записывается как НОД (a1, a2, …, an) =b.
Приведем примеры наибольшего общего делителя нескольких целых чисел: 12, -8, 52, 16. Он будет равен четырем, значит, мы можем записать, что НОД (12, -8, 52, 16) =4.
Проверить правильность данного утверждения можно с помощью записи всех делителей этих чисел и последующего выбора наибольшего из них.
На практике часто встречаются случаи, когда наибольший общий делитель равен одному из чисел. Это происходит тогда, когда на данное число можно разделить все остальные числа (в первом пункте статьи мы привели доказательство этого утверждения).
Так, наибольший общий делитель чисел 60, 15 и -45 равен 15, поскольку пятнадцать делится не только на 60 и -45, но и на само себя, и большего делителя для всех этих чисел не существует.
Особый случай составляют взаимно простые числа. Они представляют собой целые числа с наибольшим общим делителем, равным 1.
Основные свойства НОД и алгоритм Евклида
У наибольшего общего делителя есть некоторые характерные свойства. Сформулируем их в виде теорем и докажем каждое из них.
Отметим, что данные свойства сформулированы для целых чисел больше нуля, а делители мы рассмотрим только положительные.
Числа a и b имеют наибольший общий делитель, равный НОД для b и a, то есть НОД (a, b)=НОД (b, a). Перемена мест чисел не влияет на конечный результат.
Данное свойство следует из самого определения НОД и не нуждается в доказательствах.
Если число a можно разделить на число b, то множество общих делителей этих двух чисел будет аналогично множеству делителей числа b, то есть НОД (a, b)=b.
Докажем это утверждение.
Если у чисел a и b есть общие делители, то на них можно разделить любое из них. В то же время если a будет кратным b, то любой делитель b будет делителем и для a, поскольку у делимости есть такое свойство, как транзитивность. Значит, любой делитель b будет общим для чисел a и b. Это доказывает, что если мы можем разделить a на b, то множество всех делителей обоих чисел совпадет с множеством делителей одного числа b. А поскольку наибольший делитель любого числа есть само это число, то наибольший общий делитель чисел a и b будет также равен b, т.е. НОД (a, b)=b. Если a=b, то НОД (a, b)=НОД (a, a)=НОД (b, b) =a=b, например, НОД (132, 132) =132.
Используя это свойство, мы можем найти наибольший общий делитель двух чисел, если одно из них можно разделить на другое. Такой делитель равен одному из этих двух чисел, на которое можно разделить второе число. К примеру, НОД (8, 24) =8, так как 24 есть число, кратное восьми.
Если верно равенство a=b·q+c (здесь все переменные являются целыми числами), то все общие делители двух чисел a и b будут такими же, как и у чисел b и c, то есть НОД (a, b)=НОД (b, c).
Попробуем доказать данное свойство. У нас изначально есть равенство a=b·q+c, и любой общий делитель a и b будет делить и c, что объясняется соответствующим свойством делимости. Поэтому любой общий делитель b и c будет делить a. Значит, множество общих делителей a и b совпадет с множеством делителей b и c, в том числе и наибольшие из них, значит, равенство НОД (a, b)=НОД (b, c) справедливо.
Следующее свойство получило название алгоритма Евклида. С его помощью можно вычислить наибольший общий делитель двух чисел, а также доказать другие свойства НОД.
Перед тем, как сформулировать свойство, советуем вам повторить теорему, которую мы доказывали в статье о делении с остатком. Согласно ей, делимое число a можно представить в виде b·q+r, причем b здесь является делителем, q – некоторым целым числом (его также называют неполным частным), а r – остатком, который удовлетворяет условию 0≤r≤b.
Допустим, у нас есть два целых числа больше 0, для которых будут справедливы следующие равенства:
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
Эти равенства заканчиваются тогда, когда rk+1 становится равен 0. Это случится обязательно, поскольку последовательность b> r1> r2> r3, … представляет собой ряд убывающих целых чисел, который может включать в себя только конечное их количество. Значит, rk является наибольшим общим делителем a и b, то есть, rk=НОД (a, b).
В первую очередь нам надо доказать, что rk – это общий делитель чисел a и b, а после этого – то, что rk является не просто делителем, а именно наибольшим общим делителем двух данных чисел.
Просмотрим список равенств, приведенный выше, снизу вверх. Согласно последнему равенству,
rk−1 можно разделить на rk. Исходя из этого факта, а также предыдущего доказанного свойства наибольшего общего делителя, можно утверждать, что rk−2 можно разделить на rk, так как
rk−1 делится на rk и rk делится на rk.
Третье снизу равенство позволяет нам сделать вывод, что rk−3 можно разделить на rk, и т.д. Второе снизу – что b делится на rk, а первое – что a делится на rk. Из всего этого заключаем, что rk – общий делитель a и b.
Теперь докажем, что rk=НОД (a, b). Что для этого нужно сделать? Показать, что любой общий делитель a и b будет делить rk. Обозначим его r0.
Просмотрим тот же список равенств, но уже сверху вниз. Исходя из предыдущего свойства, можно заключить, что r1 делится на r0, значит, согласно второму равенству r2 делится на r0. Идем по всем равенствам вниз и из последнего делаем вывод, что rk делится на r0. Следовательно, rk=НОД (a, b).
Рассмотрев данное свойство, заключаем, что множество общих делителей a и b аналогично множеству делителей НОД этих чисел. Это утверждение, которое является следствием из алгоритма Евклида, позволит нам вычислить все общие делители двух заданных чисел.
Перейдем к другим свойствам.
Если a и b являются целыми числами, не равными 0, то должны существовать два других целых числа u0 и v0, при которых будет справедливым равенство НОД (a, b) =a·u0+b·v0.
Равенство, приведенное в формулировке свойства, является линейным представлением наибольшего общего делителя a и b. Оно носит название соотношения Безу, а числа u0 и v0 называются коэффициентами Безу.
Докажем данное свойство. Запишем последовательность равенств по алгоритму Евклида:
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.
НОД (m·a, m·b) =m·НОД(a, b) при любом натуральном значении m.
Обосновать это свойство можно так. Умножим на число m обе стороны каждого равенства в алгоритме Евклида и получим, что НОД (m·a, m·b) =m·rk, а rk – это НОД (a, b). Значит, НОД (m·a, m·b) =m·НОД(a, b). Именно это свойство наибольшего общего делителя используется при нахождении НОД методом разложения на простые множители.
Если у чисел a и b есть общий делитель p, то НОД (a:p, b:p)=НОД(a, b):p. В случае, когда p=НОД (a, b) получим НОД (a:НОД(a, b), b:НОД (a, b)=1, следовательно, числа a:НОД(a, b) и b:НОД (a, b) являются взаимно простыми.
Поскольку a=p·(a:p) и b=p·(b:p), то, основываясь на предыдущем свойстве, можно создать равенства вида НОД(a, b)=НОД(p·(a:p), p·(b:p))=p·НОД(a:p, b:p), среди которых и будет доказательство данного свойства. Это утверждение мы используем, когда приводим обыкновенные дроби к несократимому виду.
Наибольшим общим делителем a1, a2, …, ak будет число dk, которое можно найти, последовательно вычисляя НОД (a1, a2)=d2, НОД (d2, a3) =d3, НОД (d3, a4) =d4, …, НОД (dk-1, ak) =dk.
Это свойство полезно при нахождении наибольшего общего делителя трех и более чисел. С помощью него можно свести это действие к операциям с двумя числами. Его основой является следствие из алгоритма Евклида: если множество общих делителей a1, a2 и a3 совпадает с множеством d2 и a3, то оно совпадет и с делителями d3. Делители чисел a1, a2, a3 и a4 совпадут с делителями d3, значит, они совпадут и с делителями d4, и т.д. В конце мы получим, что общие делители чисел a1, a2, …, ak совпадут с делителями dk, а поскольку наибольшим делителем числа dk будет само это число, то НОД (a1, a2, …, ak) =dk.
Это все, что мы хотели бы рассказать о свойствах наибольшего общего делителя.