\input{ca_preamble.tex}

\newcommand\Lej[2]{\left(\frac{#1}{#2}\right)}
\newcommand\cLej[2]{\left( \cfrac{#1}{#2}\right)}

\begin{document}

\lectitle{2}{������������ ������ � ��������}
\lecauthor{�.\,���������}
\date{?? �������� 2008}
\maketitle

\tableofcontents

\section {������������ ������ � ��������}

\begin {definition}
	����� \textit{p}~--- ������� �������� �����. ����� ����� $a$, �����, ��� $\GCD(a, p)=1$, ���������� {\em ������� ������� $n$}, ���� 
	\[
		\exists(x):x^{n}\equiv a\pmod{p}.
	\]
	� �������� ������ ����� $a$ ���������� ��������� ������� $n$. ��� $n=2$ ����� (�������) $a$ ���������� {\em ������������}, ��� $n=3$~--- {\em ����������}, � ��� $n=4$~--- {\em ��������������}. ��� $n=2$ ����� ������������ �������� � �������� $a$ ������ ������� (���������).
\end{definition}

���������� ������ $\ZZ^{*}_{p}=\{1, 2,\dots, p-1\}$ � �������� ��������� ��������� �� ������ $p$. ��������, ���������� ���������� ������-�� ����� � $\ZZ^{*}_{p}$,~--- ������.

\begin{example} ����� $p=7, \ZZ^{*}_{7}=\{1, 2, 3, 4, 5, 6\}$.

$1^{2}=1  \pmod{7},$

$2^{2}=4  \pmod{7},$

$3^{2}=2  \pmod{7},$

$4^{2}=2  \pmod{7},$

$5^{2}=4  \pmod{7},$

$6^{2}=1  \pmod{7}.$

����� $1,2,4$ ����� �������� ������������� ��������, � ����� $3,5,6$~--- ������������� ����������.
\end{example}

\begin {proposition}
	� $\ZZ^{*}_{p}$ ���������� ����� $\frac{p-1}{2}$ ������������ �������, ��������� � �������:
	\[
	1^2, 2^2,\dots,\frac{p-1}{2}^2.
	\]
\end {proposition}

\begin{proof} 
	������� �������, ��� ����������� ������ ����� �������� �������� ���� ��������� �� $\ZZ^{*}_{p}$. 		
	��� ���������� ��������, ���� ����������� $\ZZ^{*}_{p}$ ��� 
	$\{-\frac{p-1}{2},\dots, -2, -1, 1, 2, \dots,\frac{p-1}{2}\}$. 
	������ ����� $\exists i, j\in \ZZ^{*}_{p}: i^2\equiv j^2\pmod{p}, 0<i<j\leq\frac{p-1}{2}$. ����� ��������� 
	$x^2\equiv i^2 \pmod{p}$ ������������� �� 4 �����: $x=\pm i, \pm j$, ���� ���� �� �����, � ������ ��� 	����� �� ������ $1^2, 2^2,\dots,\frac{p-1}{2}^2$ �������� �� ������ $p$.
	����� �������, ����������� ������ $1^2, 2^2,\dots,\frac{p-1}{2}^2$ ������� �� $\frac{p-1}{2}$ 
	��������� �� ������ $p$ �����, �������������� ��� ������ � ������ $\ZZ^{*}_{p}$. 
\end{proof}

\begin {proposition}\label{prop_prim_el}
	���� $\ZZ^{*}_{p}=\{1, \theta, \theta^{2},\dots, \theta^{p-2}\}$,
	��� $\theta$~--- ����������� �������, �� ����������� ���������:

	\begin{center}
		$a=\theta^{j}$~--- ������������ ����� $\Leftrightarrow$ \textit{j}~--- ������.
	\end{center}
\end {proposition}

\begin {proof} 
	����� $a=\theta^{j}$~--- ������������ �����. ����� $\exists x: x^{2}\equiv a \pmod{p}$. ��� ��� 
	$\theta$~--- ����������� �������, ������ $\exists i: x=\theta^{i}$, ������ �������, ���
	$\theta^{2i}=\theta^{j}$, �� ���� \textit{j}~--- ������.

	� �������� �������, ����� \textit{j}~--- ������. ����� $j=2i$ ��� ���������� \textit{i}, �� ����
	$a=\theta^{2i}$. ��� ������, ��� $\exists x=\theta^{i}: x^{2}\equiv a \pmod{p}$, �� ����
	\textit{a}~--- ������������ �����.
\end{proof}

\section{������ ��������}

\begin {definition}
 ��� ������ �������� ��������� \textit{p} � ������ \textit{a} ������ �������� ������������ 	
 ��������� �������:
	\[
		\cLej{a}{p} = 
		\begin{cases}
 			0, & \text{���� } a\equiv 0 \pmod{p};\\
 			1, & \text{���� \textit{a}~--- ����� $\pmod{p}$;}\\
			-1, & \text{���� \textit{a}~--- ������� $\pmod{p}$;}
		\end{cases}
	\]
\end {definition}

\subsection {�������� ������� ��������}

\begin{proposition}
  \[
    a_{1} \equiv a \pmod{p} \Rightarrow \cLej{a}{p} = \cLej{a_{1}}{p}.
  \]
\end{proposition}

\begin{proposition}[�������� ������] 
	\[
		\cLej{a}{p} \equiv a^{\frac{p-1}{2}} \pmod{p}.
	\]
\end{proposition}

\begin{proof}
  ��� $a \equiv 0 \pmod{p}$ ����������� ��������.
	����� ����� ������� ����� ������:
	\[
	a\neq 0 \pmod{p} \Rightarrow a^{p-1} \equiv 1 \pmod{p}.
	\]
	���������� 2 ������:
	\begin{enumerate}
		\item \textit{a}~--- ������������ �����, �� ���� $\exists x: x^2 \equiv a \pmod{p}$. ����� 		
		$a^{\frac{p-1}{2}}=x^{p-1} \equiv 1 \pmod{p}$. ��������� ��������� �������� �� ����� ������� �����. 
		�� �� ����, ��� \textit{a}~--- ������������ �����, ��������, ��� $\left( \cfrac{a}{p} \right) = 1$, 
		������������� $\left( \cfrac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}$.
		\item \textit{a}~--- ������������ �������, ����� �� �����������~\ref{prop_prim_el} �������, ��� 
		$\exists j:  a=\theta^{2j+1}$, ��� $\theta$~--- ����������� �������. �����
		\[
			\begin {split}
			a^{\frac{p-1}{2}} &=\theta^{\frac{(2j+1)(p-1)}{2}}=\theta^{\frac{(2jp-2j+p-1)}{2}}\\			&=\theta^{j(p-1)+\frac{p-1}{2}}=\theta^{\frac{p-1}{2}}={\theta^{\left(p-1\right)}}^{\frac{1}{2}}=1^{\frac{1}{2}}.
			\end {split}
		\]
		��������� $x^2\equiv1 \pmod{p}$ ����� ����� ������ 2 �������: $x=\pm1$, ��, ��� ��� $\theta$~--- 	
		����������� �������, �� ������ ���� �� ������� �� $0$ �� $p-1$ ����� ������ $1$, � ���~--- 	
		�������		$p-1$. ������������� $\theta^{\frac{p-1}{2}}\equiv-1 \pmod p$, � ������
		\[
			a^{\frac{p-1}{2}}\equiv-1 \pmod{p}.
		\]
		��������, ��� $a$~--- ������������ �������, � ������� ���������:
		\[
			\cLej{a}{p}\equiv a^{\frac{p-1}{2}} \pmod{p}.
		\]
	\end{enumerate}
\end{proof}

\begin{proposition} \label{prop_product}
	\[
    \cLej{ab}{p}=\cLej{a}{p}\times\cLej{b}{p}.
  \]
\end{proposition}

\begin {proof}
  �� ������� ������:
  \[
	  \cLej{ab}{p}\equiv \left(ab\right)^{\frac{p-1}{2}} \equiv a^{\frac{p-1}{2}}  b^{\frac{p-1}{2}} \equiv \cLej{a}{p}\times\cLej{b}{p} \pmod{p}.
  \]
�� ������� ���������� �������� ������� �������� �������, ��� ���������� ��������� ����� �������� � ���������.
\end {proof}

\begin{proposition} ���� $\GCD(a, p)=1$, �� ����������� ���������:
	\[
    \cLej{a^{2}b}{p} = \cLej{b}{p}.
  \]
\end {proposition}

\begin{proof}
  �������� ����������� \ref{prop_product}:
  \[
	  \cLej{a^2b}{p}=\cLej{a^2}{p}\cLej{b}{p}.
  \]
  ��� ��� $\GCD(a, p)=1$, �� $a^2$~--- ������������ �����, � ����������� ��������.
\end{proof}

\begin{proposition} \label{prop_1/p}
  \[
	  \left.
	    \begin {aligned}
	      &\cLej{1}{p}= 1;\\
		    &\cLej{-1}{p}= {\left(-1\right)}^{\frac{p-1}{2}}.
		  \end {aligned}
	  \right.
  \]
\end{proposition}

\begin {proof}
	\begin {enumerate}
		\item ��� ��� $1^2\equiv 1 \pmod{p}$, �� $1$ �������� ������������ �������, ��� ���������� ������ 
		�������.
		\item ��� �������������� ������ ������� � �������� ������ ���������� ���������� $-1$ � �������� $a$.
	\end {enumerate}
\end {proof}

\begin{proposition} \label{prop_2/p}
	\[
    \cLej{2}{p}={\left( -1 \right)}^{\frac{p^2-1}{8}}=
	  \begin {cases}
	    1, & p \equiv \pm1 \pmod{8};\\
	    -1, & p \equiv \pm3 \pmod{8}.
	  \end {cases}
	\]
\end{proposition}
�������� ���������� ��� ��������������.

\subsection {������������ ����� ����������}

\begin {theorem}
	��� ����� ������� �������� \textit{p} � \textit{q} �����������:
	\[
		\cLej{p}{q}= {\left( -1 \right)}^{\frac{p-1}{2}\frac{q-1}{2}}\cLej{q}{p}.
	\]
\end {theorem}

������� ������� ���� �������������� ������� � 1783 ����, � ������������ �������� ������� � 1796, � ����� ��������� ������������:
\[
	\cLej{p}{q} \neq \cLej{q}{p} \Leftrightarrow 
	\begin {cases}
		p \equiv 3 \pmod{4};\\
		q \equiv 3 \pmod{4}.
	\end {cases}
\]
������� ���������� ��� ��������������. 

\subsection {�������� ���������� ������� ��������}

�������� ���������� ������� �������� �������� �����������. �� �������� �� ���������� ��� ������� �����, ��� ��� ������� ���������� ����� �� ������� �����������.

\paragraph{��������}
\begin{enumerate}
	\item ���� $a<0$, ��, �������� ����������� \ref{prop_product} � \ref{prop_1/p}, �������� 
	$\cLej{a}{p}=\cLej{-a}{p}\times \left(-1\right)^\frac{p-1}{2}$.
	\\ �������������� $a:=-a$.
	\item $a:=a \mod p$ (��������� $\mod$ ��� ������ �� ����� ���������� ������ �������).
	\item ������������ $a$ �� ������� �����������:
	\[
		a=p^{k^1}_{1}\times\dots\times p^{k^s}_{s} \text{, ��� $p_j$~--- ������� ����� ��� $j=1,\dots,s$}.
	\]
	����� �������� ����������� \ref{prop_product}
	\[
		\Lej{a}{p}=\Lej{p_1}{p}^{k_1}\times\dots\times\Lej{p_s}{p}^{k_s}
	\]
	��������� � ������ ������� $k_j$ ����� �������, ��� ��� ��� ��� ����� 1. 
	\item ��� ���� $p_j=2$ � �������� $k_j$ ��������� $\cLej{2}{p}$ �� ����������� \ref{prop_2/p}.
	\item ��� ���� $p_j\neq2$ � �������� $k_j$ ��������� ������������ ����� ����������:
	\[
		\Lej{p_j}{p} = {\left(-1\right)}^{\frac{p-1}{2} \frac{p_j-1}{2}}\Lej{p}{p_j}.
	\] 
	��������� �������� ��� ������� $\cLej{p}{p_j}$.
\end{enumerate}

�������� ����� ������������� ��� ���� ������, �������������� ��������, ����� ��������� ������ ��������.

\begin{example} ��������� $\cLej{126}{53}$. �������� � ����� ��������� ��������� ���� ������� (��� ������� ��������� ����������� ������ ��������������� ����� ���������):
\[
	\begin{split}
\cLej{126}{53}&\stackrel{2}=\cLej{20}{53}\stackrel{3}=\cLej{2}{53}^2\times\cLej{5}{53}=\cLej{5}{53}\stackrel{5}=\cLej{53}{5}\left(-1\right)^{\frac{53-1}{2}\frac{5-1}{2}}\\
&=\cLej{53}{5}\stackrel{2}=\cLej{3}{5}\stackrel{5}=\cLej{5}{3}\left(-1\right)^{\frac{3-1}{2}\frac{5-1}{2}}\stackrel{2}=\cLej{2}{3}\stackrel{\text{���-�� \ref{prop_2/p}}}=\left(-1\right)^{\frac{9-1}{8}}\\
&=-1.
	\end{split}
\]
\end{example}

\section {������ �����}
\begin{definition}
	����� $n$~--- ��������, ������ ������� � $n=p^{k_1}_1\dots p^{k_s}_s$, ��� $p_1,\dots,p_s$~--- 	
	������� �����. ����� ������ ����� $\cLej{a}{n}$ ������������ ��������� ����������:
	\[
		\cLej{a}{n}={\cLej{a}{p_1}}^{k_1}\times\dots\times{\cLej{a}{p_s}}^{k_s}.
	\]
\end{definition}
������ ����� �������� ���������� ������� ��������, � ������ �������� �������� ������� ������� ������� �����.

\subsection {�������� ������� �����}
�������� ������� ����� ����� �������� �� ��������������� ������� ������� ��������. �� �������������� ����������� �������� � �������� ���������������� ����������.

\begin {proposition}
  \[
	  a_1\equiv a \pmod{n} \Rightarrow \cLej{a_1}{n}=\cLej{a}{n}.
	\]
\end {proposition}

\begin {proposition}
	\[
	  \cLej{ab}{n}=\cLej{a}{n}\cLej{b}{n}.
	\]
\end {proposition}

\begin {proposition}
	\[
	  \GCD(a, n)=1 \Rightarrow \cLej{a^2b}{n}=\cLej{b}{n}.
	\]
\end {proposition}

\begin {proposition}
\[
	\left.
	  \begin {aligned}
	    &\cLej{1}{n}= 1;\\
		  &\cLej{-1}{n}= {\left(-1\right)}^{\frac{n-1}{2}}.
		\end {aligned}
	\right.
	\]
\end {proposition}

\begin {proposition}
	\[
	  \cLej{2}{n}={\left(-1\right)}^{\frac{n^2-1}{8}}.
	\]
\end {proposition}	

\subsection{��������� ������������� ������ ����������}

������������ ����� ���������� ��� ������� �������� ���������� �� ������ ����� ��������� ����������:
\begin {theorem}
	��� ����� �������� \textit{m} � \textit{n} �����������:
	\[
		\cLej{m}{n}= {\left( -1 \right)}^{\frac{m-1}{2}\frac{n-1}{2}}\cLej{n}{m}.
	\]
\end {theorem}

\subsection{�������� ���������� ������� �����}

��� ���������� ������� ����� � �������� ���������� ������� �������� ����������� ������� ���, ������������� � ���������� ������� ����� � ������������ �������� �������� �������� �����������.

\begin {example}
  ��������� ������ ����� $\cLej{131}{255}$. ������������� ������������ ���������� ���������� ������� 
  �������� � ��� ����������� �� ���������� ������� �����. ��� ������� ��������� ����� ����������� 
  ������ ����� ���������.
  ��� ����������� ���������� ����� 255 �� ������� �����������:
  \[
    255=3\times 5 \times 17.
  \]
  �������� ��������� �������� � ��� �������� ����:
  \[
    \cLej{131}{255}\stackrel{0}=\cLej{131}{3}\times\cLej{131}{5}\times\cLej{131}{17}.
  \]
  ��������� �����������:
  \[
    \begin {split}   	  
      &\cLej{131}{3}\stackrel{2}=\cLej{2}{3}\stackrel{4}=
      \left(-1\right)^\frac{3^2-1}{8}=-1;\\
      &\cLej{131}{5}\stackrel{2}=\cLej{1}{5}\stackrel{\text{���-�� \ref{prop_1/p}}}=1;\\
      &\cLej{131}{17}\stackrel{2}=\cLej{12}{17}\stackrel{3}=
      \cLej{2}{17}^2\times\cLej{3}{17}=\cLej{3}{17}
      \stackrel{5}=\cLej{17}{3}\times\left(-1\right)^{\frac{17-1}{2}\frac{3-1}{2}}
      =\cLej{17}{3}\stackrel{2}=\cLej{2}{3}\stackrel{4}=-1.
    \end {split}
  \]
  ����������� ���������� �������� � �������� �������:
  \[
    \cLej{131}{255}=(-1)\times 1\times (-1)=1.
  \]
\end {example}

\begin {thebibliography}{0}
	\bibitem{} {\it ����������~�.�.} ������ ������ �����.~--- �.--�., �����������, 1952. 
\end {thebibliography}

\end{document}