
\newpage 

%Claude Crepeau Number Theory section

\section{Number Theory}
%=====================%

\subsection{Definitions}
%----------------------%

$$a|b \iff \exists k\in Z \,\left[ b=ak \right]$$
$$a\equiv b \pmod{n} \iff n|(a-b)$$
$$b \bmod n \iff \min \{ a>0 : a\equiv b \pmod{n} \}$$
$$b \mbox{ div } n \iff \frac{b- (b \bmod n)}{n} \iff \floor{b/n}$$
$$g = gcd(a,b)
\iff 
g|a, g|b \mbox{ and } \left[ g'|a, g'|b \implies g'|g \right]$$
$$\phi(n) = \#\{ a : 0<a<n \mbox{ and } gcd(a,n)=1 \}$$

\begin{note}
  $\phi(p) = p-1, \phi(pq) = (p-1)(q-1)$, where $p$ and $q$ are Primes.
\end{note}

\subsection{Efficient basic operations}
%-------------------------------------%
For the basic operations of $+, -, \times, \bmod, \mbox{div}$ one may 
use standard ``high school'' algorithms reducing the work load by
the following rules:

$$a
\left\{
\begin{array}{c}
+\\
-\\
\times
\end{array}
\right\}
b \bmod n = 
\left(
(a \bmod n)
\left\{
\begin{array}{c}
+\\
-\\
\times
\end{array}
\right\}
(b \bmod n)
\right)
\bmod n$$

The standard ``high school'' algorithms are precisely described in Knuth (Vol 2).
For very large numbers, special purpose divide-and-conquer algorithms may
be used for better efficiency of $\times, \bmod, \mbox{div}$.
Consult the algorithmics book of Brassard-Bratley (\cite{BB88}) for these.

\subsection{GCD calculations and multiplicative inverses}
%-------------------------------------------------------%
\begin{note}
  $gcd(a,b) = d \iff \exists_{x,y}$ such that $d = ax + by$ with $d|a$ and $d|b$.
\end{note}
The idea behind this algorithm is to maintain in each iteration
the relations $g = ax+by$ and $g' = ax'+by'$ while reducing
the value of $g$.
At the end of the algorithm, the value of $g$ is $gcd(a,b)$.
The final value of $x$
is such that $ax \equiv g \pmod{b}$. When $gcd(a,b)=1$, we find that
$x$ is the multiplicative inverse of $a$ modulo $b$.

\algo{Euclide $gcd(a,b)$}{
\label{euclide}
\step{$g\is a$, $g'\is b$, $x\is 1$, $y\is 0$, $x'\is 0$, $y'\is 1$,}
\step{{\bf WHILE} $g'>0$ {\bf DO}}
\step{$k \is g \mbox{ div } g'$,}
\step{$(\hat{g},\hat{x},\hat{y})\is (g,x,y) -k (g',x',y')$,}
\step{$(g,x,y)\is (g',x',y')$,}
\step{$(g',x',y')\is (\hat{g},\hat{x},\hat{y})$,}
\step{{\bf ENDWHILE}  }
\step{{\bf RETURN} $(g,x,y)$.}
}

\subsection{Prime Fields}
%-----------------------%
Let $p$ be a prime number.
The integers $0,1,2,...,p-1$ with operations $+ \bmod p$ et $\times \bmod p$
constitute a field $\GF{p}$ of $p$ elements.

\begin{itemize}
\item contains an additive neutral element (0)
\item each element $e$ has an additive inverse $-e$
\item contains an multiplicative neutral element (1)
\item each non-zero  element $e$ has a multiplicative inverse $e^{-1}$
\item associativity
\item commutativity
\item distributivity
\end{itemize}

\pagebreak
\paragraph{Examples}
%''''''''''''''''''%
$\GF{2}=(\BB,\oplus,\wedge)$.
$\GF{5}=(\{ 0,1,2,3,4 \}, +, \times)$ defined by
\begin{figure}[h]
\begin{center}
\begin{tabular}{|r||c|c|c|c|c|}
\hline
$+$ & 0 & 1 & 2 & 3 & 4\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 \\
\hline
1 & 1 & 2 & 3 & 4 & 0 \\
\hline
2 & 2 & 3 & 4 & 0 & 1 \\
\hline
3 & 3 & 4 & 0 & 1 & 2 \\
\hline
4 & 4 & 0 & 1 & 2 & 3 \\
\hline
\end{tabular}~~~~~~
\begin{tabular}{|r||c|c|c|c|c|}
\hline
$\times$ & 0 & 1 & 2 & 3 & 4\\
\hline\hline
0 & 0 & 0 & 0 & 0 & 0\\
\hline
1 & 0 & 1 & 2 & 3 & 4\\
\hline
2 & 0 & 2 & 4 & 1 & 3\\
\hline
3 & 0 & 3 & 1 & 4 & 2\\
\hline
4 & 0 & 4 & 3 & 2 & 1\\
\hline
\end{tabular}
\end{center}
%\caption{op\'erations de $\GF{5}$}
\end{figure}

Other kind of finite fields for numbers $q$ not necessarily prime exist.
This is studied in another section. In general we refer to $\GF{q}$ for
a finite field, but you may think of the special case $\GF{p}$ if
you do not wish to find out about the general field construction.

\subsection{Lagrange's Interpolation}
%-----------------------------------%
A polynomial over $\GF{q}$ is specified by a finite sequence $(a_n,a_{n-1},...,a_1,a_0)$
of elements from $\GF{q}$, with $a_n\neq 0$. The number $n$ is the 
degree of the polynomial.

\begin{theorem}[Lagrange's Interpolation]
Let $x_0,x_1,...,x_d$ be dinstinct elements of a field $\GF{q}$ and
$y_0,y_1,...,y_d$ be any elements of $\GF{q}$.
There exists a unique polynomial $p(x)$ over $\GF{q}$ with degree $\leq 
d$ such that $p(x_i)=y_i$ for $1\leq i\leq n$.
\end{theorem}

\algo{$Interpolation(x_0,x_1,...,x_d,y_0,y_1,...,y_d)$}{
\label{inter}
\step{
\Return
$
\left(
\begin{array}{cccc}
1 & x_0 & \ldots & x_0^d\\
1 & x_1 & \ldots & x_1^d\\
\vdots & \vdots & \ddots & \vdots\\
1 & x_d & \ldots & x_d^d
\end{array}
\right)^{-1}
\left(
\begin{array}{c}
y_0\\
y_1\\
\vdots\\
y_d
\end{array}
\right)
$
}
}

Of course the matrix inversion is to be performed over $\GF{q}$,
which means all additions, substractions and multiplications are
calculated within the field, and divisions are performed by 
multiplying with the multiplicative inverse in the field.

\pagebreak
\subsection{Application: Secret Sharing}
%--------------------------------------%

Suppose Alice wants to distribute a secret $S$ among $n$ people
$P_{1},P_{2},\ldots,P_{n}$ in such a way that any $k$ of them
can recover the secret from their joint information, while
it remains perfectly secret when any $k-1$ or less of them get together.
This is what we call a $[n,k]$-secret sharing scheme.

Let's be a bit more formal. Let $S$ be Alice's secret from the finite
set $\{0,1,2,\ldots,M\}$ and let $p$ be a prime number greater than 
$M$ and $n$, the number of share holders. Shamir's construction of a
$[n,k]$-secret sharing scheme is as follows.

\algo{SSSS$(S)$}{
\label{SSSS}
\step{$a_{0} \is S$,}
\step{{\bf FOR} $i:=1$ {\bf TO} $k$ {\bf DO} $a_{i} \is uniform(0..p-1)$}
\step{{\bf FOR} $j:=1$ {\bf TO} $n$ {\bf DO}}
\step{$s_{i} \is a_{k} j^k+ a_{k-1} j^{k-1}+\ldots+a_{1} j+a_{0} 
\bmod p$}
\step{{\bf ENDFOR}}
\step{{\bf RETURN} $s_{1},s_{2},\ldots,s_{n}$.}
}

Share $s_{j}$ is given to $P_{j}$ secretly by Alice.
In order to find $S$, $k$ or more people may construct
the matrix from Lagrange's theorem from the distinct
values $x_{j}=j$ and find the unique $(a_{0},a_{1},\ldots,a_{k})$
corresponding to their values $y_{j}=s_{j}$.

\begin{theorem}
For $0\leq m \leq n$, distincts $j_{1},j_{2},\ldots,j_{m}$ and any
$s_{j_{1}},s_{j_{2}},\ldots,s_{j_{m}}$
$$\entr{S|[j_{1},s_{j_{1}}],[j_{2},s_{j_{2}}],\ldots,[j_{m},s_{j_{m}}]}
=
\left\{
\begin{array}{ll}
0 & \mbox{if $m \geq k$}\\
\entr{S} & \mbox{if $m < k$}
\end{array}
\right.$$
\end{theorem}

\pagebreak
\subsection{Fast modular exponentiation}
%--------------------------------------%
The idea behind this algorithm is to maintain in each iteration
the value of the expression $x a^e \bmod n$ while reducing
the exponent $e$ by a factor 2.

\algo{$a^e \bmod n$}{
\label{expmod}
\step{$x \is 1$,}
\step{{\bf WHILE} $e>0$ {\bf DO}}
\step{{\bf IF} $e$ is odd {\bf THEN} $x\is ax \bmod n$,}
\step{$a\is a^2 \bmod n$, $e\is e \mbox{ div } 2$,}
\step{{\bf ENDWHILE}}
\step{{\bf RETURN} $x$.}
}

\subsection{Fermat-Euler}
%-----------------------%
\begin{theorem}[Fermat]
\label{Fermat}
Let $p$ be a prime number and $a$ be an integer not a multiple of $p$,
then $$a^{p-1} \equiv 1 \pmod p.$$
\end{theorem}

\begin{theorem}[Euler]
Let $n$ be an integer and $a$ another integer such that $gcd(a,n)=1$,
then $$a^{\phi(n)} \equiv 1 \pmod n.$$
\end{theorem}

\subsection{Prime numbers}
%------------------------%
To decide whether a number $n$ is prime or not
we rely on Miller-Rabin's probabilistic algorithm.
This algorithm relies on the notion of ``pseudo-primality'' base $a$.

\algo{$pseudo(a,n)$}{
\label{pseudo}
\step{{\bf IF} $gcd(a,n)\neq 1$ {\bf THEN RETURN} ``composite'',}
\step{Let $t$ be an odd number and $s$ a positive integer such that $n-1=t 2^s$}
\step{$x\is a^t \bmod n$, $y\is n-1$,}
\step{{\bf FOR } $i \is 1$ {\bf TO } $s$}
\step{{\bf IF} $x=1$ {\bf AND} $y= n-1$ {\bf THEN RETURN} 
``pseudo'',}
\step{$y \is x$, $x\is x^2 \bmod n$,}
\step{{\bf ENDFOR} }
\step{{\bf RETURN} ``composite''.}
}

Rabin showed that if $n$ is prime, then $pseudo(a,n)$ returns ``pseudo''
for all $a$, $0<a<n$.
He also showed that if $n$ is composite, then $pseudo(a,n)$ returns 
``composite'' for at least $3n/4$ of the values of $a$, $0<a<n$.

\begin{theorem}
$$\#\{ a : Pseudo(a,n)=\mbox{``pseudo''} \}
\left\{
\begin{array}{lll}
= \phi(n) & = n-1 & \mbox{if $n$ is prime}\\
\leq \phi(n)/4 & \leq (n-1)/4 & \mbox{if $n$ is composite.}
\end{array}
\right.$$
\end{theorem}
To increase the certainty we may repeat the above algoritm as follows.

\algo{Miller-Rabin $prime(n,k)$}{
\label{prem}
\step{{\bf FOR } $i \is 1$ {\bf TO } $k$}
\step{Pick a random element $a$, $0<a<n$,}
\step{{\bf IF} $pseudo(a,n)=$ ``composite'' {\bf THEN RETURN} 
``composite'',}
\step{{\bf ENDFOR}}
\step{{\bf RETURN} ``prime''.}
}

We easily deduce that if $n$ is prime, then $prime(n,k)$ always 
returns ``prime'' and that
if $n$ is composite, then $prime(n,k)$ returns ``composite'' with
probability at least $1-(1/4)^k$.
Thus when the algorithm $prime$ returns ``composite'', it is always
a correct verdict. However
when it returns ``prime'' it remains a very small probability that
this verdict is wrong.

If we want a random prime of a given size, we use the following
theorem to estimate the number of integers we must try before
finding a prime.
Let $\pi(n) = \#\{ a : 0<a\leq n \mbox{ and } a \mbox{ is prime}\}$.

\begin{theorem}
$\displaystyle \lim_{n\rightarrow\infty} \frac{\pi(n) \log n}{n} = 1$
\end{theorem}


\subsection{Primitive Elements}
%-----------------------------%
In all finite fields $\GF{q}$ (and some groups in general) there 
exists a {\em primitive element}, that is an element $g$  of the field
such that $g^1, g^2,...,g^{q-1}$ enumerate all of the $q-1$ non-zero
elements of the field.
We use the following theorem to find a primitive element over $\GF{q}$.

\begin{theorem}
Let $l_1,l_2,...,l_k$ be the prime factors of $q-1$ and $m_i = 
(q-1)/l_i$ for $1 \leq i \leq k$.
An element $g$ is {\em primitive} over $\GF{q}$ if and only if
\begin{itemize}
\item[$\bullet$] $g^{q-1} = 1$
\item[$\bullet$] $g^{m_i} \neq 1$ for $1 \leq i \leq k$
\end{itemize}
\end{theorem}

\algo{$Primitive(q)$}{
\label{prim}
\step{Let $l_1,l_2,...,l_k$ be the prime factors of $q-1$ and $m_i = 
\frac{q-1}{l_i}$ for $1 \leq i \leq k$,}
\step{{\bf REPEAT}}
\step{pick a random non-zero element $g$ of $\GF{q}$,}
\step{{\bf UNTIL} $g^{m_i} \neq 1$ for $1 \leq i \leq k$,}
\step{{\bf RETURN} $g$.}
}

We use the following theorems to estimate the number of field elements
we must try in order to find a primitive element.

\begin{theorem}
$\#\{ g : g \mbox{ is a primitive element of $\GF{q}$} \} = \phi(q-1)$.
\end{theorem}

\begin{theorem}
$\displaystyle \liminf_{n\rightarrow\infty} \frac{\phi(n) \log \log n}{n} = e^{-\gamma}$
\end{theorem}

\paragraph{Example:}
%-------------------%
2 is a primitive element of $\GF{5}$ since
$\{ 2,2^2,2^3,2^4 \} = \{ 2,4,3,1 \}$.

%$010$ is a primitive element of $\GF{2^3}$ as shown by the following 
%table:
%
%$$
%\begin{tabular}{|c||c|c|c|c|c|c|c|c|}
%\hline
%$x$       & $-\infty$ &   0 &   1 &   2 &   3 &   4 &   5 &   6\\
%\hline
%~$(010)^x$ &       000 & 001 & 010 & 100 & 011 & 110 & 111 & 101\\
%\hline
%\end{tabular}
%$$

\paragraph{Factoring $q-1$...}
%''''''''''''''''''''''''''''%
In general, it may be difficult to factor $q-1$.
It will therefore be only possible to find a primitive element
for fields $\GF{q}$ for which the factorization of $q-1$ is known.
However, if we are after a large field with a random number of 
elements Eric Bach has devised an efficient probabilistic algorithm
to generate random integers of a given size with known factorization.
Suppose we randomly select $r$ with its factorization using Bach's 
algorithm. We may check whether $r+1$ is a prime or a prime power.
In this case a finite field of $r+1$ elements is obtained and a 
primitive element may be computed.

\subsection{Quadratic Residuosity}
%--------------------------------%
\label{QR}
Quadratic residues modulo $n$ are the integers with an integer
{\em square root} modulo $n$:
$$QR_n = \{ a : gcd(a,n)=1, \exists r [a \equiv r^2 \pmod n] \}$$
$$QNR_n = \{ a : gcd(a,n)=1, \forall r [a \not\equiv r^2 \pmod n] \}$$
\paragraph{Example:}
%''''''''''''''''''%
$$QR_7= \{ 1,4,2 \}$$
$$QNR_7=\{ 3,5,6 \}$$
since
$$\{ 1^2, 2^2, 3^2, 4^2, 5^2, 6^2 \} \equiv \{ 1,4,2 \} \pmod 7.$$

\begin{theorem}
Let $p$ be an odd prime number
$$\#QR_p = \# QNR_p = (p-1)/2.$$
\end{theorem}
This result steers from the result that if $a \in {\bbZ_p}^*$, then
$a \in QR_p$ iff $a = \alpha^i \; mod \; p$, where $i$ is an {\it even}
integer and $\alpha$ a generator of ${\bbZ_p}^*$.

For an odd prime number $p$, we define the Legendre symbol as
$$
\jacobi{a}{p} =
\left\{
\begin{array}{rl}
+1 & \mbox{if $a\in QR_p$}\\
-1 & \mbox{if $a\in QNR_p$}\\
0 & \mbox{if $p|a$}\\
\end{array}
\right.
$$

\begin{theorem}
Let $p$ be a prime number and $a$ be an integer,
then $$a^{(p-1)/2} \equiv \jacobi{a}{p} \pmod p.$$
\end{theorem}
For any integer $n=p_1 p_2 ... p_k$,
we define the Jacobi symbol (a generalisation of the Legender symbol) as
$$
\jacobi{a}{n}= \jacobi{a}{p_1} \jacobi{a}{p_2} ... \jacobi{a}{p_k}
$$

\paragraph{Proprerties}
%'''''''''''''''''''''%
$$\jacobi{1}{n}= +1$$
$$\jacobi{ab}{n}=\jacobi{a}{n}\jacobi{b}{n}$$
$$\jacobi{a}{n}=\jacobi{a \bmod n}{n}$$
For $n$ odd
$$\jacobi{-1}{n}= (-1)^{(n-1)/2}$$
$$\jacobi{2}{n}= (-1)^{(n^2-1)/8}$$
For $a,n$ odd and such that $gcd(a,n)=1$
$$\jacobi{a}{n} \jacobi{n}{a} = (-1)^{(n-1)(a-1)/4}$$

\algo{$Jacobi(a,n)$}{
\label{jacobi}
\step{
\begin{tabbing}
\If $a \leq 1$ \= \Then \= \Return a \\
               \> \Else \> \If $a$ is odd \= \Then \= \If $a \equiv n \equiv 3 \pmod 4$\\
               \>       \>                \>       \> \Then \= \Return $-Jacobi(n \bmod a,a)$\\
               \>       \>                \>       \> \Else \> \Return $+Jacobi(n \bmod a,a)$\\
               \>       \>                \> \Else \> \If $n \equiv \pm 1 \pmod 8$\\
               \>       \>                \>       \> \Then \> \Return $+Jacobi(a/2,n)$\\
               \>       \>                \>       \> \Else \> \Return $-Jacobi(a/2,n)$
\end{tabbing}
}
}
This algorithm runs in $O((lg \; n)^2)$ bit operations.

\begin{definition}
 $$J_n := \{a \in \bbZ_n \; | \; \jacobi{a}{n} = 1 \}$$
\end{definition}

\begin{theorem}
\label{thmProductQR}
Let $n$ be a product of two distinct odd primes $p$ and $q$.  Then for an $a \in J_n$ 
we have that  $a \in QR_n$ iff $\jacobi{a}{p} = 1$.
\end{theorem}

\subsection{Quadratic Residuosity problem}

\begin{definition}
The {\it quadratic residuosity problem} (QRP) is the following:  given an odd
composite integer $n$ and $a \in J_n$, decide whether or not $a$ is a quadratic
residue modulo $n$.
\end{definition}

\begin{definition}(pseudosquare)
Let $n \geq 3$ be an odd integer.  An integer $a$ is said to be a {\it pseudosquare modulo n} if
$\jacobi{a}{n} = 1$ and $a \in QNR_n$.
\end{definition}

\hspace{-0.6cm}{\bf Remark: } If n is a prime, then it is easy to decide if $a$ is
in $QR_n$, since $a \in QR_n$ iff $a \in J_n$, and the Legendre symbol
can be efficiently computed by algorithm \ref{jacobi}.\\
If $n$ is a product of two distinct odd primes $p$ and $q$, then it follows from
theorem \ref{thmProductQR} that if $a \in J_n$, then $a \in QR_n$ iff
$\jacobi{a}{p} = 1$.

If we can factor $n$, then we can found out if $a \in QR_n$ by computing the 
Legender symbol $\jacobi{a}{p}$.\\
If the factorization of $n$ is unknown, then there is no efficient algorithm known
to decide if $a \in QR_n$.

\hspace{-0.6cm} This leads to the following Goldwasser-Micali probabilistic encryption algorithm:

\hspace{-0.6cm} {\bf Init: } $Alice$ starts by selecting two large distinct prime numbers $p$ and $q$.  
She then
computes $n = pq$ and selects a pseudosquare $y$.   $n$ and $y$ will be public, $p$ and $q$ private.

\algo{Goldwasser-Micali probabilistic encryption}{
\step{ Represent message $m$ in binary ($m = m_1m_2 \ldots m_t$).}
\step{ {\bf FOR} $i = 1$ {\bf TO} $t$ {\bf DO}}
\step{ \hspace{0.6cm} {\bf Pick} $x \in_R {\bbZ_n}^*$}
\step{ \hspace{0.6cm} {\bf IF} $m_i = 1$ {\bf THEN} $c_i \leftarrow y x^2 \; mod \; n$}
\step{ \hspace{0.6cm} {\bf ELSE} $c_i \leftarrow x^2 \; mod \; n$}
\step{ {\bf RETURN} $c = c_1c_2 \ldots c_t$}
}

\algo{Goldwasser-Micali decryption}{
\step{ {\bf FOR} $i = 1$ {\bf TO} $m$ {\bf DO}}
\step{ \hspace{0.6cm} $e_i \leftarrow \jacobi{c_i}{p}$ using algo \ref{jacobi}.}
\step{ \hspace{0.6cm} {\bf IF} $e_i = 1$ {\bf THEN} $m_i \leftarrow 0$}
\step{ \hspace{0.6cm} {\bf ELSE} $m_i \leftarrow 1$}
\step{ {\bf RETURN} $m = m_1m_2 \ldots m_t$}
}



\subsection{Extracting Square Roots modulo $n$}
%---------------------------------------------%
\label{SQUARE}
\begin{theorem}
For prime numbers $p\equiv 3 \pmod 4$ and $a\in QR_p$,
we have that $r = a^{(p+1)/4} \bmod p$ is a square root of $a$.
\end{theorem}

\begin{proof}
\begin{eqnarray*}
(a^{(p+1)/4)})^2 &= & a^{(p+1)/2} \\
               &= & a^{(p-1)/2}\cdot a \; mod \; p \\
               &= & a \; mod \; p \; \; (Fermat, \; sec. \ref{Fermat})
\end{eqnarray*}
\end{proof} 

For prime numbers $p\equiv 1 \pmod 4$ and
$a\in QR_p$, there (only) exists an efficient {\it probabilistic}
algorithm.
We present one found in the algorithmics book of Brassard-Bratley
(\cite{BB88}):

\algo{rootLV(x, p, VAR y, VAR success)}{
\step{ $a \leftarrow uniform(1 \ldots p-1)$}
\step{ {\bf IF} $a^2 \equiv x \; mod \; p$  \{very unlikey\} }
\step{ {\bf THEN} $success \leftarrow true$, $y \leftarrow a$}
\step{ {\bf ELSE} compute $c$ and $d$ such that $0 \leq c \leq p - 1, 0 \leq d \leq p-1$, \\ 
                  $\; \; \;$  and $(a + \sqrt{x})^{(p-1)/2} \equiv c + d\sqrt{x} \; mod \; p$ }
\step{ \hspace{0.6cm} {\bf IF} $d = 0$ {\bf THEN} $success \leftarrow false$}
\step{ \hspace{0.6cm} {\bf ELSE} $c = 0$, $success \leftarrow true$,} 
\step{ \hspace{1.7cm} compute $y$ such that $1 \leq y \leq p - 1$ and $d \cdot y \equiv 1 mod p$}
}

\begin{definition}[SQROOT]
\label{SQROOT}
The square root modulo $n$ problem (SQROOT) can be stated as follows:\\
given a composite integer $n$ and $a \in QR_n$, find a square root
of $a \; mod \; n$.
\end{definition}

\begin{theorem}
SQROOT is polynomialy equivalent to FACTORING (see def. section
\ref{FACTORING}).
\end{theorem}


\subsection{Chinese Remainder Theorem}
%------------------------------------%
\begin{theorem}[Chinese Remainder]
\label{chinese}
Let $m_1,m_2,...,m_r$ be $r$ positive integers such that $gcd(m_{i},m_{j})=1$ for
$1\leq i < j \leq r$ and let $a_1,a_2,...,a_r$ be integers.
The system of $r$ congruences $x \equiv a_{i} \pmod {m_{i}}$, for 
$1\leq i\leq r$ has a unique solution modulo $M=m_1 m_2 ... m_r$
which is given by
$$
x = \sum_{i=1}^r a_{i}M_{i}y_{i} \bmod M
$$
where $M_{i}=M/m_{i}$ and $y_{i}=M_{i}^{-1} \bmod \; m_{i}$, for
$1\leq i\leq r$.
\end{theorem}


\hspace{-0.6cm}{\bf Application:}\\
We want to solve $x^2 \equiv a \; mod \; n$ for $x$ knowing $n = pq$.\\
\begin{eqnarray*}
 {x_0}^2 &=& a \; mod \; p \\
 {x_1}^2 &=& a \; mod \; q 
\end{eqnarray*}
We solve \\
\begin{eqnarray*}
 x = x_0 \; mod \; p & &\iffimplies  p | x^2 - a \\
 x = x_1 \; mod \; q & &\underbrace{\iffimplies q | x^2 - a} \\
               & &\implies p \cdot q = n | x^2 - a \\
               & &\implies x^2 = a \; mod \; n
\end{eqnarray*}
We can now solve $x$ by the chinese remainder theorem.


%End of Claudes Number Theory section.
