
\medskip

\partie{A}

\begin{enumerate}
\item $a$ est premier avec $p$ donc, d'après le théorème de Fermat, $a^{p-1} \equiv 1 \mod p$.

Ainsi, par exponentiation,
\[
\left(a^{p-1}\right)^{q-1} \equiv 1 \mod p
\]
soit:
\[
a^{(p-1)(q-1)} \equiv 1 \mod p.
\]
Par symétrie du problème, comme $a$ et $q$ sont premiers entre eux, on a de même:
\[
a^{(p-1)(q-1)} \equiv 1 \mod q.
\]

\item $p$ et $q$ étant premiers entre eux, d'après le théorème de Gauss,
\[
\begin{cases}
a^{(p-1)(q-1)} \equiv 1 \mod p\\
a^{(p-1)(q-1)} \equiv 1 \mod q
\end{cases} \Rightarrow a^{(p-1)(q-1)} \equiv 1 \mod pq \Rightarrow a^{(p-1)(q-1)} \equiv 1 \mod N.
\]

\item Soit $k$ tel que $k \equiv 1 \mod n$, avec $n=(p-1)(q-1)$.

Alors, $k = 1 + (p-1)(q-1)m$, $m\in\N$.

Ainsi,
\begin{align*}
a^k & = a^{1 + (p-1)(q-1)m}\\
    & = a \times a^{(p-1)(q-1)m}\\
    & = a \times \left( a^{(p-1)(q-1)}\right)^m\\
    & \equiv a \times 1^m \mod N \text{ (d'après la question précédente)}\\
    & \equiv a \mod N.
\end{align*}
\end{enumerate}

\partie{B}

\begin{enumerate}
\item $c$ et $n$ sont premiers entre eux donc, d'après le théorème de Bézout, l'équation $cu+nv=1$ admet au moins une solution, où $u$ et $v$ sont deux entiers relatifs.

En posant $u=x$ et $y=-v$, on obtient que l'équation $cx-ny=1$ admet au moins une solution.

\item
\begin{itemize}
\item $\boxed{\Longleftarrow}$ Supposons que $x=x_0+kn$ et $y=y_0+kc$, où $k\in\Z$. Alors,
\begin{align*}
cx+ny & = c(x_0+kn) - n(y_0+kc)\\
      & = \underbrace{cx_0-ny_0}_{=1} + kcn - kcn\\
      & = 1.
\end{align*}

\item $\boxed{\Longrightarrow}$ Supposons que \coord{x_0}{y_0} est solution de l'équation $cx-ny=1$. Alors,
\[
\begin{cases}
cx - ny = 1\\
cx_0 - ny_0 = 1
\end{cases}
\]
En soustrayant membre à membre ces deux équations, on a:
\[
c(x-x_0) - n(y-y_0) = 0 \qquad\text{soit}\qquad c(x-x_0) = n(y-y_0).
\]
Or, $c$ et $n$ sont premiers entre eux donc, d'après le théorème de Bézout,
\[
\exists k\in\Z,\ \begin{cases}x-x_0=kn \\ y-y_0=kc\end{cases} \iff \begin{cases}x = x_0+kn \\ y=y_0+kc\end{cases}
\]
\end{itemize}

\item L'équation $cx-ny=1$ admet des solutions entières de la forme:
\[
\begin{cases}x = x_0+kn \\ y=y_0+kc\end{cases}\qquad,\qquad k\in\Z.
\]
Notons $d = x_0+kn$ tel que  $0 \leqslant d < n$. Cet entier est unique.

Or,
\[
cx-ny=1 \iff cx \equiv 1 \mod n.
\]
Donc il existe bien un unique entier $d$ solution de l'équation $cx\equiv1\mod n$.
\end{enumerate}

\partie{C}

Soient $a$ et $b$ deux entiers naturels et $c$ un nombre premier avec $n$, $c<n$.

D'après la partie B, il existe un entier naturel $d<n$ tel que $cd\equiv 1 \mod n$.

Ainsi, d'après la partie A, $a^{cd} \equiv a \mod N$.

On a alors:
\begin{align*}
b \equiv a^c \mod N & \Longrightarrow b^d \equiv a^{cd} \mod N\\
& \Longrightarrow b^d \equiv a \mod N.
\end{align*}
