
\begin{enumerate}
\item Montrons ce résultat par l'absurde. Supposons qu'il existe deux restes égaux $r$ et $r'$ et notons pour
$k\in\llbracket0;p-1\rrbracket$ et $k'\in\llbracket0;p-1\rrbracket$ différent de $k$ :
\begin{align*}
ka=pq+r &\qquad q\in\Z,\ 0\leqslant r < p\\
k'a=pq'+r &\qquad q'\in\Z,\ 0\leqslant r<p
\end{align*}
Ainsi, par différence :
\[
(k-k')a = (q-q')p.
\]
$p$ divise donc $(k-k')a$.

Or, $(k-k')<p$ donc $p$ ne peut pas diviser $(k-k')$ et donc $p$ divise $a$, ce qui est contradictoire avec nos hypothèses.

\medskip

\uline{Par conséquent, il ne peut pas exister deux restes égaux dans la division euclidienne par $p$ de $a$, $2a$, ... , $(p-1)a$.}

\item D'après ce qui précède :
\begin{align*}
a & \equiv r_1\mod p\\
2a & \equiv r_2\mod p\\
\vdots & \vdots \\
(p-1)a & \equiv r_{p-1}\mod p
\end{align*}

D'où, par produit :
\[
\fact{(p-1)}a^{p-1} \equiv r_1r_2\cdots r_{p-1} \mod p\;.
\]
Comme les $r_i$ sont tous distincts, $r_1r_2\cdots r_{p-1}=\fact{(p-1)}$ et comme pgcd\coord{p}{\fact{(p-1)}}=1, on peut diviser chacun des membres de la congruence par \fact{(p-1)}, ce qui donne :
\[
\boxed{a^{p-1} \equiv 1 \mod p}
\]

\item Pour tout entier $a$ tel que $pgcd\coord{a}{561}=1$, il existe un couple d'entiers relatifs \coord{u}{v} tel que $au+561v=1$, soit tel que $au\equiv1\mod 561$.

On utilise 3 fois le petit théorème de Fermat :
\[
\begin{cases}
u^2  & \equiv 1 \mod 3 \iff u^{560} \equiv 1 \mod 3 \\
u^{10} & \equiv 1 \mod 11 \iff u^{560} \equiv 1 \mod 11\\
u^{16} & \equiv 1 \mod 17 \iff u^{560} \equiv 1 \mod 17
\end{cases}
\]
D'où :
\[
u^{560} \equiv r \mod 561\qquad\text{avec}\qquad r\equiv1\mod3,\ r\equiv1\mod11,\ r\equiv1\mod17\;.
\]
On a alors :
\[
r=3k+1=11k'+1=17k''+1\;,
\]
soit :
\[
3k=11k'=17k''.
\]
Ainsi, 11 divise $k$ et 17 divise $k'$, soit $k=11m$ et $k'=17m'$.

Alors,
\[
r=3\times11m+1=11\times17m'+1
\]
soit :
\[
3\times11m=11\times17m'
\]
et donc $3m=17m'$. Ainsi, 17 divise $m$ et on peut écrire $m=17\lambda$.

On arrive ainsi à : $r=3\times11\times17\lambda+1$, soit $r\equiv1\mod561$ et donc $u^{560}\equiv1\mod561$.

\medskip

Or, nous avons vu que $au\equiv1\mod561$ donc $(au)^{560}\equiv1\mod561$.

Comme $u^{560}\equiv1\mod561$, cela nous donne : $a^{560}\equiv1\mod561$, où 561 n'est pas un nombre premier.

Ceci prouve que la réciproque du petit théorème de Fermat est fausse.
\end{enumerate}
