УказательРазделыОбозначенияАвторО проекте


Начала теории целых чисел

Делимость с остатком

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

5=1\cdot 3 + 2 \ \Rightarrow \ -5=-1\cdot 3 - 2 \ ,

и за остаток от деления (-5)_{} на 3_{} принять отрицательное число (-2). Можно действовать по схеме

5=1\cdot 3 + 2 \ \Rightarrow \ -5=-2\cdot 3 +1 \ ,

и за остаток от деления (-5)_{} на 3_{} взять положительное число 1_{}. Так вот, мы условимся находить остаток по второй схеме — т.е. всегда считать его неотрицательным числом.

§

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

Т

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

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

Доказательство. Возьмем q = \lfloor B/A \rfloor. Тогда по определению целой части числа будет выполнено

q \le \frac{B}{A}< q+1 \ \Rightarrow \ Aq \le B < Aq + A \ \Rightarrow \ 0 \le B- Aq< A \ .

Положим r= B- Aq, тогда получившаяся пара q_{} и r_{} удовлетворяет условиям теоремы.

Для доказательства единственности представления допустим существование еще одного:

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

Предположив для определенности, что \tilde{r}>r, вычтем это представление из предыдущего. Приходим к равенству A \left(q-\tilde{q} \right)=\tilde{r}-r. Поскольку в нем все числа целые, и \tilde{r}-r<A, то оно возможно лишь при q-\tilde{q}=0, но тогда и \tilde{r}-r=0. Пришли к противоречию с предположением о неединственности представления числа B_{}.

В представлении

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

число q_{} называется частным, а r_{}остатком1) от деления B_{} на A_{}. Если r=0_{}, то говорят, что число B_{} делится нацело на A_{} или что B_{} кратно A_{}, а число A_{} называется делителем B_{}. Тривиальными делителями числа A\ne 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_1\in \mathbb N \big| A делится на \ d_1,\ B делится на \ d_1 \big\} \ .

Понятие \operatorname{HOD} обобщается на произвольный набор целых чисел:

d = \operatorname{HOD} (A_1,\dots,A_K)=\max \big\{ d_1\in \mathbb N \big| A_j делится на \ d_1,\ \forall j\in\{1,\dots,K \} \big\} .

Наименьшим общим кратным отличных от нуля чисел A_1,\dots,A_K называют наименьшее положительное число, кратное всем этим числам

\operatorname{HOK} (A_1,\dots,A_K)=\min \big\{d_1\in \mathbb N \big| d_1 делится на \ A_j,\ \forall j\in\{1,\dots,K \} \big\} \ .
П

Пример. \operatorname{HOD} (-6,15)=3,\, \operatorname{HOD} (-6,0)=6,\, \operatorname{HOD} (-6,5)=1 , \operatorname{HOD} (6,10,15)=1; \operatorname{HOK} (6,10,15)=30.

?

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

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


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

Пусть A_{} и B_{} — положительные целые. Поделим B_{} на A_{}: B=Aq_1+r_1, пусть остаток r_1\ne 0: 0<r_1<A. Поделим делитель на этот остаток: A=r_1q_2+r_2, предположим, что остаток r_2\ne 0: 0<r_2<r_1. Снова разделим делитель на остаток и продолжим процесс далее до тех пор, пока на каком-то шаге не произойдет деление нацело, т.е. остаток будет равен нулю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}

для всех j\in \{4,\dots,k-1\}, из предпоследнего равенства алгоритма Евклида получим

r_k=-q_kr_{k-1}+r_{k-2}=-q_k(u_{k-1}A+v_{k-1}B)+(u_{k-2}A+v_{k-2}B)= u_kA+v_kB
\quad npu \quad u_k=-q_ku_{k-1}+u_{k-2},\ v_k=-q_kv_{k-1}+v_{k-2} \ ,

т.е. закон формирования коэффициентов при A_{} и B_{} остается прежним. Но поскольку r_{k} совпадает с \operatorname{HOD}(A,B), то последнее равенство и дает требуемое линейное представление \operatorname{HOD}: u=u_k, v=v_k.

П

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

Решение.

\begin{array}{lcl} u_3&=&-q_3u_2+u_1=-q_3(1+q_1q_2)-q_1=-(q_1+q_3+q_1q_2q_3) \ , \ v_3=1+q_2q_3 \ , \\ u_4&=&1+q_3q_4+q_1q_2+q_1q_4+q_1q_2q_3q_4, \ v_4=-(q_2+q_4+q_2q_3q_4) \ , \\ u_5&=&-(q_1+q_3+q_5+q_1q_4q_5+q_1q_2q_3+q_1q_2q_5+q_3q_4q_5+q_1q_2q_3q_4q_5) \ , \\ v_5&=&1+q_4q_5+q_2q_3+q_2q_5+q_2q_3q_4q_5 \ , \\ u_6&=&1+q_1q_2+q_1q_4+q_3q_4+q_1q_6+q_3q_6+q_5q_6+q_1q_2q_3q_4+q_1q_2q_5q_6+ \\ & &+q_1q_2q_3q_6+ q_1q_4q_5q_6+q_3q_4q_5q_6+q_1q_2q_3q_4q_5q_6 \ ,\\ v_6&=&-(q_2+q_4+q_6+q_2q_3q_4+q_2q_3q_6+q_2q_5q_6+q_4q_5q_6+ q_2q_3q_4q_5q_6) \ . \end{array}

Трудно уловить закономерность в формировании этих выражений из q_{j}, тем не менее мы ее сейчас выявим.

?

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

Пусть имеется произвольная числовая последовательность x_1,x_2,\dots,x_j,\dots (не обязательно целочисленная). Числа K_{j}, задаваемые соотношениями

K_0= 1,\ K_1 = x_1,\ K_j= K_{j-1}x_j+K_{j-2} \quad npu \ j\ge 2

называются континуантами. Иногда то обстоятельство, что K_{j} зависит от x_1,\dots,x_j подчеркивают, записывая континуанту в виде K_j(x_1,\dots,x_j).

§

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

Т

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

П

Пример.

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

Легко видеть, что числа u_{j} и v_{j}, введенные выше равенствами

u_j=-q_ju_{j-1}+u_{j-2} \ , \quad v_j=-q_jv_{j-1}+v_{j-2} \ ,

являются континуантами:

\begin{array}{lll} u_j&=K_j(-q_1,-q_2,\dots,-q_j) & = (-1)^{j}K_j(q_1,q_2,\dots,q_j) \ , \\ v_j&=K_{j-1}(-q_2,\dots,-q_{j}) & = (-1)^{j-1}K_{j-1}(q_2,\dots,q_{j}) \ . \end{array}

Приведенные выше формулы явных выражений для этих величин с увеличением j_{} становятся слишком громоздкими. Для практических расчетов более просты вычисления континуант непосредственно по рекурсивным формулам. Поскольку выполняемые операции однотипны, вычисления удобно оформить в виде таблицы. Так, стартовое состояние таблицы для вычисления K_j(q_1,q_2,\dots,q_j) следующее:

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

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

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

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

П

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

Решение. Алгоритм Евклида для данного примера приведен в предыдущем пункте, он дает последовательность частных q_1=1,\, q_2=4,\, q_3=1,\, q_4=2, завершаясь при k=4_{}.

\begin{array}{|c|c|c|c|c|c|} \hline j & 0 & 1 & 2 & 3 & 4 \\ \hline q_j & - & 1 & 4 & 1 & 2 \\ \hline K_j(q_1,q_2,\dots,q_j) & 1 & 1 & 5 & 6 & 17 \\ \hline K_{j-1}(q_2,\dots,q_j) & - & 1 & 4 &5 & 14 \\ \hline \end{array}

По формулам получаем u=17,v=-14.

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

=>

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

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

И

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

Делимость чисел

Взаимно простые числа

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

!

Следует различать понятия «взаимно простые числа» и «попарно взаимно простые числа».

П

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

Т

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

uA+vB=1 \ .

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

§

Результат теоремы, на первый взгляд, кажется несущественным. Однако первое впечатление ошибочно — он имеет «значительные последствия», и, в частности, применяется для доказательства следующих результатов.

Т

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

Доказательство. Применим метод индукции по числу сомножителей. Пусть \operatorname{HOD} (A_j,B)=1 для всех рассматриваемых индексов j_{}. По теореме 1 это условие эквивалентно выполнению равенств

u_1A_1+v_1B=1, \ u_2A_2+v_2B=1, \dots

при некоторых целых u_j,v_j. В случае K=2, перемножая первые два равенства, получим

u_1u_2A_1A_2+\left(u_1v_2A_1 + u_2v_1A_2+v_1v_2B\right) B = 1 \ .

По теореме 1, числа A_1A_2 и B_{} взаимно простые.

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

Т

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

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

Т

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

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

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

Т

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

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

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

Простые числа

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

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

Т

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

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

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


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

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


A

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

§

Таблица первых 500_{} простых чисел ЗДЕСЬ

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

Т

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

\frac{\ln 2}{2} \frac{N}{\ln N} < \pi(N) < 2\ln 2 \frac{N}{\ln N} \ .

Здесь \ln означает натуральный логарифм, т.е. логарифм по основанию числа Эйлера

e= \lim_{n\to +\infty} \left(1+ \frac{1}{n} \right)^n \approx 2.7182818284590452353\dots

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

§

П.Л.Чебышевым были получены и более тесные границы:

0.921 \frac{N}{\ln N} < \pi(N) < 1.106 \frac{N}{\ln N} \ ;

обе приведенные оценки имеют следствием:

\lim_{N\to \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 ;

их называют близнецами5). С другой стороны, существуют сколь угодно длинные отрезки натурального ряда, свободные от простых чисел:

Т

Теорема. Для любого натурального 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} при целых a_0,\dots,a_m; а также среди чисел, близко расположенных к степеням 2_{}. Так, например, доказано, что последовательности \left\{4n+1 \right\}_{n=1}^{\infty} и \left\{6n+1 \right\}_{n=1}^{\infty} содержат бесконечно много простых чисел. Первые 40_{} чисел последовательности Эйлера \left\{n^2-n+41 \right\}_{n=1}^{\infty} будут простыми, но 41-е является составным; первые 79 чисел последовательности \left\{n^2-79\,n+1601 \right\}_{n=1}^{\infty} будут простыми, но 80-е является составным; числа Ферма 2^{2^n}+1 будут простыми при n\in \{1,2,3,4,13,14,\dots \}, но составными при n\in \{5,6,7,\dots,12,15,16,\dots\}.

§

Легко доказать, что не существует полинома одной переменной с целыми коэффициентами, все значения которого являются простыми числами. Более того, не существует полинома от нескольких переменных с комплексными коэффициентами, отличного от константы, все значения которого при неотрицательных значениях переменных являются простыми числами. Однако, существуют полиномы, все положительные значения которых при неотрицательных значениях переменных являются простыми числами. См. ЗДЕСЬ.

?

Сравнить плотности простых чисел в последовательностях Эйлера \left\{n^2-n+41 \right\}, \left\{n^2+n+72\,491 \right\} и в последовательности \left\{n^2-79\,n+1601 \right\} при n\in \{1,\dots, N \}, где N\in \{ 10^2,10^3,10^6 \}.

§

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

?

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

Наибольшим числом, для которого — по состоянию на февраль 2013 г. — была установлена простота, являлось число 2^{57\,885\,161}-1, состоящее из 17\,425\,170 цифр. Числа вида 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_{} на сомножители, а сам процесс нахождения канонического разложения — факторизацией6) числа A_{}.

П

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

Т

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

A=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}}

каноническое разложение числа A_{}, то все делители этого числа заключены во множестве

\left\{p_1^{\ell_1}p_2^{\ell_2}\times \dots \times p_{\mathfrak r}^{\ell_{\mathfrak r}} \, \Big| \, 0\le \ell_1 \le {\mathfrak m}_1, 0\le \ell_2 \le {\mathfrak m}_2, \dots , 0\le \ell_{\mathfrak r} \le {\mathfrak m}_{\mathfrak r} \right\} \ .

?

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

=>

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

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

Т

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

A_j=p_1^{{\mathfrak m}_{1j}}p_2^{{\mathfrak m}_{2j}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{{\mathfrak r}j}}

(здесь возможно, что некоторые из показателей {\mathfrak m}_{\ell j} равны нулю). Тогда

\operatorname{HOD} (A_1,\dots,A_K)= p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ , \quad где \ {\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 где \ {\mathfrak M}_{\ell} = \max_{j=1,\dots,K} {\mathfrak m}_{\ell j} \ .

П

Пример.

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

?

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

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

?

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

Ответ ЗДЕСЬ.

Т

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

{\mathfrak m}=\left\lfloor \frac{n}{p}\right\rfloor +\left\lfloor \frac{n}{p^2}\right\rfloor +\left\lfloor \frac{n}{p^3}\right\rfloor +\dots+\left\lfloor \frac{n}{p^K} \right\rfloor \ .

Здесь \lfloor A \rfloor обозначает целую часть числа A_{}, а число K \in \mathbb N определяется как показатель максимальной степени p_{}, умещающейся в n_{}:

p^K\le n < p^{K+1} \ ; очевидно, \ K=\lfloor \log_{p} n \rfloor \ .

?

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

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

П

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

Решение. Вопрос равнозначен поиску максимального K\in \mathbb N такого, что 153! делится на 10^K=2^K\cdot 5^K. Очевидно, что в каноническом разложении n!_{} показатель двойки будет больше показателя любого другого простого числа, и для ответа на наш вопрос достаточно подсчитать показатель пятерки.

\left\lfloor\frac{153}{5}\right\rfloor +\left\lfloor\frac{153}{25}\right\rfloor+ \left\lfloor\frac{153}{125}\right\rfloor=30+6+1=37 \ .

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

Т

Теорема. Мультиномиальный коэффициент

\frac{n!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad n_1+ n_2+\dots +n_K=n

является целым числом.

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

Признаки делимости

Задача нахождения канонического представления числа становится достаточно трудоемкой при больших A_{} : в худшем случае приходится проверять A_{} на делимость со всеми простыми числами 2,3,5,\dots, не превосходящими \sqrt {A}. В связи с этим представляют интерес косвенные признаки делимости на данное простое p_{}, т.е. такие, которые не требуют явного выполнения деления A_{} на p_{}. Из школьного курса известны признаки делимости на 2,3 и 5, когда исключительно по цифрам десятичного представления (s+1)-значного числа

A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} = {\mathfrak a}_1\times 10^s+{\mathfrak a}_2 \times 10^{s-1} + \dots +{\mathfrak a}_s \times 10 + {\mathfrak a}_{s+1}

можно установить, делится или не делится A_{} на p_{}. Такие признаки можно установить и для других простых чисел. Проиллюстрируем на примерах p\in \{11,13,37\}.

Представим число A_{} в виде

A=10\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + {\mathfrak a}_{s+1}= 11\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + \left({\mathfrak a}_{s+1}- \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \right) .

Первое слагаемое в правой части делится на 11_{}, поэтому для того чтобы A_{} делилось на 11_{}, необходимо и достаточно, чтобы делилось на 11_{} число

A_1 = {\mathfrak a}_{s+1} - \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \ .

Очевидно, что A_1<A и к этому новому числу мы можем применить тот же прием:

A_1={\mathfrak a}_{s+1} -({\mathfrak a}_{s}-\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} +11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}) \ .

Число A_{} делится на 11_{} тогда и только тогда, когда делится на 11_{} число

A_2= {\mathfrak a}_{s+1} -{\mathfrak a}_{s} + \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} \ .

С помощью интуиции и индукции получаем следующий критерий.

Т

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

{\mathfrak a}_1-{\mathfrak a}_2 + {\mathfrak a}_3 - \dots +(-1)^{j-1}{\mathfrak a}_j +\dots + (-1)^{s-1}{\mathfrak a}_s+ (-1)^{s}{\mathfrak a}_{s+1} \ ,

т.е. разность между суммой цифр числа A_{}, стоящих на нечетных местах и суммой цифр, стоящих на четных местах.

Тот же прием срабатывает и для p=13:

A= 13\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} + \left({\mathfrak a}_{s+1}- 3\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s} \right)

и т.д.

Т

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

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

П

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

Решение.

3^6-6\times 3^5+0\times 3^4-1\times 3^3+1\times 3^2-9\times 3+7 =-767 ,\ 7\times 3^2-6\times 3+7=52 \ .

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

Ситуация с числом 37_{} несколько сложнее. Можно попробовать оперировать с двузначными числами:

A=100\times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}+ \underline{{\mathfrak a}_s {\mathfrak a}_{s+1}}=3\times 37 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}+ (\underline{{\mathfrak a}_s {\mathfrak a}_{s+1}}-11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}}) ,

и связать делимость на 37_{} числа A_{} с делимостью числа

B_1= \underline{{\mathfrak a}_s {\mathfrak a}_{s+1}} -11 \times \underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_{s-1}} \ .

Однако более изящный результат получится, если посчастливилось подметить, что 1000=37\times 27+1. Разобьем десятичное представление числа A_{} на триплеты, начиная с конца:

A= \underline{{\mathfrak a}_{s-1}{\mathfrak a}_s {\mathfrak a}_{s+1}}+10^3\times \underline{{\mathfrak a}_{s-4}{\mathfrak a}_{s-3} {\mathfrak a}_{s-2}} +10^6\times \underline{{\mathfrak a}_{s-7}{\mathfrak a}_{s-6} {\mathfrak a}_{s-5}}+\dots
Т

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

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

П

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

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

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

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

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

Т

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

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

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

П

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

7-5+3-4+7-9+6-4+3-8+9-2+0-5=-2 \ .

Согласно определению остатка: -2 при делении на 11_{} дает в остатке 9_{}.

?

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

§

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

Факторизация

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

?

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

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

A=\left(\frac{{\mathcal A}_1+{\mathcal A}_2}{2} \right)^2 - \left(\frac{{\mathcal A}_1-{\mathcal A}_2}{2} \right)^2 \ .

Этот факт, замеченный еще Ферма, можно развить до следующего критерия.

Т

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

A_0 = A, \ A_1=A_0+1,\ A_2=A_1+3,\ \dots,
A_n = A_{n-1}+(2n-1) \quad npu \quad 1\le n \le \left\lfloor \frac{A-9}{6} \right\rfloor \ .

Число A_{} будет составным тогда и только тогда, когда среди этих чисел имеется полный квадрат: \exists t\in \mathbb N такое, что A_j=t^2. В этом случае

A=(t-j)(t+j) \ .

Доказательство. Очевидно,

A_1=A+1,\ A_2=A+1+3=A+4,\ A_3=A+1+3+5=A+9,\dots,
A_j=A+\left[1+3+\cdots +(2j-1) \right]=A+j^2 \ .

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

j\le \left\lfloor (A-9)/6 \right\rfloor \ \Rightarrow A\ge 6j+9>2j+1 \ .

Используем эту оценку в равенстве t^2=A+j^2: t^2>j^2+2j+1=(j+1)^2, т.е. t>j+1.

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

Если {\mathcal A}_1>{\mathcal A}_2, то

3\le {\mathcal A}_2 \le \sqrt{A} \le {\mathcal A}_1 \le 1/3 A\ \Rightarrow \ {\mathcal A}_1 -{\mathcal A}_2 \le 1/3 A -3 \ \Rightarrow \ 0 \le j \le \frac{1/3 A -3}{2} \ ,

т.е. целое число j_{} удовлетворяет ограничению j \le \left\lfloor (A-9)/6 \right\rfloor.

П

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

Решение. Заметим, что число, составляющее полный квадрат, не может оканчиваться на 2,3,7 или 8_{}; если оканчивается на 5_{}, то должно оканчиваться на 25_{}; если оканчивается на 0_{}, то должно оканчиваться на 00_{}. Эти тривиальные соображения позволяют сразу же отбросить из рассмотрения первые числа последовательности \{A_j\}:

A_1=792020,\ A_2=792023,\ A_3=792028, A_4=792035 \ .

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

§

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

§

Метод факторизации из теоремы эффективен, если факторизуемое число близко к полному квадрату, т.е. раскладывается на два сомножителя {\mathcal A}_1 и {\mathcal A}_2 близкие по величине. Фактически в этом случае удается свести задачу факторизации к задаче проверки нового числа на равенство полному квадрату и до положительного ответа удается дойти за небольшое количество шагов (итераций) j_{}. Если же факторизуемое число далеко от полного квадрата, то алгоритм может работать достаточно долго. Например, для определения хотя бы одного множителя числа 71299=37\cdot 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) = 60\left( 1-\frac{1}{2} \right)\left( 1-\frac{1}{3}\right) \left( 1-\frac{1}{5} \right)=16 ,\quad \phi (81)=81-27=54 , \quad \phi (481) = 432 \ .

=>

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

\phi (A_1A_2\times \dots \times A_K)=\phi (A_1) \phi (A_2) \times \dots \times \phi (A_K) \ ;

в частности, если числа p_1,p_2,\dots,p_{\mathfrak r} — различные простые, то

\phi (p_1p_2\times \dots \times p_{\mathfrak r})=(p_1-1)(p_2-1)\times \dots \times (p_{\mathfrak r}-1) \ .

=>

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

§

Теорема Эйлера является частным случаем следующего более общего результата, известного под названием формула включений-исключений.

Т

Теорема. Пусть даны подмножества7) 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_{1\le j_1 < j_2 \le \mathfrak r} \operatorname{Card}(A_{j_1} \cap A_{j_2}) + \sum_{1\le 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

1) quotiens (лат.) — сколько раз; residu(um) (лат.) — остаток.
2) Это обязательно случится за конечное число шагов, так как числа уменьшаются.
3) primus (лат.) — первый; Евклид называл простое число \pi\rho\tilde{\omega}\tau{\rm o}\varsigma \ \alpha\rho\iota\vartheta\mu {\rm o} \varsigma, т.е. «первым числом». Еще в учебниках XIX века взаимно простые числа назывались «числами первыми между собой», а простые числа — «первоначальными».
4) Неудачное использование обозначения функции — посредством буквы, прочно зарезервированной за константой 3.1415926\dots; но что поделать — традиция!
5) Гипотеза о бесконечности числа близнецов не доказана.
6) factor (англ.) — множитель.
7) Необязательно различные.

2016/03/16 17:58 редактировал au