\input{ca_preamble.tex}

\begin{document}

\lectitle{}{Простые числа}
\lecauthor{М.\,Гусева}
\date{18 октября 2008}
\maketitle

\tableofcontents


\section{О распределении простых чисел}

Обозначим $\pi(x)$ количество простых чисел, не превосходящих $x$.

\begin{theorem}[Чебышев, 1850 г.] \label{th_Chebyshev}
Существуют такие положительные константы $с_1$, $с_2$, что для любого $n > 1$
$$\frac{c_{1}x}{\ln x}<{\pi}(x)<\frac{c_{2}x}{\ln x}$$ 
\end{theorem}

\begin{corollary}\label{cor11}
Пусть $p_{n}$ --- $n$-е простое число, тогда существуют такие положительные
$c_{3}$, $c_{4}$, что для всех достаточно больших $n$
\begin{equation}
 c_{3}n \ln n < p_{n} < c_{4}n \ln n. \label{f_p_n}
\end{equation}
\end{corollary}

\begin{proof}
Используя теорему \ref{th_Chebyshev}, можем записать неравенство 
$$
\frac{c_{1}x}{ \ln x}<{\pi}(x)<\frac{c_{2}x}{ \ln x}.
$$
Подставим $x = p_{n}$:
$$
 \frac{c_{1} p_{n}}{  \ln p_{n}} < {\pi}(p_{n})<\frac{c_{2}p_{n}}{ \ln p_{n}},
 $$
где
$$ {\pi}(p_{n}) = n.$$
Таким образом,
\begin{equation}
 \frac{c_{1} p_{n}}{  \ln p_{n}} < n <\frac{c_{2}p_{n}}{ \ln p_{n}}. \label{f_cheb_corollary_n_in}
\end{equation}

Докажем правую часть неравенства \Ref{f_p_n}.
Из \Ref{f_cheb_corollary_n_in} получаем
$$ 
n < \frac{c_{2}p_{n}}{ \ln p_{n}},
$$
откуда
$$
p_{n} > \frac{n \ln n}{c_{2}}  = c_{4}n \ln n.
$$


Докажем левую часть неравенства \Ref{f_p_n}. 
Логарифмируя левое из неравенств \Ref{f_cheb_corollary_n_in}, получаем
Рассмотрим
$$  
\ln n >
\ln \frac{c_{1}p_{n}}{ \ln p_{n}} =  \ln c_{1}+  \ln \frac{p_{n}}{ \ln p_{n}} 
=\ln c_{1} +  \ln p_{n}- \ln\ln p_{n}.
$$
Однако $\ln c_{1} +  \ln p_{n}- \ln ( \ln p_{n}) > c_{3} \ln p_{n}$ для некоторого $c_3$, поскольку 
$$
 \lim\limits_{n->\infty}  \frac{ \ln c_{1} + \ln p_{n}- \ln ( \ln p_{n})}{c_{3} \ln p_{n}} = 1.$$
%$$ \frac{c_{1}c_{3}p_{n}}{ \ln (n)} < \frac{ c_{1}p_{n} }{  \ln (p_{n}) } < n.$$
\end{proof}

\begin{corollary}
Существуют такие положительные константы $c_6$ и $c_7$, что
$$
c_{6} \ln n< p_{n+1}- p_{n} < c_{7} \ln n.
$$
\end{corollary}
\begin{proof}
По следствию \ref{cor11} имеем $c_{3}n\ln n < p_{n} < c_{4}n\ln n.$ 
Для $p_{n+1}$ имеем 
$$ c_{3}(n+1) \ln (n+1) < p_{n+1} < c_{4}(n+1) \ln (n+1)  \eqno(*) $$
Далее, $$ -c_{4}n \ln n < -p_{n} < -c_{3}n \ln n     \eqno(**) $$
Сложим $(*)$ и $(**)$:
$$ c_{3}(n+1) \ln (n+1) - c_{4}n \ln n < p_{n+1}- p_{n} < c_{4}(n+1) \ln (n+1) - c_{3}n \ln n. $$
Так как $ \ln (n+1) >  \ln (n)$, то 
$$ (c_{4} -c_{3}) \ln (n) + c_{3} \ln n < p_{n+1}- p_{n} < (c_{4} - c_{3})n \ln (n) + c_{4} \ln n. $$
Так как $c_{4} < c_{3}$, то $c_{4} - c_{3} < 0$, то получаем
$$ c_{3} \ln n < p_{n+1} - p_{n} < c_{4}n \ln n. $$
%Переобозначаем константы $c_{3}, c_{4}$ на $c_{6}, c_{7}$.
\end{proof}

\begin{theorem}[Адамар, Валле-Пуссен, 1896; элементарное доказательство --- Серберг, 1949]
$$\pi(x)\sim \frac{x}{\ln x}\qquad x \to \infty.$$
\end{theorem}


\section{Проверка простоты числа}

\subsection{Решето Эратосфена}

Это алгоритм нахождения  простого  числа при помощи перебора всех простых чисел до заданного n.
Сложность  $O(\sqrt{n} \log ^2n)$.


\subsection{Критерий Вильсона}

\begin{theorem}[Э. Варинг, 1770]
Пусть $n$ --- целое число, $n\ge 2$.
Для того, чтобы $n$ было простым необходимо и достаточно, чтобы 
$(n-1)! \equiv -1 \pmod n$.
\end{theorem}

\subsection{Малая теорема Ферма и числа Кармайкла}

\begin{theorem}
Пусть $p$ --- простое и $\GCD(a, p)=1$, тогда 
\begin{equation} \label{f_Ferma_smThe}
a^{p-1}\equiv 1 \pmod{p}.   
\end{equation}
\end{theorem}
\begin{proof}
Доказательство следует из свойств группы $Z^{*}_{p}$, состоящей из чисел $1,2,\ldots,p-1$ c операцией умножения по модулю $p$. 
Действительно, порядок любого элемента $a$ должен делить порядок группы, поэтому $a^{p-1}\equiv 1 \pmod p$.
\end{proof}
Проверка \Ref{f_Ferma_smThe} для заданного числа $p$ не требует больших вычислений, но, к сожалению, утверждение, обратное
малой теореме Ферма, неверно. Более того, имеются составные числа $p$, обладающие свойством  \Ref{f_Ferma_smThe} для любого
целого $a$, взаимно простым с $p$. Эти числа называются числами Кармайкла.

\begin{definition}
Целое $n$ ($n\ge 2$) называется {\em псевдопростым по основанию} $a$ $(1<a<n)$, если $\GCD(a,n)=1$ и $a^{n-1}\equiv 1 \pmod n.$
\end{definition}

\begin{example}
$$
\begin{narrowarray}{ll}
a = 2, & n= 341 = 11\cdot 31, \\
a = 3, & n= 91  = 7\cdot 13,  \\
a = 5, & n= 217 = 7\cdot 31, \\
a = 7, & n= 25 = 5\cdot 5.
\end{narrowarray}
$$
\end{example}

\begin{definition}
Составное $n$ называется {\em числом Кармайкла}, если оно псевдопростое по любому основанию $a$  $(1<a<n)$.
\end{definition}

%\begin{theorem}
%Числa Кармайкла существуют.
%\end{theorem}

\begin{example}
 $$561= 3\cdot11\cdot17$$
% $$a = 3; n= 91 = 7\cdot13$$ 
\end{example}

\begin{theorem}[Кармайкл, 1912]\ 

%$n$ --- нечетное составное. Если

\begin{enumerate}
\item[\rm 1.] Число Кармайкла свободно от квадратов.
\item[\rm 2.] Если $n = p_1 \cdot p_2 \cdot \ldots \cdot p_k$, где 
$p_1, p_2,\dots, p_k$ --- попарно различные простые числа, то для того, чтобы $n$ было числом Кармайкла 
необходимо и достаточно, чтобы $(n-1)\divv (p_i-1)$ $(i= 1, \ldots ,k)$.   
\item[\rm 3.] Если $n = p_1 \cdot p_2 \cdot \ldots \cdot p_k$ --- число Кармайкла, где 
$p_1, p_2,\dots, p_k$ --- попарно различные простые числа, то $k\geq 3$.
\end{enumerate}
\end{theorem}

\begin{proof}
Рассмотрим сначала несколько вспомогательных утверждений.

\begin{proposition}[Теорема о разложении мультипликативной группы кольца $Z_m$.]\label{prop_Karm1}
Если $m = m_1, m_2,\ldots , m_s$, где $m_i$ попарно взаимно просты, то $Z^{*}_m\cong\ Z^{*}_{m_1} \times\ldots \times Z^{*}_{m_s}$.
\end{proposition}
%\begin{proof}
%$Z^{*}_m \cong Z^{*}_{m_1} \otimes\ldots \otimes Z^{*}_{m_s} =  Z^{*}_{m_1}\times \ldots \times Z^{*}_{m_s}$.
%\end{proof}

\begin{proposition}\label{prop_Karm2}
Группа $Z^{*}_n$ циклическая для всех $n \geq 1$.
\end{proposition}

Перейдем к доказательству теоремы.

1.

2. Пусть $n = p^{e_1}\ldots p^{e_r}$  разложение n на простые числа. По
утверждению \ref{prop_Karm1} имеем изоморфизм групп $Z^{*}_{n} \rightarrow Z^{*}_{p^{e_1}_{1}} \times \ldots \times Z^{*}_{p^{e_r}_{r}}$
Поэтому, если для любого $a\in Z^{*}_{n}$ выполняется $a^{n-1} = 1$, то и для любого $a_i\in Z^{*}_{p^{e_i}_{i}} $
выполняется $a^{n-1}_i = 1$. По утверждению \ref{prop_Karm2} группа $Z^{*}_{p^{e_i}_{i}}$ циклическая, т.е. в ней имеется
элемент $a_i$ порядкa $|Z^{*}_{p^{e_i}_{i}}| = \Phi(p^{e_i}_{i}) = p^{e_i-1}_{i}(p_i-1)$. Поэтому $n - 1$ делится на этот порядок,
а значит $e_i = 1$ и $n - 1$ делятся на $p_i - 1$.
Наоборот, если $e_i = 1$ и $n - 1$ делится на $p_i - 1$ при всех i, то для любого $a_i \in Z^{*}_{p}$
выполняется $a^{n-1}_{i}=1$. Значит, для любого $a \in Z^{*}_{n}$ выполняется $a^{n-1} = 1$.


3. Предположим, что $n$ --- число Кармайкла и $n = pq$, где $p, q$  различные простые
числа. Тогда $n - 1$ делится на $p - 1$ и $q - 1$. Имеем $n - 1 = (p - 1)q + (q - 1)$. Тогда $p - 1$
делится на $q - 1$. Аналогично $q - 1$ делится на $p - 1$, откуда $p = q$. Противоречие. 
\end{proof}

\end {document}