\documentclass[11pt, francais]{smfart}
\usepackage{amsfonts, amssymb, amsmath, latexsym}
\usepackage{mathptmx}
\usepackage[frenchb]{babel}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{textcomp}

\pagestyle{empty}

\input xy
\xyoption{all}

\addtolength{\hoffset}{-25mm}
%\addtolength{\voffset}{-10mm}
\addtolength{\topmargin}{-40mm} \addtolength{\headsep}{5mm}
\addtolength{\textwidth}{50mm} \addtolength{\textheight}{65mm}

\newcommand{\A}{\mathrm{A}}
\newcommand{\E}{\mathrm{E}}
\newcommand{\K}{\mathrm{K}}
\newcommand{\rP}{\mathrm{P}}
\newcommand{\T}{\mathrm{T}}
\newcommand{\B}{\mathrm{B}}
\newcommand{\M}{\mathrm{M}}
\newcommand{\V}{\mathrm{V}}
\newcommand{\F}{\mathrm{F}}
\newcommand{\N}{\mathrm{N}}
\newcommand{\Q}{\mathrm{Q}}
\newcommand{\U}{\mathrm{U}}
\newcommand{\Ir}{\mathrm{I}}
\newcommand{\Sr}{\mathrm{S}}
\newcommand{\C}{\mathrm{C}}
\newcommand{\X}{\mathrm{X}}
\newcommand{\D}{\mathrm{D}}
\newcommand{\Lr}{\mathrm{L}}

\thispagestyle{empty}

\begin{document}
\noindent \textbf{Alg\`ebre et Th\'eorie des nombres - Printemps 2008} \hfill \textbf{Universit\'e Claude Bernard Lyon 1}
\vspace{0.3cm}
\hrule

\vspace{0.7cm}

\begin{center} {\bfseries \scshape 2. Congruences et petit th\'eor\`eme de Fermat} \end{center}

\vspace{0.8cm}
\noindent \textbf{Exercice 1.} \'Ecrire les tables de l'addition et de la multiplication dans $\mathbb{Z}/n\mathbb{Z}$ pour $n=5$, $n=6$, $n=7$ et $n=8$. Dans chaque cas, d\'eterminer tous les \'el\'ements inversibles, puis tous les \'el\'ements $\alpha$ de $\mathbb{Z}/n\mathbb{Z}$ tels que $\alpha^2=1$, puis enfin tous les \'el\'ements $\alpha$ tels que $\alpha^4=1$.

\vspace{0.8cm}
\noindent \textbf{Exercice 2.} D\'emontrer qu'un nombre entier de la forme $8k-1$ n'est jamais la somme de trois carr\'es.

\vspace{0.8cm}
\noindent \textbf{Exercice 3.} Soient $a$, $b$ et $c$ trois nombres entiers relatifs. D\'emontrer que, si $a^3 + b^3 + c^3$ est divisible par $7$, alors n\'ecessairement l'un des trois nombres $a$, $b$ ou $c$ est divisible par $7$.

\vspace{0.8cm}
\noindent \textbf{Exercice 4.} D\'eterminer l'inverse de $8$ modulo $43$, puis l'inverse de $11$ modulo $128$.

\vspace{0.8cm}
\noindent \textbf{Exercice 5.} (\emph{La fonction indicatrice d'Euler}) \'Etant donn\'e un entier naturel $n \geq 1$, on rappelle que l'on note $\varphi(n)$ le nombre d'\'el\'ements inversibles dans l'anneau $\mathbb{Z}/n\mathbb{Z}$ ; de mani\`ere \'equivalente, $\varphi(n)$ est le nombre d'entiers naturels $m$ tels que $$1 \leq m \leq n \ \ \textrm{et} \ \ \mathrm{pgcd}(n,m)=1.$$ L'application $\varphi : \mathbb{N} - \{0\} \rightarrow \mathbb{N}$ ainsi d\'efinie est la \emph{fonction indicatrice d'Euler}.

1. D\'eterminer directement $\varphi(n)$ pour $1 \leq n \leq 8$.

2. Soient $n$, $n'$ deux entiers naturels non nuls et premiers entre eux. D\'emontrer que l'on a $\varphi(nn') = \varphi(n) \varphi(n')$.

3. Calculer $\varphi(p^k)$ pour tout nombre premier $p$ et tout nombre entier naturel $k$.

4. D\'eduire des questions (ii) et (iii) une formule explicite pour $\varphi(n)$, quel que soit le nombre entier $n \geq 1$.

5. Calculer $\varphi(60)$ et $\varphi(100)$.

6. On va finalement montrer que, pour tout nombre entier $n \geq 1$, $$\sum_{d|n} \varphi(d) = n,$$ la somme portant sur l'ensemble des entiers $d \geq 1$ divisant $n$.

Posons $\Phi(n) = \sum_{d|n} \varphi(d).$
\begin{itemize} \item  V\'erifier que $\Phi(nn')=\Phi(n)\Phi(n')$ pour tous $n, n'$ tels que $\mathrm{pgcd}(n,n')=1$. \item Calculer $\Phi(p^k)$ pour tout nombre premier $p$ et tout nombre entier naturel $k$. \item Conclure. \end{itemize}

\vspace{0.8cm}
\noindent \textbf{Exercice 6.} (\emph{Le th\'eor\`eme de Fermat-Euler, 1}) D\'emontrer que les quatre \'enonc\'es suivants sont \'equivalents.

1. Quel que soit le nombre premier $p$, $a^{p-1} \equiv 1 \ (\mathrm{mod} \ p)$ pour tout nombre entier $a$ tel que $p \nmid a$.

2. Quel que soit le nombre premier $p$, $a^p \equiv a \ (\mathrm{mod} \ p)$ pour tout nombre entier $a$.

3. Quels que soient le nombre premier $p$ et l'entier naturel $k \geq 1$, $a^{p^{k-1}(p-1)} \equiv 1 \ (\mathrm{mod} \ p^k)$ pour tout nombre entier $a$ tel que $p \nmid a$.

4. Quel que soit le nombre entier $n \geq 1$, $a^{\varphi(n)} \equiv 1 \ (\mathrm{mod} \ n)$ pour tout nombre entier $a$ tel que $\mathrm{pgcd}(a,n) = 1$.

\vspace{0.1cm}
(\emph{Indication : d\'emontrer les implications $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$. Pour $2 \Rightarrow 3$, raisonner par r\'ecurrence sur $k$ en \'ecrivant $a^{p^{k-1}(p-1)} - 1 = A^p - 1$ avec $A = a^{p^{k-2}(p-1)}$.})

\vspace{0.8cm}
\noindent \textbf{Exercice 7.} (\emph{Le th\'eor\`eme de Fermat-Euler, 2}) Soit $n \geq 1$ un nombre entier et soit $a \in \mathbb{Z}$ premier avec $n$.

1. Notons $M$ le produit de tous les entiers $m \in \{1, \ldots, n-1\}$ tels que $\mathrm{pgcd}(n,m)=1$. En consid\'erant la multiplication par $a$ dans $\mathbb{Z}/n\mathbb{Z}$, d\'emontrer que l'on a : $a^{\varphi(n)} M \equiv M \ (\mathrm{mod} \ n)$.

2. En d\'eduire le th\'eor\`eme de Fermat-Euler : $$a^{\varphi(n)} \equiv 1 \ (\mathrm{mod} \ n).$$

3. D\'eterminer le dernier chiffre de $13^{2009}$ dans l'\'ecriture d\'ecimale. M\^eme question avec $13^{100!}$.

4. D\'eterminer le dernier chiffre de $2007^{2008}$ dans l'\'ecriture hexad\'ecimale (c'est-\`a-dire en base $16$).

\vspace{0.8cm}
\noindent \textbf{Exercice 8.} (\emph{Le petit th\'eor\`eme de Fermat}) Soit $p$ un nombre premier.

1. D\'emontrer que, pour tout entier $k \in \{1, \ldots, p-1\}$, $p$ divise le coefficient binomial $\binom{p}{k}$.

2. En d\'eduire que l'on a $(a+b)^{p} \equiv a^p + b^p \ (\mathrm{mod} \ p)$ pour tous $a, \ b \in \mathbb{Z}$.

3. En d\'eduire le petit th\'eor\`eme de Fermat : $$\forall a \in \mathbb{Z}, \ \ a^{p} \equiv a \ (\mathrm{mod} \ p).$$
 
\vspace{0.8cm}
\noindent \textbf{Exercice 9.} (\emph{Le th\'eor\`eme RSA (Rivest-Shamir-Adleman, 1977})) Soient $p$ et $q$ deux nombres premiers distincts. On pose $N = pq$ et on choisit un nombre entier $e >1$ premier \`a $\varphi(N)  = (p-1)(q-1)$.

1. Justifier qu'il existe un nombre entier $d$ tel que $ed \equiv 1 \ (\mathrm{mod} \ (p-1)(q-1)).$

2. D\'emontrer que, pour tout nombre entier $a$, $a^{ed} \equiv a \ (\mathrm{mod} \ p)$  et $a^{ed} \equiv a \ (\mathrm{mod} \ q)$.

3. En d\'eduire que, pour \emph{tout} nombre entier $a$, $$a^{ed} \equiv a \ (\mathrm{mod} \ N).$$

\emph{Cette variante du th\'eor\`eme de Fermat-Euler est le fondement du syst\`eme de cryptographie RSA, introduit par Ron Rivest, Adi Shamir et Len Adleman en 1977 et utilis\'e aujourd'hui de mani\`ere quasi universelle... Pour en savoir plus, voir la fiche compl\'ementaire \og Cryptographie\fg \ ainsi que les diff\'erents documents regroup\'es sur ma page personnelle~\footnote{http://math.univ-lyon1.fr/~thuillier/enseignements/ATN}, dont l'article original de Rivest, Shamir et Adleman.}

\vspace{0.8cm}
\noindent \textbf{Exercice 10.} (\emph{Le th\'eor\`eme de Wilson, 1}) Soit $p$ un nombre premier.

1. D\'eterminer tous les \'el\'ements $\alpha$ du corps $\mathbb{Z}/p\mathbb{Z}$ tels que $\alpha^2 = 1$.

2. En regroupant chaque \'el\'ement avec son inverse, d\'emontrer que le produit de tous les \'el\'ements non nuls du corps $\mathbb{Z}/p\mathbb{Z}$ est \'egal \`a $-1$.

3. En d\'eduire le th\'eor\`eme de Wilson : $$(p-1)! \equiv -1 (\mathrm{mod} \ p).$$

\vspace{0.8cm}
\noindent \textbf{Exercice 11.} (\emph{Le th\'eor\`eme de Wilson, 2}) Soit $p$ un nombre premier.

1. D\'emontrer que le polyn\^ome $\T^{p-1} - 1$ est scind\'e \`a racines simples sur le corps $\mathbb{Z}/p\mathbb{Z}$.

2. En d\'eduire que l'on a : $(p-1)! \equiv -1 \ (\mathrm{mod} \ p)$.

3. D\'emontrer qu'un nombre entier $n \geq 2$ est premier si et seulement si $$(n-1)! \equiv -1 \ (\mathrm{mod} \ n).$$


\end{document} 