==Начала теории целых чисел== ~~TOC~~ === Делимость с остатком == Прежде чем излагать новый материал, необходимо договориться о терминологии. Понятие остатка от деления положительного целого числа $ 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 rr $, вычтем это представление из предыдущего. Приходим к равенству $ A \left(q-\tilde{q} \right)=\tilde{r}-r $. Поскольку в нем все числа целые и $ \tilde{r}-r ♦ В представлении $$ B=Aq+r\, , \quad npu \ \{q,r\} \subset \mathbb Z \ \ u \quad 0\le r Для обозначения факта делимости $ 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 \ \mbox{ делится на } \ d_1,\ B \ \mbox{ делится на } \ d_1 \big\} \ .$$ Понятие $ \operatorname{HOD} $ обобщается на произвольный набор целых чисел: $$d = \operatorname{HOD} (A_1,\dots,A_K)=\max \big\{ d_1\in \mathbb N \big| A_j \ \mbox{ делится на } \ d_1,\ \forall j\in\{1,\dots,K \} \big\} .$$ **Наименьшим общим кратным** отличных от нуля чисел $ A_1,\dots,A_K $ называют наименьшее положительное число, кратное всем этим числам $$ \operatorname{HOK} (A_1,\dots,A_K)=\min \big\{d_1\in \mathbb N \big| d_1 \ \mbox{ делится на } \ A_j,\ \forall j\in\{1,\dots,K \} \big\} \ .$$ !!П!! **Пример.** $ \operatorname{HOD} (-6,15)=3,\, \operatorname{HOD} (-6,0)=6,\, \operatorname{HOD} (-6,5)=1 , \operatorname{HOD} (6,10,15)=1 $; $ \operatorname{HOK} (6,10,15)=30 $. !!?!! Философ ((http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D1%82%D0%BE%D0%BD Платон)) считал, что наилучший размер для государства --- $ 5040 $ семейств. Одним из обоснований этого числа он выдвигал его делимость на все числа от $ 1_{} $ до $ 10_{} $. Является ли это число наименьшим натуральным с таким свойством? Для нахождения $ \operatorname{HOD} $ используется следующий алгоритм. ---- Алгоритм Евклида. Пусть $ A_{} $ и $ B_{} $ --- положительные целые. Поделим $ B_{} $ на $ A_{} $: $ B=Aq_1+r_1 $, пусть остаток $ r_1\ne 0 $: $ 0 ♦ !!И!! Биографические заметки об Евклиде ☞ ((:biogr#evklid ЗДЕСЬ)). !!П!! **Пример.** Найти $ \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_{} $. **Доказательство** ☞ ((:numtheory:lame ЗДЕСЬ)). ===Линейное представление НОД== !!Т!! **Теорема.** //Существуют целые числа// $ 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) $. Континуанта является примером ((:recurr рекуррентной последовательности)), задаваемой линейным однородным разностным уравнением с переменными коэффициентами. То, что континуанта определяется как число --- не существенно; можно говорить о $ K_j(x_1,\dots,x_j) $ как о ((:polynomialm полиноме)) от $ 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) $ следующее: {{ cont1.gif |}} и значение для $ K_2(q_1,q_2)=1+q_1q_2 $ вычисляется по схеме, указанной стрелками. Следующее состояние таблицы --- {{ cont2.gif |}} и очередное значение $ 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) $ строится по тому же принципу, только с иными стартовыми значениями: {{ cont3.gif |}} Обычно таблицы для вычисления обеих континуант объединяют. !!П!! **Пример.** Найти линейное представление $ \operatorname{HOD} (5797,7038) $. **Решение.** Алгоритм Евклида для данного примера приведен в предыдущем ((#алгоритм_евклида пункте)), он дает последовательность частных $ q_1=1,\, q_2=4,\, q_3=1,\, q_4=2 $, завершаясь при $ k=4_{} $. $$ \begin{array}{|c|c|c|c|c|c|} \hline j & 0 & 1 & 2 & 3 & 4 \\ \hline q_j & - & 1 & 4 & 1 & 2 \\ \hline K_j(q_1,q_2,\dots,q_j) & 1 & 1 & 5 & 6 & 17 \\ \hline K_{j-1}(q_2,\dots,q_j) & - & 1 & 4 &5 & 14 \\ \hline \end{array} $$ По формулам получаем $ u=17,v=-14 $. **Проверка.** $ 17\times 5797 -14 \times 7038=98\,549-98\, 532=17= \operatorname{HOD} (5797,7038) $. !!=>!! Существует бесконечное число линейных представлений $ \operatorname{HOD} $. **Доказательство.** Действительно, если пара $ \tilde u, \tilde v $ --- какое-то из решений уравнения $ uA+vB= \operatorname{HOD} (A,B) $, то при $ \forall t\in \mathbb Z $ пара $ \tilde{\tilde u}=\tilde u+tB,\tilde{\tilde v} =\tilde v-tA $ также является решением. Можно, например, подобрать число $ t_{} $ так, чтобы было выполнено $ 0\le \tilde{\tilde u} ♦ !!И!! Биографические заметки об Евклиде ☞ ((:biogr#евклид ЗДЕСЬ)). ==Делимость чисел== ===Взаимно простые числа== Два целых числа $ 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_{} $. **Доказательство.** Применим ((:basics:induction метод индукции)) по числу сомножителей. Пусть $ \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 \ . $$ **Доказательство** (набросок) ☞ ((:numtheory:cesaro ЗДЕСЬ)). ===Простые числа== Число $ 1_{} $ имеет только один положительный делитель, именно $ 1_{} $. В этом отношении число $ 1_{} $ в ряду натуральных чисел стоит совершенно особо. Всякое целое, большее $ 1_{} $, имеет не менее двух делителей: по крайней мере тривиальные делители (само число и $ 1_{} $) у него всегда существуют. Если число $ A>1 $ имеет __только__ тривиальные делители, то оно называется **простым**. Целое $ A>1 $, имеющее кроме тривиальных другие положительные делители, называется **составным**. В дальнейшем за простым числом закрепим обозначение $ p_{} $. **p**rimus (//лат.//) --- первый; Евклид называл простое число $ \pi\rho\tilde{\omega}\tau{\rm o}\varsigma \ \alpha\rho\iota\vartheta\mu {\rm o} \varsigma $, т.е. "первым числом". Еще в учебниках XIX века взаимно простые числа назывались "числами первыми между собой", а простые числа --- "первоначальными". !!Т!! **Теорема [Евклид].** //Множество простых чисел бесконечно.// **Доказательство** проводится от противного. Предположим, что существует конечное число простых чисел и наибольшее из них равно $ 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} ☞ ((http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BE_%D0%AD%D1%80%D0%B0%D1%82%D0%BE%D1%81%D1%84%D0%B5%D0%BD%D0%B0 ЗДЕСЬ)) Таблица первых $ 500_{} $ простых чисел ☞ ((http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB ЗДЕСЬ)) Можно заметить, что относительная плотность простых чисел убывает: на первый десяток их приходится $ 4_{} $, т.е. $ 40_{} \% $, на сотню --- $ 25_{} $ , т.е. $ 25 \% $, на тысячу --- $ 168 $, т.е. $ \approx 17 \% $, на миллион --- $ 78\, 498 $, т.е. $ \approx 8 \% $. !!Т!! **Теорема [Чебышев].** //Обозначим количество простых чисел, не превосходящих// $ N_{} $, //через//[[Неудачное использование обозначения функции --- посредством буквы, прочно зарезервированной за константой $ 3.1415926\dots $; но что поделать --- традиция!]] $ \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 $$ На рисунке виден сравнительный рост количества простых чисел {{ numprimes.gif |}} П.Л.Чебышевым были получены и более тесные границы: $$ 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 ; $$ их называют **близнецами**[[Гипотеза о бесконечности числа близнецов не доказана.]]((:numtheory:vspom5 .)) С другой стороны, существуют сколь угодно длинные отрезки натурального ряда, свободные от простых чисел: !!Т!! **Теорема.** //Для любого натурального// $ k_{} $ //существует натуральное число// $ N_{} $ //такое, что все числа// $$ N+1, N+2,\dots, N+k $$ //являются составными.// **Доказательство.** Числа $$ (k+1)!+2, (k+1)!+3,\dots, (k+1)!+(k+1) $$ являются составными, поскольку первое делится на $ 2_{} $, второе --- на $ 3_{} $, и т.д., последнее --- на $ k+1 $. ♦ ===="Генераторы" простых чисел== Отдельной задачей является вопрос о "генераторах" простых чисел --- аналитически заданных последовательностях, все элементы которых являются простыми. Такие последовательности искались среди арифметических прогрессий, а, в общем случае, среди последовательностей вида $$ \left\{ a_0n^m+a_1n^{m-1}+\dots + a_m \right\}_{n=1}^{\infty} \quad \mbox{ при } \ \{a_0,\dots,a_m\} \subset \mathbb Z \, ; $$ а также среди чисел, близко расположенных к степеням $ 2_{} $. Так, например, доказано, что последовательности $$ \left\{4n+1 \right\}_{n=1}^{\infty} \quad \mbox{ и } \quad \left\{6n+1 \right\}_{n=1}^{\infty} $$ содержат бесконечно много простых чисел. Первые $ 40_{} $ чисел **последовательности Эйлера** $$ \left\{n^2-n+41 \right\}_{n=1}^{\infty} $$ являются простыми, но $ 41 $-е является составным; первые $ 79 $ чисел последовательности $$ \left\{n^2-79\,n+1601 \right\}_{n=1}^{\infty} $$ будут простыми, но $ 80 $-е является составным. **Числа Ферма** $$ 2^{2^n}+1 $$ будут простыми при $ n\in \{1,2,3,4,13,14,\dots \} $, но составными при $ n\in \{5,6,7,\dots,12,15,16,\dots\} $. Легко доказать, что не существует полинома одной переменной с целыми коэффициентами, все значения которого являются простыми числами. Более того, не существует ((:polynomialm полинома от нескольких переменных)) с комплексными коэффициентами, отличного от константы, все значения которого при неотрицательных значениях переменных являются простыми числами. Однако существуют полиномы, все __положительные__ значения которых при неотрицательных значениях переменных являются простыми числами. См. ☞ ((:numtheory:vspom3 ЗДЕСЬ)). !!?!! Сравнить плотности простых чисел в последовательностях Эйлера $$ \left\{n^2-n+41 \right\} \quad \mbox{ и } \quad \left\{n^2+n+72\,491 \right\} $$ и в последовательности $$ \left\{n^2-79\,n+1601 \right\} $$ при $ n\in \{1,\dots, N \} $, где $ N\in \{ 10^2,10^3,10^6 \} $. !!§!! ''Геометрию последовательностей вида'' $ \left\{n^2-n+a \right\} $ ''при'' $ a\in \mathbb Z $ ''см.'' ☞ ((:numtheory:spiral ЗДЕСЬ)). !!?!! ((#источники [2])). Проверить, что в последовательности $$ \left\{n^2-2999\,n+2\,248\,541 \right\} $$ имеется $ 79 $ подряд идущих простых чисел. Наибольшим числом, для которого --- по состоянию на декабрь 2018 г. --- установлена простота, является ((http://www.mersenne.org/ число)) $ 2^{82\,589\,933} -1 $, состоящее из $ 24\,862\,048 $ цифр. Числа вида $ 2^{n}-1 $ называются **числами Мерсенна**. Значение математических работ Марена Мерсенна (Mersenne Marin, 1588-1648) сравнительно невелико, но его роль как организатора европейской науки Нового времени огромна, см. ☞ ((http://krotov.info/history/17/1670/elizarov.htm ЗДЕСЬ)). !!§!! ''Критерии простоты числа'' $ p_{} $ ''в настоящем ресурсе'': ☞ ((:modular:wilson ТЕОРЕМА ВИЛЬСОНА)); ☞ ((:modular:index#критерий_простоты_числа КРИТЕРИЙ, ОСНОВАННЫЙ НА ЗНАНИИ КАНОНИЧЕСКОГО РАЗЛОЖЕНИЯ ЧИСЛА)) $ 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_{} $ на сомножители, а сам процесс нахождения канонического разложения --- **факторизацией**[[factor (//англ.//) --- множитель.]] **числа** $ A_{} $. !!П!! **Пример.** $ 18225625000=2^3\cdot 5^{7}\cdot 11^{2}\cdot 241 $. !!Т!! **Теорема 4.** //Если// $$ A=p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} $$ --- //каноническое разложение числа// $ A_{} $, //то все делители этого числа заключены во множестве// $$ \left\{p_1^{\ell_1}p_2^{\ell_2}\times \dots \times p_{\mathfrak r}^{\ell_{\mathfrak r}} \, \Big| \, 0\le \ell_1 \le {\mathfrak m}_1, 0\le \ell_2 \le {\mathfrak m}_2, \dots , 0\le \ell_{\mathfrak r} \le {\mathfrak m}_{\mathfrak r} \right\} \ . $$ !!?!! Сколько чисел содержится в этом множестве? !!=>!! Сумма различных делителей числа $ A_{} $ равна $$ \frac{p_1^{{\mathfrak m}_1+1}-1}{p_1-1}\frac{p_2^{{\mathfrak m}_2+1}-1}{p_2-1} \times \dots \times \frac{p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}+1}-1}{p_{\mathfrak r}-1} \ . $$ !!Т!! **Теорема 5.** //Пусть множество// $ \{ p_1,\dots,p_{\mathfrak r} \} $ //представляет собой объединение множеств простых сомножителей целых чисел// $ A_1,\dots,A_K $. //Выпишем "универсальное" каноническое разложение для каждого// $ A_{j} $: $$A_j=p_1^{{\mathfrak m}_{1j}}p_2^{{\mathfrak m}_{2j}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{{\mathfrak r}j}} $$ (//здесь возможно, что некоторые из показателей// $ {\mathfrak m}_{\ell j} $ //равны нулю//). //Тогда//$$ \operatorname{HOD} (A_1,\dots,A_K)= p_1^{{\mathfrak m}_1}p_2^{{\mathfrak m}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{\mathfrak r}} \ , \quad \mbox{ где } \ {\mathfrak m}_{\ell} = \min_{j=1,\dots,K} {\mathfrak m}_{\ell j} \ , $$ $$ \operatorname{HOK} (A_1,\dots,A_K)= p_1^{{\mathfrak M}_1}p_2^{{\mathfrak M}_2}\times \dots \times p_{\mathfrak r}^{{\mathfrak M}_{\mathfrak r}}\ , \quad \mbox{ где } \ {\mathfrak M}_{\ell} = \max_{j=1,\dots,K} {\mathfrak m}_{\ell j} \ . $$ !!П!! **Пример.** $$ \operatorname{HOD} (20099016,\, 9900,\, 3690) = $$ $$ =\operatorname{HOD} (2^3\cdot 3^5\cdot 7^2\cdot 211,\ 2^2\cdot 3^2\cdot 5^2\cdot 11,\ 2\cdot 3^2\cdot 5\cdot 41)=2\cdot 3^2=18 \ ; $$ $$\operatorname{HOK} (20099016,\, 9900,\, 3690) =2^3\cdot 3^5 \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 41 \cdot 211 = 226616405400 \ . $$ !!?!! Доказать, что для любых натуральных $ A_{} $ и $ B_{} $: $$ \operatorname{HOD} (A,B) \cdot \operatorname{HOK} (A,B) = A\cdot B \ . $$ !!?!! Результат предыдущего упражнения позволяет выразить $ \operatorname{HOK} (A,B) $ через $ \operatorname{HOD} (A,B) $. Как обобщить эту формулу --- выразить $ \operatorname{HOK} $ произвольного набора чисел через $ \operatorname{HOD} $? **Ответ** ☞ ((numtheory:vspom2 ЗДЕСЬ)). !!Т!! **Теорема [Лежандр].** //Простое число// $ 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 $ //обозначает// //((:algebra2:notations#целая_часть_числа целую часть)) числа// $ A_{} $, //а число// $ K \in \mathbb N $ //определяется как показатель максимальной степени// $ p_{} $, //умещающейся в// $ n_{} $: $$ p^K\le n < p^{K+1} \ ; \ \mbox{ очевидно, } \ K=\lfloor \log_{p} n \rfloor \ . $$ !!?!! Показать, что $$ \left\lfloor \frac{n}{p^2}\right\rfloor = \left\lfloor \frac{\left\lfloor \frac{n}{p}\right\rfloor }{p} \right\rfloor \ . $$ !!П!! **Пример.** Сколькими нулями оканчивается десятичное представление числа $ 153! $ ? **Решение.** Вопрос равнозначен поиску максимального $ K\in \mathbb N $ такого, что $ 153! $ делится на $ 10^K=2^K\cdot 5^K $. Очевидно, что в каноническом разложении $ n!_{} $ показатель двойки будет больше показателя любого другого простого числа, и для ответа на наш вопрос достаточно подсчитать показатель пятерки. $$\left\lfloor\frac{153}{5}\right\rfloor +\left\lfloor\frac{153}{25}\right\rfloor+ \left\lfloor\frac{153}{125}\right\rfloor=30+6+1=37 \ .$$ **Ответ.** Десятичное представление оканчивается $ 37_{} $-ю нулями. !!Т!! **Теорема.** //((:binomial Мультиномиальный коэффициент))// $$ \frac{n!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad n_1+ n_2+\dots +n_K=n $$ //является целым числом.// **Доказательство** ☞ ((:numtheory:vspom1 ЗДЕСЬ)). ===Признаки делимости == Задача нахождения канонического представления числа становится достаточно трудоемкой при больших $ 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 ♦ !!П!! **Пример.** Остаток от деления числа $ 50298346974357 $ на $ 11_{} $ равен $ 9_{} $. Cумма его цифр с чередующимися знаками из теоремы: $$ 7-5+3-4+7-9+6-4+3-8+9-2+0-5=-2 \ . $$ Согласно ((numtheory#делимость_с_остатком определению остатка)): $ -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_{} $ ☞ ((:modular#теоремы_ферма_и_эйлера ЗДЕСЬ)) ===Факторизация== Как уже отмечалось в начале ☞ ((#простые_числа ПУНКТА)), общий метод факторизации данного числа $ A_{} $ заключается в том, что $ A_{} $ пробуют делить последовательно на простые числа, не превосходящие $ \sqrt {A} $. Для некоторых классов чисел известны более быстрые способы факторизации, не требующие такого перебора. Например, число $ A=N^4-4 $ при $ N\in \mathbb N $ факторизуется очевидным способом; несколько труднее установить справедливость следующего результата. !!?!! **[Софи Жермен]** Доказать, что при $ N>1 $ число $ N^4+4 $ всегда составное. Очевидно также, что любое число вида $ A=S^2-T^2 $ при $ \{S,T \}\subset \mathbb N $ всегда составное. Это утверждение допускает и обращение: если нечетное число $ A>0 $ --- составное, т.е. $ A={\mathcal A}_1{\mathcal A}_2 $ и $ {\mathcal A}_1>{\mathcal A}_2 $, то его можно представить в виде разности двух квадратов целых чисел: $$ A=\left(\frac{{\mathcal A}_1+{\mathcal A}_2}{2} \right)^2 - \left(\frac{{\mathcal A}_1-{\mathcal A}_2}{2} \right)^2 \ . $$ Этот факт, замеченный еще Ферма, можно развить до следующего критерия. !!Т!! **Теорема.** //Пусть число// $ A\ge 9 $ // нечетно. Рассмотрим последовательность натуральных чисел// $$ A_0 = A, \ A_1=A_0+1,\ A_2=A_1+3,\ \dots,\ $$ $$ A_n = A_{n-1}+(2n-1) \quad npu \quad 1\le n \le \left\lfloor \frac{A-9}{6} \right\rfloor \ . $$ //Число// $ A_{} $ //будет составным тогда и только тогда, когда среди этих чисел имеется полный квадрат:// $ \exists t\in \mathbb N $ //такое, что// $ A_j=t^2 $.// В этом случае// $$ A=(t-j)(t+j) \ . $$ **Доказательство.** Очевидно, $$A_1=A+1,\ A_2=A+1+3=A+4,\ A_3=A+1+3+5=A+9,\dots, $$ $$ A_j=A+\left[1+3+\cdots +(2j-1) \right]=A+j^2 \ .$$ **Достаточность.** Пусть $ A_j=t^2 $, тогда $ A=(t-j)(t+j) $. Покажем, что при ограничении из условия теоремы: $ j \le \left\lfloor (A-9)/6 \right\rfloor $ будет выполнено $ t-j>1 $, т.е. $ A_{} $ раскладывается на два нетривиальных множителя. Имеем $$j\le \left\lfloor (A-9)/6 \right\rfloor \ \Rightarrow A\ge 6j+9>2j+1 \ .$$ Используем эту оценку в равенстве $ t^2=A+j^2 $: $ t^2>j^2+2j+1=(j+1)^2 $, т.е. $ t>j+1 $. **Необходимость.** Если число $ A_{} $ --- нечетное составное: $ A={\mathcal A}_1{\mathcal A}_2 $, то имеет место представление $ A=\left( ({\mathcal A}_1+{\mathcal A}_2)/2 \right)^2 - \left( ({\mathcal A}_1-{\mathcal A}_2)/2 \right)^2 $, которое соответствует формуле $ A=(t-j)(t+j) $ при $ t=1/2 ({\mathcal A}_1+{\mathcal A}_2) $, $ j=1/2({\mathcal A}_1-{\mathcal A}_2) $. Покажем, что найденное значение для $ j_{} $ удовлетворяет неравенству из условия теоремы. Если $ {\mathcal A}_1>{\mathcal A}_2 $, то $$3\le {\mathcal A}_2 \le \sqrt{A} \le {\mathcal A}_1 \le \frac{A}{3}\ \Rightarrow \ {\mathcal A}_1 -{\mathcal A}_2 \le \frac{A}{3} -3 \ \Rightarrow \ 0 \le j \le \frac{A/3 -3}{2} \ , $$ т.е. целое число $ j_{} $ удовлетворяет ограничению $ j \le \left\lfloor (A-9)/6 \right\rfloor $. ♦ !!П!! **Пример.** Факторизовать число $ A=792019 $. **Решение.** Заметим, что число, составляющее полный квадрат, не может оканчиваться на $ 2,3,7 $ или $ 8_{} $; если оканчивается на $ 5_{} $, то должно оканчиваться на $ 25_{} $; если оканчивается на $ 0_{} $, то должно оканчиваться на $ 00_{} $. Эти тривиальные соображения позволяют сразу же отбросить из рассмотрения первые числа последовательности $ \{A_j\} $: $$ A_1=792020,\ A_2=792023,\ A_3=792028, A_4=792035 \ .$$ Далее, $ A_5=792044=2^2\cdot 198011 $, и число $ 198011 $ не может быть полным квадратом, так как не существует двузначного числа, квадрат которого оканчивается на $ 11_{} $. Числа $ A_6=792055,\ A_7=792068,\ A_8=792083 $ не могут быть квадратами. Число $ A_9=792100=890^2 $. Согласно теореме : $ j=9,t=890 $ и $ A=881\times 899 $. К числу $ 899 $ снова применяем теорему. Удача ожидает нас уже на первом шаге: $ 899+1=30^2 $ и, следовательно, $ 899=29\times 31 $. С числом $ 881 $ дело обстоит не так хорошо: забегая вперед, скажем, что оно --- простое. Если бы мы организовали проверку этого факта по теореме, то нам пришлось бы анализировать на равенство полному квадрату $ \lfloor (881-9)/6 \rfloor = 145 $ чисел. Понятно, что проще было бы установить факт простоты последовательным перебором возможных простых делителей в пределах до $ \sqrt{881}<30 $. ♦ !!§!! Регулярный метод проверки числа на равенство полному квадрату, а также вычисления $ \lfloor \sqrt{A} \rfloor $ ☞ ((:numtheory:issquare ЗДЕСЬ)). Метод факторизации из теоремы эффективен, если факторизуемое число __близко к полному квадрату__, т.е. раскладывается на два сомножителя $ {\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_{} $ эффективно возможно по ((:crypto:attacks#метод_полларда алгоритму факторизации Полларда)). ==Функция Эйлера== **Функция Эйлера** (или **тотиент**) натурального числа $ 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 , $$ $$ \phi (81)=81-27=54 , \quad \phi (481) = 432 \ . $$ !!=>!! Если числа $ A_1,\dots ,A_K $ попарно ((numtheory#взаимно_простые_числа взаимно просты)), то $$\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) $. Теорема Эйлера является частным случаем следующего, более общего результата, известного как **((http://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%B2%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D0%B9-%D0%B8%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B5%D0%BD%D0%B8%D0%B9 формула включений-исключений))**. **Теорема.** //Пусть даны подмножества//[[Необязательно различные.]] $ 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}) \ . $$ **Доказательство** ☞ ((:incl_excl ЗДЕСЬ)). !!?!! Пусть $ N \in \mathbb N $. Определить вероятность того, что число, случайным образом выбранное из множества $ \{1,2,\dots,N\} $, будет ((:numtheory#взаимно_простые_числа взаимно просто)) с $ N_{} $. Еще пара результатов для функции Эйлера, не совсем тривиально доказываемых. !!Т!! **Теорема.** $ \displaystyle \sum_{d} \phi(d) = n $; здесь суммирование производится по всем числам $ d_{} $, являющимся делителями числа $ n_{} $. **Доказательство** ☞ ((:complex_num:circlediv ЗДЕСЬ)). !!П!! **Пример.** Для $ 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_{} $. **Доказательство** ☞ ((:modular:index#первообразный_корень ЗДЕСЬ)). ==Сравнения (модулярная арифметика) == Раздел ☞ ((:modular ЗДЕСЬ)). ---- ==Задачи== ☞ ((:numtheory:problems ЗДЕСЬ)). ==Источники== [1]. **Бухштаб А.А.** //Теория чисел.// М. Просвещение. 1966 [2]. **Honsberger R.** //Mathematical Gems II.// Mathematical Assn. of Amer. 1976 [3]. **Чебышев П.** //Теорiя сравненiй.// СПб. Типографiя Императорской Академiи Наукъ. 1901