\chapter{Arithmétique}

\newpage
\pagestyle{main}

\section{Divisibilité}

\begin{defin}
Un nombre relatif $a$ est \textit{divisible} par un entier naturel $n$ non nul s'il existe un entier $k$ tel que $a = kn$.
\[
a\in\Z,\ n\in\N*,\ a\text{ divisible par }n \iff \exists k\in\N*,\ a=kn.
\]
$n$ est alors appelé un \textit{diviseur} de $a$.
\end{defin}

\begin{exemple}
\begin{itemize}
\item $786$ est divisible par 2 et par 3 car $786 = 2\times393$ et $786=3\times262$.
\item 0 est divisible par tout entier naturel $n$ non nul car $0 = k\times 0$.
\end{itemize}
\end{exemple}

\begin{defin}
L'ensemble des entiers  naturels compris entre deux entiers naturels $a$ et $b$ est noté:
\[
\llbracket a\;;\; b \rrbracket.
\]
\end{defin}

\begin{exemple}
$\llbracket 0\;;\; 5 \rrbracket = \{ 0;1;2;3;4;5\}$.
\end{exemple}

\begin{prop}
Soit $n$ un entier relatif non nul.

L'ensemble des diviseurs positifs de $n$ est un ensemble fini.
\end{prop}

\begin{demo}
$\llbracket 1\;;\; |n| \rrbracket$ est un ensemble fini et si $n$ possède des diviseurs alors ils appartiennent à cet ensemble.

Par conséquent, l'ensemble des diviseurs positifs de $n$ est un sous-ensemble de $\llbracket 1\;;\; |n| \rrbracket$, et est donc fini. 
\end{demo}

\medskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.1} et \ref{exercice:\thechapter.2}.

\begin{prop}
Soient $a$, $b$ et $c$ trois entiers relatifs, $a\neq0$ et $b\neq0$.
\begin{enumerate}
\item Si $a$ divise $b$ et $b$ divise $c$ alors $a$ divise $c$.
\item Si $a$ divise $b$ et $c$ alors $a$ divise toute combinaison linéaire de $b$ et $c$.
\end{enumerate}
\end{prop}

\begin{demo}
\og $a$ divise $b$ \fg{} peut aussi s'écrire \og $a|b$ \fg.
\begin{enumerate}
\item $a|b \iff \exists k\in\N*,\ b = ka$.

$b|c \iff \exists k'\in\N*,\ c = k'b$.

\medskip

Ainsi, 
\[
\exists (k,k')\in\N*\times\N*,\ c = k' \times ka = (kk')a.
\]
Par conséquent, il existe un entier $K = kk'$ tel que $c=Ka$, donc $a|c$.

\item $a|b$ et $a|c$ donc il existe deux entiers $k$ et $k'$ tels que $b = ka$ et $c= k'a$.

Une combinaison linéaire de $b$ et $c$ est $pb+qc$, $p$ et $q$ étant deux entiers relatifs.
\[
pb+qc = p(ka) + q(k'a) = (pk + qk')a.
\]
Par conséquent, $a|(pb+qc)$.
\end{enumerate}
\end{demo}

\medskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.3} à \ref{exercice:\thechapter.18}.

\section{Division euclidienne}

\begin{thm}
Soient $a$ et $b$ deux entiers naturels.

Il existe un unique couple \coord{q}{r} d'entiers naturels tels que:
\[
a = bq+r \qquad,\qquad 0 \leqslant r < b.
\]
Cette dernière écriture est appelée la \textit{division euclidienne de $a$ par $b$}.

$q$ est alors le \textit{quotient} et $r$ le \textit{reste} de cette division.
\end{thm}

\begin{exemple}
La division euclidienne de 37 par 11 est:
\[
37 = 3\times 11 + 4.
\]
Le quotient de cette division est 3, et le reste 4.
\end{exemple}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.19} à \ref{exercice:\thechapter.24}.

\section{Congruences}

\begin{defin}
Soient $a$ et $b$ deux entiers relatifs
On dira que $a$ est congru à $r$ modulo $n$ si:
\[
a = nq + r\qquad,\qquad 0 \leqslant r < n.
\]
On note alors:
\[
a \equiv r \quad [n]\qquad\text{ou}\qquad a\equiv r\quad (n)\qquad\text{ou}\qquad a\equiv r \mod n.
\]
\end{defin}

\begin{exemple}
On a:
\[
17 = 3\times5 + 2
\]
donc:
\[
17 \equiv 2 \quad [3] \qquad\text{et}\qquad 17 \equiv 2 \quad [5].
\]
\end{exemple}

\begin{prop}
Soient $a$ et $b$ deux entiers relatifs, et $n$ un entier naturel.
\begin{enumerate}
\item \textbf{[divisibilité]} $a\equiv b\quad (n) \iff n|(a-b)$.
\item \textbf{[transitivité]} Si $a\equiv c\quad (n)$ et $c\equiv b\quad (n)$ alors $a\equiv b\quad (n)$, pour $c\in\Z$.
\item \textbf{[somme]}
\begin{enumerate}
\item $a\equiv b \quad (n) \iff a+k \equiv b+k \quad (n)$ pour $k\in\Z$.
\item $\begin{cases}
a\equiv b \quad (n)\\
a'\equiv b' \quad (n)
\end{cases} \Longrightarrow a+a' \equiv b+b' \quad (n)$.
\end{enumerate}
\item \textbf{[produit]}
\begin{enumerate}
\item $a\equiv b \quad (n) \iff ka \equiv kb \quad (n)$ pour $k\in\Z$.
\item $\begin{cases}
a\equiv b \quad (n)\\
a'\equiv b' \quad (n)
\end{cases} \Longrightarrow aa' \equiv bb' \quad (n)$.
\end{enumerate}
\item \textbf{[puissance]} $a\equiv b \quad (n) \Longrightarrow a^k \equiv b^k \quad (n)$ pour $k\in\N*$.
\end{enumerate}
\end{prop}

\begin{exemple}
On a: $17 \equiv 1 \quad (4)$. Par conséquent,
\[
\forall k\in\N,\qquad 17^k \equiv 1^k \quad (4)
\]
soit:
\[
\forall k\in\N,\qquad 17^k \equiv 1 \quad (4)
\]
\end{exemple}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.25} à \ref{exercice:\thechapter.40}.

\section{PGCD de deux entiers}

\subsection{Notion de PGCD}

\begin{defin}
Soient $a$ et $b$ deux entiers naturels non tous les deux nuls.

Le \textit{plus grand commun diviseur} de $a$ et $b$, noté $\pgcd{a}{b}$ ou PGCD\coord{a}{b}, est le plus grand diviseur de $a$ et de $b$.
\end{defin}

\begin{exemple}
Les diviseurs de 12 sont: 1, 2, 3, 4, 6, 12.

Les diviseurs de 15 sont: 1, 3, 5.


Ainsi, $\pgcd{12}{15}=3$ car c'est 3 divise 12 et 15, et c'est le plus grand des diviseurs qui apparaît dans les deux listes.
\end{exemple}

\subsection{Algorithme d'Euclide}

\begin{prop}
Soient $a$ et $b$ deux entiers naturels non nuls tels que:
\[
\exists q\in\N*,\ a = bq+r\quad,\quad 0\leqslant r < b.
\]
Alors, $\pgcd{a}{b} = \pgcd{b}{r}$.
\end{prop}

De cette propriété, on déduit ce que l'on appelle l'algorithme d'Euclide.

\begin{exemple}
\begin{minipage}{0.7\linewidth}
Prenons  $a=\numprint{1386}$ et $b=\numprint{1092}$.
\begin{itemize}
\item $\numprint{1386} = 1\times\numprint{1092} + 294$.

Ainsi, $\pgcd{\numprint{1386}}{\numprint{1092}} = \pgcd{\numprint{1092}}{294}$.

\item $\numprint{1092} = 3\times294 + 210$.

Ainsi, $\pgcd{\numprint{1092}}{294} = \pgcd{294}{210}$.

\item $294 = 1\times210 + 84$.

Ainsi, $\pgcd{294}{210} = \pgcd{210}{84}$.

\item $210 = 2\times84 + 42$.

Ainsi, $\pgcd{210}{84} = \pgcd{84}{42}$.

\item $84 = 2\times42 + 0$.

Ainsi, $\pgcd{84}{42} = \pgcd{42}{0}=42$.
\end{itemize}
\end{minipage}
\begin{minipage}{0.28\linewidth}
On en déduit alors que:
\[
\pgcd{\numprint{1386}}{\numprint{1092}}  = 42.
\]
\end{minipage}
\end{exemple} 

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.41} et \ref{exercice:\thechapter.42}.

\newpage

\begin{prop}
Soient $a$ et $b$ deux entiers naturels.
\begin{enumerate}
\item Les diviseurs communs à $a$ et $b$ divisent $\pgcd{a}{b}$.
\item Si $d$ divise $a$ et $d$ divise $b$ alors $d$ divise $\pgcd{a}{b}$.
\item Il existe deux entiers naturels $a'$ et $b'$ tels que $a=a'\times\pgcd{a}{b}$ et $b=b'\times\pgcd{a}{b}$, avec $\pgcd{a'}{b'}=1$.
\end{enumerate}
\end{prop}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.43} à \ref{exercice:\thechapter.47}.

\section{Théorème de Bézout et théorème de Gauss}

\begin{defin}[entiers premiers entre eux]
On dit que deux entiers sont \textit{premiers entre eux} quand leur PGCD est égal à 1.
\end{defin}


\begin{thm}
Soient $a$ et $b$ deux entiers naturels non nuls.
\[
\pgcd{a}{b}=1 \iff \exists\coord{u}{v}\in\Z^2,\ au+bv=1.
\]
\end{thm}

\begin{demo}
\begin{itemize}
\item Démontrons d'abord que si il existe un couple $\coord{u}{v}\in\Z^2$ tel que $au+bv=1$ alors $\pgcd{a}{b}=1$.

\medskip

Supposons donc qu'il existe un couple $\coord{u}{v}\in\Z^2$ tel que $au+bv=1$. 

$\pgcd{a}{b}$ divise $a$ et $b$, donc divise $au+bv$, donc 1. Or, 1 n'a qu'un diviseur: lui-même. Donc $\pgcd{a}{b}=1$.

\bigskip


\item Supposons maintenant que $\pgcd{a}{b}=1$.

Notons $E$ l'ensemble des combinaisons linéaires de $a$ et $b$. $E$ n'est pas vide car\linebreak $a=1\times a + 0\times b$ appartient à $E$.

$E$ a donc un plus petit élément, que l'on va noter $c=au+bv$.

La division euclidienne de $a$ par $c$ est: $a = cq+r\quad,\quad 0\leqslant r < c$.

Ainsi, 
\[
r = a-cq = a-(au+bv)q = (1-uq)a + (-vq)b.
\]
$r$ est donc une combinaison linéaire de $a$ et $b$, donc appartient à $E$. Mais $r<c$, ce qui est contradictoire avec notre hypothèse. Cela implique alors que $r=0$, et donc $c$ divise $a$.

\medskip

De manière analogue, on montre que $c$ divise $b$ et donc que $c$ est un diviseur commun à $a$ et $b$. Or, $\pgcd{a}{b}=1$ donc $c=1$, soit $au+bv=1$.
\end{itemize}
\end{demo}

\begin{prop}[corollaire du théorème de Bézout]
Soient $a$ et $b$ deux entiers naturels non nuls.
\[
\pgcd{a}{b}=d \iff \begin{cases}
d|a\text{ et} d|b\\
\exists\coord{u}{v}\in_Z^2,\ au+bv=d.
\end{cases}
\]
\end{prop}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.48} à  \ref{exercice:\thechapter.55}.

\begin{thm}[de Gauss]
Soient $a$, $b$ et $c$ trois entiers naturels non nuls.

Si $a$ divise $bc$ et si $\pgcd{a}{b}=1$ alors $a$ divise $c$.
\end{thm}

\begin{demo}
$a$ divise $bc$ donc il existe un entier $k$ non nul tel que $bc=ak$.

$\pgcd{a}{b}=1$ donc d'après le théorème de Bézout, il existe un couple \coord{u}{v} d'entiers relatifs tel que $au+bv=1$, soit en multipliant par $c$:
\[
acu + bcv = c \iff acu + akv = c \iff a(cu+kv) = c.
\]
Ainsi, $a$ divise $c$.
\end{demo}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.56} à  \ref{exercice:\thechapter.58}.


\section{Nombres premiers}

\begin{defin}
Un entier naturel est premier s'il n'est divisible que par 1 et lui-même.
\end{defin}

\begin{rem}
Notez bien dans la définition la présence de la conjonction \og et \fg{} qui induit nécessairement que le nombre doit admettre exactement deux diviseurs. 

Ainsi, le nombre 1 n'est pas premier car il n'admet qu'un diviseur: lui-même.
\end{rem}

\begin{thm}
Il existe une infinité de nombres premiers.
\end{thm}

\begin{demo}
Supposons que l'ensemble des nombres premiers soit fini. Notons alors cet ensemble:
\[
\{p_1;p_2;\cdots;p_n\}.
\]
Considérons alors le nombre:
\[
N = p_1 \times p_2 \times \cdots \times p_n + 1.
\]
Il est immédiat que $N$ n'appartient pas à l'ensemble des nombres premiers considéré.

Or, $N$ n'est divisible par aucun des $p_k$, pour $1 \leqslant k \leqslant n$.

Par conséquent, il est premier... ce qui est contradictoire avec le fait que $N$ n'appartienne pas à l'ensemble des nombres premiers considéré.

\medskip

Ainsi, notre hypothèse selon laquelle l'ensemble des nombres premiers est fini est fausse.
\end{demo}

\begin{rem}
L'ensemble des nombres premiers est souvent noté $\mathbb{P}$.
\end{rem}

\begin{thm}
Soit $n$ un entier naturel non nul.

Si $n$ n'est divisible par aucun nombre premier inférieur ou égal à $\sqrt{n}$ alors $n$ est premier.
\end{thm}

\begin{exemple}
$\sqrt{137}\approx11,7$.

De plus, 137 n'est pas divisible par 2, 3, 5, 7 et 11 donc $137\in\mathbb{P}$.
\end{exemple}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.59} à  \ref{exercice:\thechapter.66}.

\bigskip

\begin{thm}[décomposition en produit de facteurs premiers]
Tout entier naturel $n$ supérieur ou égal à 2 peut s'écrire sous la forme:
\[
n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}
\]
où $k$ est un entier naturel non nul et $p_i\in\mathbb{P}$ pour $1\leqslant i\leqslant k$.

\medskip

Cette écriture est appelée la décomposition en produit de facteurs premiers de $n$ et elle est unique.
\end{thm}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.67} à \ref{exercice:\thechapter.70}.

\newpage

\begin{thm}["petit" théorème de Fermat] 
Si $p$ est un nombre premier et si $a$ est un entier non divisible par $p$ alors $a^{p-1}\equiv 1\mod p$.
\end{thm}

\begin{exemple}
Prenons $a=27$ et $p=5$.

$p$ est premier et $a$ n'est pas divisible par $p$ donc $27^4\equiv1\mod5$.
\end{exemple}

\begin{rem}
La congruence de ce théorème est aussi présentée sous la forme suivante:
\[
a^p\equiv a\mod p.
\]
\end{rem}

\bigskip

$\blacktriangleright$ Voir les exercices \ref{exercice:\thechapter.71} à \ref{exercice:\thechapter.77}.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercices %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Divisibilité}

\begin{exocor}{ensemble des diviseurs}
Pour chacun des nombres suivants, donner la liste de ses diviseurs positifs.
\begin{enumerate}
\begin{multicols}{4}
\item $123$
\item $56$
\item $78$
\item $\numprint{1517}$
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item $123 = 3\times41$ donc les diviseurs de 123 sont: 1, 3, 41, 123.

\bigskip

\item $56=2^3\times 7$ donc les diviseurs de 56 sont:
\begin{itemize}
\item \textbf{les facteurs premiers et 1:} 1, 2, 7;
\item \textbf{les produits à deux facteurs premiers}: $2\times2=4$, $2\times7 = 14$;
\item \textbf{les produits à 3 facteurs premiers:} $2^3=8$ et $2^2\times7=28$;
\item \textbf{les produits à 4 facteurs premiers:} $2^3\times7=56$.
\end{itemize}
L'ensemble des diviseurs de 56 est donc : $\{1;2;4;7;8;14;28;56\}$.

\bigskip

\item $78=2\times3\times13$ donc les diviseurs de 78 sont:
\begin{itemize}
\item \textbf{les facteurs premiers et 1:} 1, 2, 3, 13;
\item \textbf{les produits à deux facteurs premiers}: $2\times3=6$, $2\times13 = 26$ et $3\times13=39$;
\item \textbf{les produits à 3 facteurs premiers:} $2\times3\times13=78$.
\end{itemize}
L'ensemble des diviseurs de 78 est donc : $\{1;2;3;6;13;26;39;78\}$.

\bigskip

\item $\numprint{1517}=37\times41$ donc les diviseurs de $\numprint{1517}$ sont 1, 37, 41 et $\numprint{1517}$.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{programme Python}
Compléter le programme Python suivant afin que la fonction \texttt{liste\_diviseurs(n)} retourne la liste de tous les diviseurs positifs de l'entier relatif $n$.
\begin{python}
def liste_diviseurs(n):
    L = []
    for k in range(... , ...):
        if ...:
            L.append(k)
            
    return L
\end{python}

\tcblower

Voici le programme complété:

\begin{python}
def liste_diviseurs(n):
    L = []
    for k in range(1,abs(n)+1):
        if n%k == 0:
            L.append(k)
            
    return L
\end{python}

\medskip

Comme $n$ est un entier relatif, il ne faut pas oublier de faire appel à sa valeur absolue dans la boucle qui parcourt tous les entiers naturels de 1 à $n$.

Ainsi, dans ce programme, $k$ désigne un entier de $\llbracket 1; n\rrbracket$ (n'oublions pas qu'en Python, \texttt{range(a,b)} désigne la liste des entiers de $a$ (compris) à $b-1$ (compris).

Dans la boucle, on teste si $n$ est divisible par $k$ (avec le test \og \texttt{if n\%k == 0} \fg); si tel est le cas, on ajoute à la liste \texttt{L} le nombre $k$  (qui fait donc partie des diviseurs de $n$).
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{combinaison linéaire}
\begin{enumerate}
\item Déterminer les entiers naturels $n$ tels que $n+7$ soit un multiple de 5.
\item Montrer que $51n+4$ n'est jamais divisible par 17.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $n+7$ multiple de 5 signifie qu'il existe un entier $k$ tel que $n+7=5k$, soit $n=5k-7$.

\medskip

Les entiers naturels $n$ tels que $n+7$ soit un multiple de 5 sont les entiers $n$ s'écrivant $n=5k-7$, $k\geqslant2$.

\item $51n=17\times3n$ donc $51n$ est divisible par 17. Or, 7 n'est pas divisible par 17 donc $51n+7$ n'est pas divisible par 17.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{combinaison linéaire}
Soient $a=2n+1$ et $b=n+13$, $n\in\Z$.

Déterminer tous les entiers relatifs $n$ tels que $a|b$ ($a$ divise $b$).

\tcblower

Avant tout, écrivons:
\[
a|b \iff \exists k\in\Z,\ b = ka \iff n+13 = k(2n+1) \iff (2k-1)n = 13-k.
\]
Cela ne nous avance pas à grand-chose... Il faut donc s'y prendre autrement!

\medskip

Cherchons une combinaison linéaire de $a$ et $b$ indépendante de $n$. Notons-la $pa+qb$. Comme $a|a$ et $a|b$, $a|(pa+qb)$. Comme $pa+qb$ est indépendante de $n$, cela signifie que $a$ est un diviseur de cette combinaison linéaire, et on pourra exploiter cela.
\[
pa+qb = 2pn+p+qn+13q = (2p+q)n+p+13q.
\]
$pa+bq$ indépendante de $n$ $\iff 2p+q=0 \iff q=-2p$. On peut alors prendre $p=1$ et $q=-2$.
\[
a-2b=-25.
\]
Par conséquent, $a|25$, donc $a\in\{-25;-5;-1;1;5;25\}$.
\begin{itemize}
\item si $a=-25$, alors $2n+1=-25$ et $n=-13$;
\item si $a=-5$, alors $2n+1=-5$ et $n=-3$;
\item si $a=-1$, alors $2n+1=-1$ et $n=-1$;
\item si $a=1$, alors $2n+1=1$ et $n=0$;
\item si $a=5$, alors $2n+1=5$ et $n=2$;
\item si $a=25$, alors $2n+1=25$ et $n=12$.
\end{itemize}
On doit maintenant vérifier que pour toutes les valeurs de $n$ trouvées, $a$ divise $b$, ce qui se fait rapidement.

\medskip

\underline{Les valeurs de $n$ cherchées sont donc : $-13$, $-3$, $-1$, 0, 2 et 12.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{combinaison linéaire}
Déterminer les entiers relatifs $n$ tels que $a=n-4$ divise $b=3n-17$.

\tcblower

$a|b \iff a|(pa+qb)$, où $p$ et $q$ sont deux entiers relatifs.

$pa+qb=(p+3q)n-(4p+17q)$ est indépendante de $n$ si $p+3q=0$, soit $p=-3q$. Prenons alors $p=-3$ et $q=1$:
\[
pa+qb=-3a+b=-3(n-4)+3n-17=-5.
\]
\newpage
Ainsi, $a|5$, donc
\begin{itemize}
\item $a=1$, et dans ce cas, $n-4=1$, soit $n=5$;
\item $a=5$, et dans ce cas, $n-4=5$, soit $n=9$.
\end{itemize}
Si $n=5$, $a=1$ et $b=2$ ey $a$ divise bien $b$.

Si $n=9$, $a=5$ et $b=10$ et $a$ divise bien $b$.

\medskip

\underline{Ainsi, les valeurs de $n$ telles que $a$ divise $b$ sont 5 et 9.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel non nul.
\begin{enumerate}
\item Montrer que $n+1$ est un diviseur de $n^3+n^2+n+1$.
\item En déduire deux diviseurs de \numprint{1111}.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
n^3+n^2+n+1 & = \dfrac{n^4-1}{n-1}\\
& = \dfrac{(n^2-1)(n^2+1)}{n-1}\\
& = \dfrac{(n-1)(n+1)(n^2+1)}{n-1}\\
& = (n+1)(n^2+1).
\end{aligned}$

\medskip

\underline{Donc $n^3+n^2+n+1$ est bien divisible par $n+1$.}

\item $\numprint{1111} = 10^3+10^2+10+1$ est divisible par $10+1=11$.

De plus, d'après la question précédente, $10^2+1=101$ est aussi un diviseur de \numprint{1111}.

\medskip

\underline{Deux diviseurs non triviaux de \numprint{1111} sont donc 11 et 101.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel.
\begin{enumerate}
\item Démontrer que si $n$ est impair alors 4 divise $n^2-1$.
\item La réciproque est-elle vraie ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Supposons que $n$ soit pair. Alors, il existe un entier $k$ tel que $n=2k+1$.

Ainsi, $n^2-1=(2k+1)^2-1=(2k+1-1)(2k+1+1)=(2k)(2k+2)=4k(k+1)$.

\underline{Par conséquent, 4 divise bien $n^2-1$.}

\item Supposons que 4 divise $n^2-1$. Alors, il existe un entier $k$ tel que $n^2-1=4k$, soit\linebreak $n^2=4k+1$.

On se demande si $n$ est nécessairement impair. Supposons donc qu'il ne le soit pas, et qu'il existe un entier $p$ tel que $n=2p$.

Alors, $n^2=4k+1 \iff 4p^2=4k+1 \iff 4(p^2-k)=1$, ce qui est impossible (car cela voudrait dire que 1 est divisible par 4).

\underline{Ainsi, la réciproque est vraie.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Comment choisir l'entier relatif $n$ pour qu'il divise $n+p$ ?

\tcblower

$n$ divise $n$ donc pour que $n$ divise $n+p$, il est nécessaire que $n$ divise $p$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que la somme de quatre entiers consécutifs est divisible par 2.

\tcblower

Posons $n$ un entier relatif. Alors, $n+(n+1)+(n+2)+(n+3) = 4n+6=2(n+3)$.

On constate alors que la somme des quatre entiers consécutifs est un multiple de 2.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{exocor}{}
Résoudre l'équation $n^2 = m^2 + 11$, où $m$ et $n$ sont deux entiers relatifs.

\tcblower

Avant tout, remarquons que:
\[
n^2 = m^2 + 11 \iff n^2-m^2=11 \iff (n+m)(n-m)=11.
\]
Ainsi, il est nécessaire que $n+m$ ou $n-m$ divise 11. Or, 11 est un nombre premier donc:
\[
\begin{cases}
n+m = 11\\
n-m=1
\end{cases}\qquad\text{ou}\qquad
\begin{cases}
n-m=11\\
n+m=1
\end{cases}.
\]
Autrement dit,
\[
n=6 \qquad\text{et} m=5 \text{ ou }m=-5.
\]
Ainsi, les solutions de l'équation $n^2 = m^2 + 11$ sont les couples $\coord{6}{-5}$ et $\coord{6}{5}$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
On pose $A_n=2n^2+11n+32$ et $B_n=n+3$ pour tout entier relatif $n$.

On se demande pour quelles valeurs de $n$ $B_n$ divise $A_n$.

\begin{enumerate}
\item Montrer que $A_n=(n+3)(2n+5)+17$.
\item Conclure.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
(n+3)(2n+5)+17 & = 2n^2+5n+6n+15+17\\
& = 2n^2+11n+32\\
& = A_n.
\end{aligned}$

\item $B_n$ divise $A_n$ si $\dfrac{A_n}{B_n}\in\Z$, pour $n\neq-3$. Or, 
\begin{align*}
\dfrac{A_n}{B_n} & =\dfrac{(n+3)(2n+5)+17}{n+3}\\
								 & = \dfrac{(n+3)(2n+5)}{n+3}+\dfrac{17}{n+3}\\
								 & =2n+5+\dfrac{17}{n+3}.
\end{align*}

$(2n+5)\in\Z$ donc $\dfrac{A_n}{B_n}\in\Z\iff(n+3)\vert17$.

17 étant un nombre premier, il n'est divisible que par 1 et 17 donc il faut que \mbox{$n+3=\pm1$} (i.e. $n=1-3=-2$ ou $n=-1-3=-4$) ou $n+3=\pm17$ (i.e. $n=17-3=14$ ou\linebreak $n=-17-3=-20$).


\uline{$B_n$ divise $A_n$ pour $n=-2$ et $n=14$.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%% somme 

\begin{exocor}{}
On souhaite démontrer que $5^n+19$ est toujours divisible par 4 pour tout entier naturel $n$.

\begin{enumerate}

\item Exprimer de façon plus simple la somme $1+5+5^2+\cdots+5^{n-1}$ en fonction de $n$.
\item Conclure.
\end{enumerate}

\tcblower

\begin{enumerate}
\item On sait que $1+q+q^2+\cdots+q^n=\dfrac{1-q^{n+1}}{1-q}$ pour $q\neq1$. Ainsi,
\[
1+5+5^2+\cdots+5^{n-1}=\dfrac{1-5^n}{1-5}=\dfrac{5^n-1}{4}.
\]

\item La somme $1+5+5^2+\cdots+5^{n-1}$ est entière donc $5^n-1$ est divisible par 4. 

Ainsi, $5^n-1+4k \in\N$ pour tout entier relatif $k$.

En prenant $k=5$, on obtient $5^n-1+4\times5=5^n+19$, donc $5^n+19$ est toujours divisible par 4.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Démontrer que pour tout entier relatif $p$, $p(p^2-1)$ est divisible par 2 et par 3.

\tcblower

\begin{enumerate}
\item Divisibilité par 2. Deux cas se présentent :
\begin{itemize}
\item $p$ est pair : $p=2k$, $k\in\Z$. Dans ce cas, $p(p^2-1)=2k(4k^2-1)$ est divisible par 2.

\item Si $p$ est impair : $p=2k+1$, $k\in\Z$. Dans ce cas, 
\begin{align*}
p(p^2-1) & =(2k+1)\big[(2k+1)^2-1\big]\\
				 & = (2k+1)(4k^2+2k+1-1)\\
				 & = (2k+1)(4k^2+2k)\\
				 & = 2(2k+1)(2k^2+k)
\end{align*}

Ainsi, $p(p^2-1)$ est divisible par 2.
\end{itemize}

Dans tous les cas, le résultat est démontré.


\item Divisibilité par 3. Trois cas se présentent :
\begin{itemize}
\item $p=3k$, $k\in\Z$. Alors, $p(p^2-1)=3k(9k^2-1)$ est divisible par 3.

\item $p=3k+1$. Alors,
\begin{align*}
p(p^2-1) & = (3k+1)\big[(3k+1)^2-1\big]\\
				 & = (3k+1)(9k^2+6k)\\
				 & = 3k(3k+2)(3k+1).
\end{align*}
Donc $p(p^2-1)$ est divisible par 3.

\item $p=3k+2$. Alors,
\begin{align*}
p(p^2-1) & = (3k+2)\big[(3k+2)^2-1\big]\\
				 & = (3k+2)(9k^2+12k+3)\\
				 & = 3(3k^2+4k+1)(3k+2).
\end{align*}
Donc $p(p^2-1)$ est divisible par 3.
\end{itemize}

Dans tous les cas, $p(p^2-1)$ est divisible par 3.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Démontrer que pour tout entier naturel $n$ impair, $n^2-1$ est divisible par 8.

\tcblower

$n$ est impair donc $n=2k+1$, $k\in\N$.

Ainsi,
\begin{align*}
n^2-1 & = (2k+1)^2-1\\
		  & = 4k^2+4k\\
		  & = 4k(k+1).
\end{align*}

$k$ et $k+1$ sont deux entiers consécutifs donc l'un des deux est pair ; ainsi, leur produit est pair et s'écrit donc $k(k+1)=2q$, $q\in\N$.

On a donc : $n^2-1=4\times2q=8q$, ce qui prouve que $n^2-1$ est divisible par 8.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item On considère un nombre à deux chiffres. On note $d$ le chiffre des dizaines et $u$ celui des unités.

Montrer qu'il est divisible par 7 si et seulement si $3d+u$ est divisible par 7.

\item Comment appliqueriez-vous ce critère pour vérifier que 392 est bien divisible par 7 ?

\item Le nombre \numprint{6119} est-il divisible par 7 ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item $x=10d+u=(7d+3d)+u=7d+(3d+u)$.

$x$ est divisible par 7 équivaut à dire que $7d+(3d+u)$ l'est aussi, i.e. que $3d+u$ est divisible par 7 car $7d$ l'est toujours.

\item On peut s'inspirer du raisonnement précédent en posant :
\begin{align*} 
x & =392\\
  & =39\times10+2\\
  & =39\times(7+3)+2\\
  & =39\times7+3\times39+2
\end{align*}

392 est divisible par 7 si et seulement si $3\times39+2$ l'est aussi.
\[
3\times39+2=3\times(40-1)+2=120-3+2=119.
\]
On recommence avec 119 :
\[
119=11\times7+11\times3+9.
\]
119 est divisible par 7 si et seulement si $11\times3+9$ l'est aussi.
\[
11\times3+9=33+9=42=7\times6.
\]
Ainsi, 119 est divisible par 7, donc 392 aussi.

\item $611\times3+9=\numprint{1833}+9=\numprint{1842}$.

$184\times3+2=552+2=554$

$55\times3+4=165+4=169$

$16\times3+9=48+9=57$

$57$ n'est pas divisible par 7 donc \numprint{6119} non plus.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item Soit $a$ un entier naturel.

Montrer que $a^5-a$ est divisible par 10.

\item Soient $a$ et $b$ deux entiers naturels tels que $a\geqslant b$.

Démontrer que si $a^5-b^5$ est divisible par 10, alors $a^2-b^2$ est divisible par 20.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $a\in\N$. 

$\begin{aligned}[t]
a^5-a & = a(a^4-1)\\
		  & = a(a^2-1)(a^2+1)\\
		  & = a(a-1)(a+1)(a^2+1).
\end{aligned}$

Entre $a$ et $a+1$, il y a un nombre pair ; donc $a^5-a$ est divisible par 2.

$a-1$, $a$ et $a+1$ sont trois nombres consécutifs. Si l'un deux est divisible par 5, alors $a^5-1$ l'est aussi et donc au final, il est divisible par 10.

Si aucun des nombres $a-1$, $a$ et $a+1$ n'est divisible par 5, alors notons $r$ le reste de la division euclidienne de $a$ par 5 : $a=5q+r$, $0<r<5$, $q\in\N$.

Si $a-1$ n'est pas divisible par 5, alors $r\neq1$ ;

si $a+1$ n'est pas divisible par 5, alors $r\neq4$.

Alors, $a^2+1=(5q+r)^2+1=25q^2+10qr+r^2+1$, avec $r=2$ ou $r=3$.

\begin{itemize}
\item Si $r=2$, $r^2+1=5$ ;
\item Si $r=3$, $r^2+1=10$.
\end{itemize}

Dans les deux cas, $a^2+1$ est divisible par 5.

\uline{Ainsi, $a^5-a$ est divisible par 5 et par 2, donc par 10.}

\item $a^5-b^5$ divisible par 10.

Or, on peut écrire :
\[ 
a^5-b^5 = a^5-a+a-(b^5-b)-b=(a^5-a)-(b^5-b)+(a-b).
\]

$a^5-a$ et $b^5-b$ sont divisibles par 10 d'après la question précédente ; ainsi, si $a^5-b^5$ est divisible par 10, $a-b$ doit l'être aussi.

Ainsi, $a-b=10q$, $q\in\N$ et donc $a=10q+b$. En ajoutant $b$ dans les deux membres, on obtient $a+b=10q+2b=2(5q+b)$, et donc $a+b$ est divisible par 2.

\medskip

$a-b$ est divisible par 10 et $a+b$ est divisible par 2, donc $(a-b)(a+b)=a^2-b^2$ est divisible par 20.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Calculer la plus grande valeur de l'entier naturel $n$ telle que $3^n$ divise \fact{\numprint{1000}}.

\tcblower

Remarquons que :
\[
\fact{\numprint{1000}}=(1\times2\times3\times\cdots\times10)\times(11\times\cdots\times20)\times\cdots\times(991\times\cdots\times\numprint{1000})\;.
\]

Combien de multiples de 3 avons-nous ici ? Il y en a 333 ($999\div3$). 

On peut donc factoriser ainsi :
\begin{align*}
\fact{\numprint{1000}} & =3^{333}(
1\times2\times\textcolor{red}{1}\times
4\times5\times\textcolor{red}{2}\times
7\times8\times\textcolor{red}{3}\times10)\times
\cdots\times(991\times992\times\textcolor{red}{331}\cdots\times\textcolor{red}{333}\times\numprint{1000})\\
& = 3^{333} \times \textcolor{red}{1\times2\times\cdots\times333}\times\underbrace{1\times2\times4\times5\times\cdots\times\numprint{1000}}_{\text{aucun multiples de 3}}\\
& = 3^{333} \times \fact{333} \times N_1,\quad \text{avec $N_1$ non multiple de 3}.
\end{align*}
De plus, dans $\fact{333}$, il y a 111 multiples de 3 donc, avec un même raisonnement, on a :
\[
\fact{333}=3^{111} \times \fact{111} \times N_2,\quad\text{avec $N_2$ non multiple de 3}.
\]
On voit apparaître \fact{111} dans lequel il y a 37 multiples de 3 (3, 6, 9, ..., 99, 102, 105, 108, 111). On peut donc écrire :
\[
\fact{111} = 3^{37} \times \fact{37} \times N_3,\quad\text{avec $N_3$ non multiple de 3}.
\]
De même, on voit \fact{37} apparaître, où il y a 12 multiples de 3 donc on peut écrire :
\[
\fact{37} = 3^{12} \times \fact{12} \times N_4,\quad\text{avec $N_4$ non multiple de 3}.
\]
On voit \fact{12} apparaître, où il y a 4 multiples de 3 donc on peut écrire :
\[
\fact{12} = 3^{4} \times \fact{4} \times N_5,\quad\text{avec $N_5$ non multiple de 3}.
\]
On voit apparaître \fact{4} où il y a 1 multiple de 3 et on peut écrire :
\[
\fact{4}=3^1(1\times2\times1\times4)\;.
\]
Finalement, dans \fact{\numprint{1000}}, on peut mettre en facteur $3^{333+111+37+12+4+1}=3^{498}$.

\uline{Ainsi, le plus grand entier $n$ tel que $3^n$ divise \fact{\numprint{1000}} est $n=498$.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier relatif.
\begin{enumerate}
\item Montrer que si $d$ divise $12n+7$ et $3n+1$ alors $d$ divise 3.
\item Montrer que $\dfrac{12n+7}{3n+1}$ est irréductible.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Supposons que $d$ divise $a=12n+7$ et $b=3n+1$. Alors, $d$ divise toute combinaison linéaire de $a$ et $b$:
\[
\forall\coord{\lambda}{\mu}\in\Z^2,\ d | \lambda(12n+7)+\mu(3n+1).
\]
Choisissons \coord{\lambda}{\mu} de sorte que la combinaison linéaire de dépende plus de $n$. Prenons alors $\lambda=1$ et $\mu=-4$.

Alors, $d$ divise $12n+7-4(3n+1)$, soit \underline{$d$ divise 3}.

\item Faisons un raisonnement par l'absurde: supposons que $\dfrac{12n+7}{3n+1}$ ne soit pas irréductible.

Alors, il existe un enter $d$ qui divise $12n+7$ et $3n+1$, donc qui divise 3 (d'après la question précédente).

Ainsi, $d=1$ ou $d=3$ ou $d=-1$ ou $d=-3$.

\medskip

Les cas $d=1$ et $d=-1$ ne sont pas possibles car la fraction est supposée simplifiable. 

\medskip

Si $d=3$ ou $d=-3$ alors 3 divise $12n+7$, ce qui est impossible car 3 divise $12n$ mais pas 7. 

\medskip

Il y a donc contradiction; notre hypothèse de départ est alors fausse: $\dfrac{12n+7}{3n+1}$ est irréductible.
\end{enumerate}
\end{exocor}

\subsection*{Division euclidienne}

\begin{exocor}{}
Donner la division euclidienne de $a$ par $b$ dans chaque cas suivant.
\begin{enumerate}
\begin{multicols}{2}
\item $a=345$ et $b=12$
\item $a=76$ et $b=67$
\item $a=\numprint{1001}$ et $b=101$
\item $a=673$ et $b=97$.
\end{multicols}
\end{enumerate}

\vspace*{-1.5em}

\tcblower

\begin{enumerate}
\item $345 = 28\times12 + 9$.
\item $76=1\times67+9$.
\item $\numprint{1001} = 9\times101 + 92$.
\item $673=6\times97+91$.
\end{enumerate}
%
%\medskip
%
%\begin{rem}
%On peut bien entendu utiliser la calculatrice en prenant la partie entière de la division euclidienne de $a$ par $b$ (pour trouver le quotient $q$), puis obtenir $r=a-bq$, mais on peut aussi utiliser Python.
%
%\medskip
%
%Pour la première division euclidienne, on a:
%\begin{console}
%>>> 345//12
%28
%
%>>> 345%12
%9
%\end{console}
%
%\medskip
%
%qui nous donne successivement le quotient et le reste.
%\end{rem}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel.

Déterminer le quotient et le reste de la division euclidienne de $7n+5$ par $3n+1$ suivant les valeurs de $n$.

\tcblower

On écrit $a=bq+r$ avec $a=7n+5$ et $b=3n+1$:
\[
7n+5 = 2(3n+1) + n+3\qquad,\qquad 0 \leqslant n+3 < 3n+1.
\]
La condition sur le reste $0 \leqslant n+3 < 3n+1$ équivaut à écrire que $n > 1$. Donc,
\begin{itemize}
\item si $n>1$ le quotient est égal à 2 et le reste à $n+3$;
\item si $n=0$, $a=bq+r \iff 5 = 5\times1+0$ donc dans ce cas, le quotient est égal à 5 et le reste à 0;
\item si $n=1$, $a=bq+r \iff 12 = 3\times4 + 0$ donc ici, le quotient est égal à 3 et le reste à 0.
\end{itemize}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel.

Quand on le divise par 4, le reste est 3.

Quand on le divise par 5, le reste est 1.

Dans les deux cas, le quotient est le même.

\medskip

Quelle est la valeur de $n$ ?
\vspace*{-1.5em}

\tcblower

D'après l'énonce, on a :
\[
\begin{cases}
n = 4q+ 3\\
n = 5q+1
\end{cases}
\]
donc $4q+3=5q+1 \iff q = 2$. Par conséquent, $n=4q+3=11$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un nombre entier inférieur à 100.

Le reste de la division euclidienne de $n$ par 2 est 1.

Le reste de la division euclidienne de $n$ par 3 est 2.

Le reste de la division euclidienne de $n$ par 5 est 4.


\'Ecrire un programme Python permettant de trouver toutes les valeurs de $n$ possibles.

\tcblower

Voici une suggestion, qui fait appel aux \textit{listes construites par compréhension}:

\begin{python}
L = [ 2*q+1 for q in range(50) ]
P = [ 3*q+2 for q in range(33) ]
Q = [ 5*q+4 for q in range(20) ]
N = [ n for n in L if n in P and n in Q ]
print( N )
\end{python}

\begin{console}
[29, 59, 89]
\end{console}

La liste \texttt{L} est construite en prenant tous les entiers naturels $q$ de 0 à 49 (\texttt{range(0,50}), et en ajoutant 1 à leur double. $2\times49+1=99$ et $2\times50+1=101>100$, ce qui justifie que l'on prend $q\leqslant49$.

Cette liste contient alors tous les entiers de 0 à 100 dont le reste est 1 dans la division euclidienne par 2.

\medskip

Vous l'aurez compris, les listes \texttt{P} et \texttt{Q} sont construites sur un modèle similaire par rapport aux conditions de l'énoncé sur les autres divisions euclidiennes.

\medskip

La liste \texttt{N} contient toutes les valeurs de $n$ dans \texttt{L} qui sont aussi dans les autres listes. C'est donc l'intersection des trois listes, et c'est ce que nous voulions.

\newpage

Une autre suggestion est la suivante:

\begin{python*}
for n in range(101):
    if n%2 == 1 and n%3 == 2 and n%5 == 4:
        print(n)
\end{python*}

qui affiche les mêmes nombres (29, 59 et 89).

Ici, on fait une simple boucle pour parcourir tous les entiers naturels de 0 à 100, et on teste pour chacun d'eux leur reste dans la division euclidienne par 2, 3 et 5. S'ils coïncident avec ce que l'on veut, on les affiche.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel tel que le reste de la division euclidienne de $n$ par 17 est égal à 7.

\begin{enumerate}
\item Quel est le reste de la division euclidienne de $n^2$ par 17 ?
\item Quel est le reste de la division euclidienne de $n^3$ par 17 ?
\end{enumerate}
\vspace*{-1.5em}

\tcblower

\begin{enumerate}
\item Le reste de la division euclidienne de $n$ par 17 est égal à 7:
\[
n = 17q + 7.
\]
Par conséquent,
\begin{align*}
n^2 & = (17q+7)^2\\
    & = 17^2q^2 + 17\times14q + 49\\
 & = 17(17q^2+14q) + 17\times2 + 15\\
    & = 17(17q^2+14q+2) + 15.
\end{align*}
On s'est ici arrangé pour écrire $n^2$ sous la forme $17Q + r$, $0\leqslant r < 17$, afin d'avoir une division euclidienne.

\underline{Ainsi, le reste de la division euclidienne de $n^2$ par 17 est 15.}

\item Procédons de même avec $n^3$:
\begin{align*}
n^3 & = (17q+7)^3\\
    & = 17^3q^3 + 3\times17^2\times q^2\times7 + 3\times17q\times 7^2 + 7^3\\
    & = 17(17^2q^3 + 3\times17\times7q^2 + 3q\times7^2) + 20*17 + 3\\
    & = 17(289q^3+357q^2+147q+20)+3.
\end{align*}
\underline{Ainsi, le reste de la division euclidienne de $n^3$ par 17 est 3.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{division par 11}
\begin{enumerate}
\item Déterminer le reste de la division euclidienne de 100 par 11, de \numprint{1000} par 11, de \numprint{10000} par 11, de \numprint{100000} par 11.

Quelle conjecture peut-on alors faire ?
\item Démontrer la conjecture.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
10^2=100 & =9\times11+1\\
10^3=\numprint{1000} & = 90\times11+10\\
10^4=\numprint{10000} & = 909\times11+1\\
10^5=\numprint{100000} & =\numprint{9090}\times11+10
\end{aligned}$

On peut conjecturer que lorsque $n$ est pair, le reste de la division euclidienne de $10^n$ par 11 est égal à 1 et lorsqu'il est impair, ce reste est égal à 10.

\item 
\begin{itemize}
\item Supposons que $n$ soit un entier naturel pair. Alors, $n=2k$, $k\in\N$ et\\ $10^n=10^{2k}=100^k=(99+1)^k$.

Or, $(a+b)^k=\displaystyle\sum_{p=0}^k c_p a^p b^{k-p}$, où les $c_p$ sont des coefficients entiers.

Autrement dit, $(99+1)^k=99^k+99^{k-1}c_1+99^{k-2}c_2+\cdots+99c_{p-1}+1$.

Chaque terme de cette somme (sauf le dernier) étant un multiple de 99, le reste de la division euclidienne de $100^k$ par 11 est égale à 1 (le dernier terme de la somme).

\uline{Cela montre que si $n$ est pair, alors le reste de la division euclidienne de $10^n$ par 11 est égal à 1.}

\item Supposons que $n$ soit impair. Alors, $n=2k+1$, $k\in\N$ et $10^n=10^{2k+1}=10^{2k}\times10$.

D'après ce qui a été fait précédemment, on peut alors écrire :
\[
10^{2k}\times10=10\times99^k+10\times99^{k-1}c_1+10\times99^{k-2}c_2+\cdots+10\times99c_{p-1}+10.
\]

Ainsi, le reste de la division euclidienne de $10^{2k+1}$ par 11 est égal à 10.
\end{itemize}

La conjecture est alors démontrée.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection*{Congruences}

\begin{exocor}{}
Quel est le reste de la division euclidienne de $73^{37}$ par 5 ?

\tcblower

Remarquons que:
\[
73 \equiv 3\quad (5)
\]
donc:
\[
73^{37} \equiv 3^{37}\quad (5).
\]
Regardons les premières puissances de 3 modulo 5:
\begin{itemize}
\item $3^1\equiv 3\quad (5)$
\item $3^2\equiv 9\equiv 4 \quad (5)$
\item $3^3\equiv 27 \equiv 2\quad (5)$
\item $3^4\equiv \big(3^2\big)^2 \equiv 4^2 \equiv 1\quad (5)$
\end{itemize}
Ce dernier reste est intéressant car il signifie que $\big(3^4\big)^k\equiv 1\quad (5)$ pour tout entier naturel $k$.

\medskip

Or, 
\[
3^{37} = 3^{4\times 9 + 1}
\]
donc:
\[
73^{37} \equiv 3^{4\times9+1}\quad (5)
\]
soit:
\[
73^{37} \equiv \big(3^{4}\big)^9 \times 3^1\quad (5)
\]
donc:
\[
73^{37} \equiv 1 \times 3^1\quad (5).
\]
Finalement,
\[
\boxed{73^{37} \equiv 3\quad (5).}
\]
\underline{Ainsi, le reste de la division euclidienne de $73^{37}$ par 5 est 1.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Calculer le reste de la division euclidienne de $13^{\numprint{1789}}$ par 14.

\tcblower

$13\equiv-1\mod14$ donc $13^{\numprint{1789}}\equiv(-1)^{\numprint{1789}}\equiv-1\equiv13\mod14$.

\medskip

\underline{Le reste de la division euclidienne de $13^{\numprint{1789}}$ par 14 est donc 13.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Quel est le reste de la division par 7 du nombre $32^{45}$ ? 

\tcblower

Nous savons que $32=4\times7+4$ donc $32\equiv4\mod7$.

Ainsi, $32^{45}\equiv4^{45}\mod7$.

Or, $4^2=16\equiv2\mod7$ et $4^3=64\equiv1\mod7$.

On peut donc écrire :

\begin{align*}
32^{45} & \equiv4^{3\times15}\mod7\\
        & \equiv\big(4^3\big)^{15}\mod7\\
        & \equiv1^{15}\mod7\\
        & \equiv1\mod7.
\end{align*}

\underline{Le reste de la division euclidienne de $32^{45}$ par 7 est donc 1.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Calculer le reste de la division euclidienne de $17^{548}$ par 7.

\tcblower

$17\equiv3\mod7$ car $17=2\times7+3$.

Ainsi, $17^2\equiv3^2\equiv2\mod7$, et donc $17^{\textcolor{red}{6}}\equiv2^3\equiv1\mod7$.

On écrit 548 sous la forme : $548=\textcolor{red}{6}\times91+2$ donc :
\begin{align*}
17^{548} & =\big(17^6\big)^{91}\times17^2\\
				 & \equiv 1^{91}\times2\mod7\\
				 & \equiv 2\mod 7
\end{align*}

\uline{Ainsi, le reste de la division euclidienne de $17^{548}$ par 7 est égal à 2.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Trouver tous les entiers naturels $n$ tels que le reste de la division euclidienne de $24^n$ par 7 soit égal à 3.

\tcblower

Remarquons que $24\equiv3\mod7$ car $24=3\times7+3$.

Ainsi, $\begin{aligned}[t]
24^1\equiv3^1\equiv\mod7\\
24^2\equiv3^2\equiv2\mod7\\
24^3\equiv3^3\equiv6\mod7\\
24^4\equiv3^4\equiv4\mod7\\
24^5\equiv3^5\equiv5\mod7\\
24^6\equiv3^6\equiv1\mod7\\
24^7\equiv3^7\equiv3\mod7\\
\end{aligned}$

La boucle est bouclée pour l'exposant 7 et on peut en conclure que $24^{6k+1}\equiv3\mod7$, où $k\in\N$.

\uline{Ainsi, le reste de la division euclidienne de $24^n$ par 7 est égal à 3 pour $n\equiv1\mod6$.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soient $a$ et $b$ deux nombres relatifs, tous les deux non divisibles par 3.

Montrer que $a^6-b^6$ est divisible par 3.

\tcblower

$a$ n'est pas divisible par 3 donc $a\equiv1\mod3$ ou $a\equiv2\mod3$. 

Ainsi, $a^6\equiv1^6\equiv1\mod3$ ou $a\equiv2^6\equiv64\equiv1\mod3$ car $64=3\times21+1$.

Ainsi, $a^6-b^6\equiv1-1\equiv0\mod3$ et donc \uline{$a^6-b^6$ est divisible par 3.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{équation $ax\equiv1\mod p$}
Soient $a$ et $p$ deux entiers naturels non nuls. Un inverse de $a$ modulo $p$, s'il existe, est un nombre $x$ tel que $ax\equiv1\mod p$.

Trouver tous les inverses, s'ils existent, de $a$ modulo $p$ dans les cas suivants :

\begin{enumerate}
\begin{multicols}{3}
\item $a=5$, $p=7$
\item $a=3$, $p=5$
\item $a=6$, $p=15$
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item On cherche $x$ tel que $5x\equiv1\mod7$. On constate que :
\begin{align*}
5\times1\equiv5\mod7\\
5\times2\equiv3\mod7\\
5\times3\equiv1\mod7
\end{align*}

Donc, si $x\equiv3\mod7$ alors $5x\equiv5\times3\equiv1\mod7$.

De plus, si $5x\equiv1\mod7$ alors $3\times5x\equiv3\mod7$, soit $15x\equiv3\mod7$ donc\linebreak $x\equiv3\mod3$.

On a alors l'équivalence suivante : $x\equiv3\mod7\iff5x\equiv1\mod7$.

\uline{Par conséquent, les inverses de 5 modulo 7 sont toutes les valeurs de $x$ telles que $x\equiv3\mod7$.}

\item On cherche $x$ tel que $3x\equiv1\mod5$. 

On constate que :
\begin{align*}
3\times1\equiv3\mod5\\
3\times2\equiv1\mod5
\end{align*}

On peut alors raisonner de la même façon qu'à la question précédente.

\uline{Par conséquent, un inverse de 3 modulo 5 sont toutes les valeurs de $x$ telles que $x\equiv2\mod5$.}

\item On cherche $x$ tel que $6x\equiv1\mod15$. 

On constate que :
\begin{align*}
6\times1\equiv6\mod15\\
6\times2\equiv12\mod15\\
6\times3\equiv3\mod15\\
6\times4\equiv9\mod15\\
6\times5\equiv0\mod15\\
6\times6\equiv6\mod15
\end{align*}
On constate alors que c'est un cas particulier : 
\[
\begin{cases}
6\times(1+5k)\equiv1\mod15,\ k\in\N\\
6\times(2+5k)\equiv12\mod15,\ k\in\N\\
6\times(3+5k)\equiv3\mod15,\ k\in\N\\
6\times(4+5k)\equiv9\mod15,\ k\in\N\\
6\times(5+5k)\equiv0\mod15,\ k\in\N
\end{cases}
\]
\uline{Par conséquent, il n'existe pas d'inverse à 6 modulo 15.}

\begin{rem}
Cela vient du fait que 6 et 15 ne sont pas premiers entre eux.
\end{rem}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ tel que $n\equiv1\mod2$, $n\equiv2\mod3$ et $n\equiv5\mod7$.

\medskip

Quel est le reste de la division euclidienne de $n$ par 42 ?

\tcblower

Nous avons:


$\left.
\begin{array}{l}
n\equiv1\mod2\iff21n\equiv21\mod42\\
n\equiv2\mod3\iff14n\equiv28\mod42\\
n\equiv5\mod7\iff6n\equiv30\mod42\\
\end{array}
\right\}\Rightarrow 41n\equiv79\mod42$.

\medskip

Or, $41\equiv-1\mod42$ et $79\equiv-5\mod42$ donc $-n\equiv-5\mod42$, soit $n\equiv5\mod42$.

\medskip

\uline{Le reste de la division euclidienne de $n$ par 42 est donc égal à 5.}
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que si 7 divise $a^2+b^2$, alors 7 divise $a$ et $b$.

La réciproque est-elle vraie ?

\tcblower

Supposons que 7 divise $a^2+b^2$.

Les restes possibles de la division euclidienne de $a$ par 7 sont : 0, 1, 2, 3, 4, 5 ou 6. 
\begin{align*}
a\equiv0\mod 7&\Rightarrow a^2\equiv0\mod7\\
a\equiv1\mod 7&\Rightarrow a^2\equiv1\mod7\\
a\equiv2\mod 7&\Rightarrow a^2\equiv4\mod7\\
a\equiv3\mod 7&\Rightarrow a^2\equiv9\equiv2\mod7\\
a\equiv4\mod 7&\Rightarrow a^2\equiv16\equiv2\mod7\\
a\equiv5\mod 7&\Rightarrow a^2\equiv25\equiv4\mod7\\
a\equiv6\mod 7&\Rightarrow a^2\equiv36\equiv1\mod7\\
\end{align*}
Il n'y a donc que 4 restes possibles dans la division euclidienne de $a^2$ par 7 : 0, 1, 2 ou 4.

\medskip

Il en est de même pour $b^2$. 

\medskip

Or, $a^2+b^2\equiv0\mod7$ donc seul le couple \coord{0}{0} convient.

\medskip

\uline{Ainsi $a\equiv0\mod7$ et $b\equiv0\mod7$, soit 7 divise $a$ et $b$.}

\bigskip

La réciproque est vraie car si 7 divise $a$ et $b$, alors $a^2\equiv0\mod7$ et $b^2\equiv0\mod7$, donc $a^2+b^2\equiv0\mod7$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Résoudre dans $\Z$ l'équation $x^2\equiv-11\mod100$.

\tcblower

\begin{align*}
x^2\equiv-11\mod100 
& \iff x^2\equiv300-11\mod100\\
& \iff x^2\equiv289\mod100\\
& \iff x^2\equiv17^2\mod100\\
& \iff \boxed{x\equiv17\mod100}
\end{align*}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item Montrer par récurrence que pour tout entier naturel $n$, $4^n\equiv1+3n\mod9$.
\item En déduire que $2^{2n}+15n-1\equiv0\mod9$ pour tout entier naturel $n$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item 
\begin{itemize}
\item Initialisation : $4^0=1$ et $1+3\times0=1$ donc $4^n\equiv1+3n\mod9$ est vraie pour $n=0$.

\item Hérédité : supposons que pour un entier $n$ fixé, $4^n\equiv1+3n\mod9$.

Alors, $4^{n+1}\equiv4\times(1+3n)\mod9$, soit $4^{n+1}\equiv4+12n\equiv4+3n\equiv1+3(n+1)\mod9$.

L'hérédité est alors vérifiée.
\end{itemize}

\uline{Ainsi, pour tout entier naturel $n$, $4^n\equiv1+3n\mod9$.}

\item $\begin{aligned}[t]
2^{2n}+15n-1 & \equiv4^n+15n-1\mod9\\
						 & \equiv1+3n+15n-1\mod9\\
						 & \equiv18n\mod9\\
						 & \equiv0\times n\mod9\\
						 & \equiv0\mod9.
\end{aligned}$
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{démonstration par récurrence}
Montrer que pour tout entier naturel $n$, $(n+1)(n+2)\cdots(2n-1)\times2n$ est divisible par $2^n$ et trouver le quotient correspondant.

\tcblower

Posons:
\[
{\cal P}_n \quad : \quad (n+1)(n+2)\cdots(2n-1)\times2n\equiv0\mod 2^n.
\]

Notons:
\[
A_n=(n+1)(n+2)\cdots(2n-1)\times2n.
\]

Montrons par récurrence que ${\cal P}_n$ est vraie pour tout entier naturel $n$.

\begin{itemize}
\item Initialisation : ${\cal P}_0$ est vraie car $A_0=1$ et $2^0=1$. On a donc bien $A_0\equiv0\mod1$.

\bigskip

\item Supposons que pour un entier $n$ fixé, ${\cal P}_n$ est vraie, donc que $A_n=2^nB_n$.

\medskip

$\begin{aligned}[t]
A_{n+1} & = A_n\times(2n+1)(2n+2)\\[8pt]
				& = 2^nB_n\times2(2n+1)(n+1)\\[8pt]
				& = 2^{n+1}B_n(2n+1)(n+1).
\end{aligned}$

\medskip

Ainsi, $A_{n+1}$ est divisible par $2^{n+1}$. L'hérédité est alors vérifiée.
\end{itemize}

\bigskip

\uline{Ainsi, ${\cal P}_n$ est vraie pour tout entier naturel $n$.}

\bigskip

$A_n=\dfrac{(2n)!}{n!}$ donc $\dfrac{A_n}{2^n}=\dfrac{(2n)!}{2^n(n!)}=1\times3\times5\times\cdots\times(2n-1)$.

\medskip

Le quotient de $A_n$ par $2^n$ est donc égal à $\displaystyle\prod_{k=0}^{n-1}(2k+1)$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{critère de divisibilité par 3}
\og Un nombre est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3. \fg{} 

\medskip

En notant:
\[
x = \sum_{k=0}^n x_k \times 10^k
\]
démontrer cette propriété.

\medskip

Démontrer que le critère de divisibilité par 9 est semblable.

\tcblower

On sait que $10 \equiv 1 \mod 3$ donc:
\[
\forall k\in\N,\qquad 10^k \equiv 1 \mod 3
\]
et donc:
\[
\sum_{k=0}^n x_k \times 10^k \equiv \sum_{k=0}^n x_k \mod 3.
\]
\begin{align*}
x \text{ est divisible par 3 } & \iff x\equiv 0 \mod 3\\[8pt]
& \iff  \sum_{k=0^N} x_k \equiv 0 \mod 3\\[8pt]
& \iff \text{ la somme des chiffres de x divise 3}.
\end{align*}

\medskip

$10 \equiv 1 \mod 9$ donc le critère de divisibilité par 9 est identique: un nombre est divisible par 9 si la somme de ses chiffres l'est aussi.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{critère de divisibilité par 11}
Soit $x$ un enter naturel s'écrivant:
\[
\sum_{k=0}^n x_k \times 10^k.
\]
Établir un critère de divisibilité par 11 de $x$ en partant de la congruence:
\[
10 \equiv -1 \mod 11.
\]
Tester le critère obtenu avec les nombres $37653$ et $7432$.

\tcblower

\[
10 \equiv -1 \mod 11 \iff \forall k\in\N,\ 10^k \equiv (-1)^k \mod 11.
\]
Ainsi,
\begin{align*}
x\text{ est divisible par 11} & \iff \sum_{k=0}^n x_k \times 10^k \equiv 0 \mod 11\\[10pt]
& \iff \sum_{k=0}^n x_k \times (-1)^k \equiv 0 \mod 11\\[10pt]
& \iff \sum_{p=0}^{\lfloor n/2 \rfloor} x_{2p} - \sum_{p=0}^{\lfloor n/2 \rfloor} x_{2p+1}\equiv 0\mod 11\\[10pt]
& \iff \sum_{p=0}^{\lfloor n/2 \rfloor} x_{2p} \equiv \sum_{p=0}^{\lfloor n/2 \rfloor} x_{2p+1}\mod 11.
\end{align*}

Ici, nous convenons de noter $\left\lfloor\dfrac{n}{2}\right\rfloor$ la partie entière inférieure de $\dfrac{n}{2}$.

Par exemple, $\left\lfloor\dfrac{7}{2}\right\rfloor=3$.

\medskip

Nous arrivons alors au critère de divisibilité suivant: \og un nombre est divisible par 11 si et seulement si la somme des chiffres de rangs pairs et congrue à celle des chiffres de rangs impairs modulo 11 \fg.

\bigskip

Essayons avec:

\begin{itemize}
\item \textbf{37653 :} $3+6+3 = 12$ et $5+7=12$. Nous obtenons la même somme donc 37653 est divisible par 11.

\item \textbf{7432 :} $2+4 = 6$ et $3+7=10$; les deux sommes ne sont pas congrues modulo 11 donc 7432 n'est pas divisible par 11.
\end{itemize}
\vspace*{2cm}~
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Trouver les chiffres $a$ et $b$ tels que le nombre $1a4b$ soit divisible par 45.

Proposer un code Python qui affiche tous les nombres possibles.

\tcblower

On a :
\begin{align*}
1a4b\text{ divisible par 45} & \iff 1a4b\text{ divisible par 5 et 9}\\[10pt]
& \iff 1a4b \equiv 0 \mod 5\text{ et }1a4b\equiv0\mod9\\[10pt]
& \iff b=0\text{ ou }b=5\text{ et }1+a+4+b\equiv0\mod9\\[10pt]
& \iff  b=0\text{ ou }b=5\text{ et }a+b\equiv-5\equiv4\mod9.
\end{align*}
\begin{itemize}
\item si $b=0$ alors $a=4$;
\item si $b=5$ alors $a=8$.
\end{itemize}
Les deux nombres possibles sont alors $1845$ et $1440$.

\bigskip

Pour contrôler nos résultats, on va utiliser le programme suivant.

Dans ce programme, on va se servir de la conversion des nombres en chaîne de caractères: si \texttt{n} est un objet de type \texttt{int} (entier) alors \texttt{str(n)} est le même nombre, mais vu comme une chaîne de caractères, où \texttt{str(n)[0]} est le premier chiffre en partant de la gauche.

\begin{console}
>>> for n in range(10000):
    	if n%45==0 and str(n)[0]=='1' and str(n)[2]=='4':
        	print(n)
        
1440
1845
\end{console}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Démontrer par récurrence que pour tout entier naturel $n$, $3^{2n}-2^n$ est divisible par 7.

\tcblower

\begin{itemize}
\item \textbf{Initialisation:} pour $n=0$, $3^{2n}-2^n=0$ est divisible par 7.

\item \textbf{Hérédité:} supposons que pour un entier naturel $k$ fixé, $3^{2n}-2^n$ est divisible par 7.

Alors, $3^{2n}-2^n \equiv0\mod7$, soit $3^{2n} \equiv 2^n \mod 7$.

\begin{align*}
3^{2(n+1)}-2^{n+1} & \equiv 3^{2n}\times3^2 - 2^{n+1}\mod7 & \\[10pt]
& \equiv 2^n\times9 - 2^{n+1}\mod7 & \text{par hypothèse de récurrence}\\[10pt]
& \equiv 2^n\times2 - 2^{n+1}\mod7 & \text{car }9\equiv2\mod7\\[10pt]
& \equiv2^{n+1}-2^{n+1}\mod7 & \\[10pt]
& \equiv 0\mod 7.
\end{align*}

L'hérédité est alors vérifiée.
\end{itemize}

Ainsi, pour tout entier naturel $n$, $3^{2n}-2^n$ est divisible par 7.
\end{exocor}

\subsection*{PGCD}

\begin{exocor}{algorithme d'Euclide}
En utilisant l'algorithme d'Euclide, calculer le PGCD des nombres suivants.
\begin{enumerate}
\begin{multicols}{4}
\item \numprint{2070} et 432
\item \numprint{1065} et 235
\item 363 et 792
\item 858 et 910
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\begin{multicols}{2}
\item $\begin{aligned}[t]
\numprint{2070} & = 4 \times 432 + 342\\
 432 & = 1 \times 342 + 90\\
 342 & = 3 \times  90 + 72\\
  90 & = 1 \times  72 + 18\\
  72 & = 4 \times  18 + 0.
\end{aligned}$

\bigskip

Ainsi, $\pgcd{\numprint{2070}}{432}=18$.

\item $\begin{aligned}[t]
\numprint{1065} & = 4 \times 235 + 125\\
 235 & = 1 \times 125 + 110\\
 125 & = 1 \times 110 + 15\\
 110 & = 7 \times  15 + 5\\
  15 & = 3 \times   5 + 0.
\end{aligned}$

\bigskip

Ainsi, $\pgcd{\numprint{1065}}{235}=5$.
\end{multicols}

\bigskip

\begin{multicols}{2}
\item $\begin{aligned}[t]
792& = 2 \times 363 + 66\\
 363 &= 5 \times  66 + 33\\
  66 &= 2 \times  33 + 0.
\end{aligned}$

\bigskip

Ainsi, $\pgcd{792}{363}=33$.

\item $\begin{aligned}[t]
910 &= 1 \times 858 + 52\\
 858 &= 16 \times  52 + 26\\
  52 &= 2 \times  26 + 0.
\end{aligned}$

\bigskip

Ainsi, $\pgcd{910}{858}=26$.
\end{multicols}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{algorithme d'Euclide}
En utilisant l'algorithme d'Euclide de manière astucieuse, trouver un couple d'entiers \coord{x}{y} tel que $23x+32y=1$.

\tcblower

On a: $\begin{aligned}[t]
32 &= 1 \times  23 + 9\\
  23 &= 2 \times   9 + 5\\
   9 &= 1 \times   5 + 4\\
   5 &= 1 \times   4 + 1\\
   4 &= 4 \times   1 + 0.
\end{aligned}$

Ainsi, de l'avant dernière ligne, on peut écrire:
\begin{align*}
1 & = 5 - 4\\
& = (23 - 2\times9) - (9-5)\\
& = 23-2\times(32-23) - (32-23) + (23-2\times9)\\
& = 23-2\times(32-23) - (32-23) + 23-2\times(32-23)\\
& = 23 - 2\times32 + 2\times23 - 32 + 23 + 23 - 2\times32 + 2\times23\\
& = 7\times23 -5\times32.
\end{align*}

\medskip

Un couple solution de l'équation $23x+32y=1$ est donc \coord{7}{-5}.
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{système avec PGCD}
Déterminer tous les couples d'entiers naturels non nuls $x$ et $y$ tels que $\begin{cases}
x+y=\numprint{5664}\\
\pgcd{x}{y}=354
\end{cases}$.

\tcblower

$\pgcd{x}{y}=354 \iff \exists \coord{x'}{y'}\in\N,\ x=354x',\ y=354y',\ \pgcd{x'}{y'}=1$.

Ainsi, $x+y=\numprint{5664} \iff 354x'+354y'=\numprint{5664}\iff x'+y'=16$.

On cherche donc deux entiers $x'$ et $y'$ premiers entre eux dont la somme vaut 16. On peut en faire la liste:
\begin{itemize}
\begin{multicols}{4}
\item $\coord{x'}{y'}=\coord{1}{15}$
\item $\coord{x'}{y'}=\coord{3}{13}$
\item $\coord{x'}{y'}=\coord{5}{11}$
\item $\coord{x'}{y'}=\coord{7}{9}$
\item $\coord{x'}{y'}=\coord{9}{7}$
\item $\coord{x'}{y'}=\coord{11}{5}$
\item $\coord{x'}{y'}=\coord{13}{3}$
\item $\coord{x'}{y'}=\coord{15}{1}$
\end{multicols}
\end{itemize}
En multipliant ces valeurs par 354, on obtient tous les couples \coord{x}{y}:
\begin{itemize}
\begin{multicols}{2}
\item $\coord{x}{y}=\coord{354}{\numprint{5310}}$
\item $\coord{x}{y}=\coord{\numprint{1062}}{\numprint{4602}}$
\item $\coord{x}{y}=\coord{\numprint{1770}}{\numprint{3894}}$
\item $\coord{x}{y}=\coord{\numprint{2478}}{\numprint{3186}}$
\item $\coord{x}{y}=\coord{\numprint{3186}}{\numprint{2478}}$
\item $\coord{x}{y}=\coord{\numprint{3894}}{\numprint{1770}}$
\item $\coord{x}{y}=\coord{\numprint{4602}}{\numprint{1062}}$
\item $\coord{x}{y}=\coord{\numprint{5310}}{\numprint{354}}$
\end{multicols}
\end{itemize}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{système avec PGCD}
Déterminer tous les couples d'entiers naturels non nuls $x$ et $y$ tels que $\begin{cases}
xy=\numprint{1734}\\
\pgcd{x}{y}=17
\end{cases}$.

\tcblower

$\pgcd{x}{y}=17 \iff \exists \coord{x'}{y'}\in\N,\ x=17x',\ y=17y',\ \pgcd{x'}{y'}=1$.

Ainsi,
\[
xy=\numprint{1734} \iff 17x'+17y'=\numprint{1734}\iff x'y'=102.
\]
On cherche donc deux entiers $x'$ et $y'$ premiers entre eux dont le produit vaut $102=2\times3\times17$. Les possibilités sont les suivantes:
\begin{itemize}
\begin{multicols}{3}
\item $\coord{x'}{y'}=\coord{6}{17}$
\item $\coord{x'}{y'}=\coord{2}{51}$
\item $\coord{x'}{y'}=\coord{1}{102}$
\item $\coord{x'}{y'}=\coord{102}{1}$
\item $\coord{x'}{y'}=\coord{51}{2}$
\item $\coord{x'}{y'}=\coord{17}{6}$
\end{multicols}
\end{itemize}
En multipliant par 17 toutes ses possibilités, on obtient les couples \coord{x}{y}:
\begin{itemize}
\begin{multicols}{3}
\item $\coord{x'}{y'}=\coord{102}{289}$
\item $\coord{x'}{y'}=\coord{34}{867}$
\item $\coord{x'}{y'}=\coord{17}{\numprint{1734}}$
\item $\coord{x'}{y'}=\coord{\numprint{1734}}{17}$
\item $\coord{x'}{y'}=\coord{867}{34}$
\item $\coord{x'}{y'}=\coord{289}{102}$
\end{multicols}
\end{itemize}
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soient $a=3n+1$ et $b=5n-1$, où $n$ est un entier naturel.
\begin{enumerate}
\item Montrer que $\pgcd{a}{b}$ divise 8.
\item Montrer que si $n=8k+5$, $k\in\N$, alors $\pgcd{a}{b}=8$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\pgcd{a}{b}$ divise $a$ et $b$, donc divise $a+b=8n$, multiple de 8.

Par conséquent, $\pgcd{a}{b}$ divise 8.

\item $n=8k+5$ donc :
\begin{itemize}
\item $a=3(8k+5)+1=24k+16=8(3k+2)$,
\item $b=5(8k+5)-1=40k+24=8(5k+3)$.
\end{itemize}
Ainsi, 8 divise $a$ et $b$, donc 8 divise $\pgcd{a}{b}$.

Or, $\pgcd{a}{b}$ divise 8 d'après la question précédente.

Par conséquent, $\pgcd{a}{b}=8$.
\end{enumerate}
\end{exocor}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soient $n$, $a$ et $b$ trois entiers naturels.

Montrer que si $n$ divise pgcd\coord{a}{b} alors $n$ divise $x$, où $x\equiv a\mod b$.

\tcblower

$\begin{aligned}[t]
n\text{ divise pgcd}\coord{a}{b} & \Rightarrow n\equiv0\mod a\text{  et  }n\equiv0\mod b\\
& \Rightarrow \begin{cases}a=kn\\b=k'n\end{cases}\quad,\quad \coord{k}{k'}\in\N\times\N
\end{aligned} $

\medskip

Or, $x\equiv a\mod b$ donc $x=bq+a$, $q\in\N$, soit $x=k'nq+kn=n(k'q+k)$.

Ainsi, $n$ divise $x$.
\end{exocor}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
On pose $x=9(k+3)$ et $y=4k$, où $k\in\Z$.

Montrer que \pgcd{x}{y} divise 108.

\tcblower

Utilisons l'algorithme des différences (et donc la propriété : $\pgcd{a}{b}=\pgcd{a}{b-a}$) pour démontrer le résultat :
\begin{align*}
\pgcd{x}{y} 
& = \pgcd{9k+27}{4k}\\
& \textcolor{gray}{= \pgcd{4k}{9k+27-4k}}\\
& = \pgcd{4k}{5k+27}\\
& \textcolor{gray}{= \pgcd{5k+27}{5k+27-4k}}\\
& = \pgcd{5k+27}{k+27}\\
& \textcolor{gray}{= \pgcd{k+27}{5k+27-(k+27)}}\\
& = \pgcd{k+27}{4k}\\
& \textcolor{gray}{= \pgcd{k+27}{4k-(k+27)}}\\
& = \pgcd{k+27}{3k-27}\\
& \textcolor{gray}{= \pgcd{k+27}{3k-27-(k+27)}}\\
& = \pgcd{k+27}{2k-54}\\
& \textcolor{gray}{= \pgcd{k+27}{2k-54-(k+27)}}\\
& = \pgcd{k+27}{k-81}\\
& \textcolor{gray}{= \pgcd{k+27}{k+27-(k-81)}}\\
& = \pgcd{k+27}{108}.
\end{align*}
Or, \pgcd{k+27}{108} divise 108 (par définition) donc \pgcd{x}{y} divise 108.
\end{exocor}

\subsection*{Théorème de Bézout}

\begin{exocor}{}
Soit $n$ un entier naturel.
\begin{enumerate}
\item Montrer que $3n+7$ et $n+2$ sont premiers entre eux.
\item Montrer que $3n+4$ et $2n+3$ sont premiers entre eux.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Pour $n=0$, $3n+7=7$ et $n+2=2$ sont bien premiers entre eux.

Soit $n\in\N*$. Nous allons chercher une combinaison linéaire de $3n+7$ et $n+2$ qui est égale à 1: on regarde les termes en $n$ et on s'aperçoit qu'en multipliant par 3 le deuxième nombre, on a:
\[
(3n+7) - 3(n+2) = 1.
\]
Il existe donc une combinaison linéaire de ces deux nombres qui est égale à 1; par conséquent, ils sont premiers entre eux d'après le théorème de Bézout.

\item De la même façon que dans la question précédent, on a:
\[
-2(3n+4) + 3(2n+3) = 1.
\]
Donc $3n+4$ et $2n+3$ sont premiers entre eux pour $n\in\N*$.

Pour $n=0$, 4 et 3 sont bien premiers entre eux.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n$ un entier naturel.
\begin{enumerate}
\item Montrer que $2n+1$ et $3n+2$ sont premiers entre eux.
\item Montrer que $7n+4$ et $5n+3$ sont premiers entre eux.
\end{enumerate}

\tcblower

\begin{enumerate}
\item On a: $-3(2n+1) + 2(3n+2) = 1$.

Il existe une combinaison linéaire de $2n+1$ et $3n+2$ égale à 1. Donc, d'après le théorème de Bézout, $2n+1$ et $3n+2$ sont premiers entre eux.

\item On a :
\[
-5(7n+4) + 7(5n+3) = 1.
\]
Il existe une combinaison linéaire de $7n+4$ et $5n+3$ égale à 1. 

\bigskip

Donc, d'après le théorème de Bézout,  $7n+4$ et $5n+3$ sont premiers entre eux.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soit $n\geqslant2$ un entier naturel.

Montrer que $n$ et $n^2-1$ sont premiers entre eux.

\tcblower

On a:
\[
n\times n - (n^2-1) = 1.
\]
Donc il existe un couple $\coord{u}{v}=\coord{n}{-1}$ tel que $nu+(-1)(n^2-1)=1$.

\bigskip

Ainsi, d'après le théorème de Bézout, $n$ et $n^2-1$ sont premiers entre eux.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que 99 et 56 sont premiers entre eux en déterminant deux entiers $u$ et $v$ tels que $99u+56v=1$.

\tcblower

On a:
\begin{align*}
99& = 1 \times  56 + 43\\
  56 &= 1 \times  43 + 13\\
  43 &= 3 \times  13 + 4\\
  13 &= 3 \times   4 + 1\\
   4 &= 4 \times   1 + 0.
\end{align*}
En \og remontant \fg, on a :
\begin{align*}
1 & = 13 - 3\times4\\
  & = (56-43) - 3(43-3\times13)\\
  & = 56 - 4\times43 + 9\times13\\
  & = 56 - 4\times(99-56) + 9(56-43)\\
  & = 14\times56 -4\times99 - 9\times43\\
  & =  14\times56 -4\times99 - 9(99-56)\\
  & = 23\times56 -13\times99.
\end{align*}
Il existe donc un couple $\coord{u}{v}=\coord{-13}{23}$ tel que $99u+56v=1$.

\bigskip

Ainsi, d'après le théorème de Bézout, $\pgcd{99}{56}=1$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{condition d'inversibilité}
Soient $a$ et $p$ deux entiers naturels non nuls. $a$ est dit \textit{inversible modulo $p$}, s'il existe un nombre $x$ tel que $ax\equiv1\mod p$.

Montrer que $a$ est inversible modulo $p$ si et seulement si $\pgcd{a}{p}=1$.

\tcblower

\vspace*{-1em}
\begin{align*}
a\text{ est inversible modulo }p & \iff \exists\ x \in\N*\;|\; ax\equiv1\mod p\\
& \iff \exists\ (x,y) \in\N*\times\N\;|\; ax=py+1\\
& \iff \exists\ (x,y) \in\N*\times\N\;|\; ax-py=1\\
& \iff \exists\ (x,y) \in\N*\times\N\;|\; ax+p(-y)=1\\
& \iff \pgcd{a}{p}=1\text{ d'après le théorème de Bézout.}
\end{align*}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item Calculer $\pgcd{550}{693}$.
\item Déterminer un couple \coord{u}{v} tel que $550u+693v=11$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
693 &= 1 \times 550 + 143\\
 550& = 3 \times 143 + 121\\
 143 &= 1 \times 121 + 22\\
 121& = 5 \times  22 + 11\\
  22 &= 2 \times  11 + 0.
\end{aligned}$

\medskip

Ainsi, $\pgcd{550}{693}=11$.

\item $\begin{aligned}[t]
11 & = 121 - 5\times22\\
   & = (550 - 3\times143) - 5\times(143-121)\\
   & = 550 - 3\times(693-550) - 5\big[(693-550) - 550 + 3(693-550)\big]\\
   & = 550 - 3\times693 + 3\times550 - 5\times693 + 10\times550 - 15\times693 + 15\times550\\
   & = 29\times550 - 23\times693.
\end{aligned}$

\medskip

Un couple \coord{u}{v} tel que $550u+693v=11$ est donc \coord{29}{-23}.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soient $a$, $b$ et $c$ trois entiers naturels tels que $bc>a$.

Montrer que $\pgcd{bc-a}{b}=\pgcd{a}{b}$ à l'aide du théorème de Bézout.

\tcblower

Notons $d=\pgcd{bc-a}{b}$.

\begin{itemize}
\item D'après l'égalité de Bézout, il existe un couple d'entiers relatifs $\coord{u}{v}$ tel que \mbox{$(bc-a)u+bv=d$}.
\begin{align*}
(bc-a)u+bv=d & \iff bcu-au+bv=d\\
						 & \iff a(-u) + b(cu+v) = d
\end{align*}

$-u\in\Z$ et $(cu+v)\in\Z$ donc il existe un couple d'entiers relatifs \coord{u'}{v'}, avec $u'=-u$ et $v'=cu+v$, tel que $au'+bv'=d$.

Donc $\pgcd{a}{b}$ divise $d$.

\medskip

\item De plus, $d=\pgcd{bc-a}{b} \Rightarrow d|b\text{ et } d|(bc-a) \Rightarrow d|a$ car si $d|b$, alors $d|(bc)$ donc si $d|(bc-a)$, alors nécessairement, $d|a$.

Ainsi, $d|a$ et $d|b$ donc $d|\pgcd{a}{b}$
\end{itemize}

\uline{Finalement, $\pgcd{a}{b}|d$ et $d|\pgcd{a}{b}$ donc $d=\pgcd{a}{b}$.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que si $a$ et $b$ sont premiers entre eux, alors $3a+5b$ et $a+2b$ sont également premiers entre eux.

\tcblower

$\pgcd{a}{b}=1$ donc il existe un couple d'entiers relatifs {u}{v} tel que :
\[au+bv=1.\]
Nous allons montrer qu'il existe un couple d'entiers relatifs {u'}{v'} tel que:
\[
(3a+5b)u'+(a+2b)v'=1.
\]
\begin{align*}
(3a+5b)u'+(a+2b)v' 
& = 3au'+5bu'+av'+2bv'\\
& = a(3u'+v')+b(5u'+2v').
\end{align*}

Pouvons-nous choisir $u'$ et $v'$ de sorte que 
$\begin{cases}
3u'+v'=u & (L_1)\\
5u'+2v'=v & (L_2)
\end{cases}$ ?

\bigskip

Pour répondre à cette question, cherchons à résoudre ce dernier système.

\medskip

En faisant $2(L_1)-(L_2)$, on obtient :
\[
u'=2u-v
\]
et en faisant $-5(L_1)+3(L_2)$, on obtient :
\[
v'=-5u+3v.
\]
En prenant ces valeurs de $u'$ et $v'$, on a $(3a+5b)u'+(a+2b)v'=au+v=1$.

\uline{Ainsi, d'après le théorème de Bézout, $\pgcd{3a+5b}{a+2b}=1$.}
\end{exocor}


\subsection*{Théorème de Gauss}

\begin{exocor}{}
\begin{enumerate}
\item Déterminer \pgcd{31}{28} à l'aide de l'algorithme d'Euclide.

Trouver alors deux nombres relatifs $x$ et $y$ tels que $31x-28y=1$.

\item Résoudre dans $\Z\times\Z$ l'équation $31x-28y=1$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
31 & = 1\times28+3\\
28 & = 9\times3+1\\
3  & = 3\times1+0
\end{aligned}$

\uline{Donc $\pgcd{31}{28}=1$.}

\bigskip

De l'algorithme précédent, on peut écrire :

\begin{align*}
1 & = 28-9\times3\\
  & = 28 - 9\times(31-28)\\
  & = 10\times28-9\times31
\end{align*}

Ainsi, si $x=-9$ et $y=-10$, $31x-28y=1$.

\item On a :
\[
\begin{array}{c@{\;\times\;}c@{\;-\;}c@{\;\times\;}c@{\;=\;}c}
31 & (-9) & 28 & (-10) & 1\\
31 &   x  & 28 &   y   & 1\\
\hline
31 & (-9-x) & 28 & (-10-y) & 0
\end{array}
\]
Ainsi :
\[
31(-9-x)=28(-10-y).
\]
Or, $\pgcd{31}{28}=1$ donc d'après le théorème de Gauss, 31 divise $(-10-y)$ et 28 divise $(-9-x)$ :
\[
\begin{cases}
-9-x & = 28k\\
-10-y & = 31k
\end{cases}\quad,\quad k\in\Z
\]
soit :
\[
\boxed{
\begin{cases}
x & = -9-28k\\
y & = -10-31k
\end{cases}\quad,\quad k\in\Z}
\]
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Résoudre dans $\Z\times\Z$ l'équation $108x+55y=1$.

\tcblower

\begin{enumerate}
\item $\begin{aligned}[t]
108 & = 1\times55+53\\
55 & = 1\times53+2\\
53 & = 26\times2+1\\
2  & = 2\times1+0
\end{aligned}$

\uline{Donc $\pgcd{108}{55}=1$.}

De l'algorithme précédent, on peut écrire :

$\begin{aligned}[t]
1 & = 53-26\times2\\
  & = (108-55)-26\times(55-53)\\
  & = 108-55-26\times55+26\times53\\
  & = 108-27\times55+26(108-55)\\
  & = 27\times108 -53\times55
\end{aligned}$

Ainsi, si $x_0=27$ et $y_0=-53$ sont deux solutions particulières de l'équation diophantienne $108x+55y=1$.

\item On a :
\[
\begin{array}{c@{\;\times\;}c@{\;+\;}c@{\;\times\;}c@{\;=\;}c}
108 & 27 & 55 & (-53) & 1\\
108 & x  & 55 &   y   & 1\\
\hline
108 & (27-x) & 55 & (-53-y) & 0
\end{array}
\]
Ainsi :
\[
108(27-x)=55(53+y).
\]
Or, $\pgcd{108}{55}=1$ donc d'après le théorème de Gauss, 108 divise $(53+y)$ et 55 divise $(27-x)$ :
\[
\begin{cases}
27-x & = 55k\\
53+y & = 108k
\end{cases}\quad,\quad k\in\Z
\]
soit :
\[
\boxed{
\begin{cases}
x & = 27-55k\\
y & = -53+108k
\end{cases}\quad,\quad k\in\Z}
\]
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{trouver le nombre d'hommes et de femmes}
Au 8\ieme{} siècle, un groupe composé d'hommes et de femmes a dépensé 100 pièces de monnaie dans une
auberge. Les hommes ont dépensé 8 pièces chacun et les femmes 5 pièces chacune. 

\medskip

Combien pouvait-il y avoir d'hommes et de femmes dans le groupe ?

\tcblower

Notons $x$ le nombre d'hommes et $y$ celui de femmes.

L'énoncé nous donne alors l'équation :
\[
8x+5y=100.
\]

Avant tout, trouvons une solution particulière à cette équation. 

Il faut que $y=\dfrac{100-8x}{5}=\dfrac{100}{5}-\dfrac{8x}{5}=20-\dfrac{8x}{5}$ soit entier, donc que $8x$ soit un multiple de 5. 

Prenons alors $x=5$ et donc $y=20-8=12$.

Une solution particulière est donc $\coord{x_0}{y_0}=\coord{5}{12}$.

On a alors :
\[
\begin{array}{c@{\;\times\;}c@{\;+\;}c@{\;\times\;}c@{\;=\;}c}
8 & 5 & 5 & 12 & 100\\
8 & x & 5 &  y & 100\\
\hline
8 & (5-x) & 5 & (12-y) & 0
\end{array}
\]
soit :
\[
8(5-x)=5(y-12).
\]
$\pgcd{8}{5}=1$ donc d'après le théorème de Gauss, 8 divise $(y-12)$ et 5 divise $(5-x)$ :
\[
\begin{cases}
5-x&=5k\\
y-12&=8k
\end{cases}\quad,\quad k\in\Z
\]
soit :
\[
\begin{cases}
x&=5-5k\\
y&=12+8k
\end{cases}\quad,\quad k\in\Z.
\]
On sait que $\coord{x}{y}\in\N*\times\N*$ ce qui nous laisse peu de choix quant aux valeurs de $k$ :
\begin{itemize}
\item $k=0$ : on a alors $x=5$ et $y=12$;
\item $k=-1$: on a alors $x=10$ et $y=4$.
\end{itemize}

\uline{Il y avait donc 5 hommes et 12 femmes, ou 10 hommes et 4 femmes.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newpage

\subsection*{Nombres premiers}

\begin{exocor}{}
\numprint{1789} est-il un nombre premier ?

\tcblower

Rappelons que si $p$ est un nombre premier, alors il n'admet aucun diviseurs inférieurs à $\sqrt{p}$.

\medskip

$\sqrt{\numprint{1789}}\approx42,3$.

Les nombres premiers inférieurs à 42 sont :
\[
2;3;5;7;11;13;17;19;23;29;31;37;41.
\]
On vérifie que aucun d'entre eux ne divisent \numprint{1789}.

\uline{Par conséquent, \numprint{1789} est un nombre premier.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item \'Etablir la liste des nombres premiers inférieurs à 50.
\item Le nombre \numprint{1517} est-il premier ?
\item Déterminer tous les entiers naturels $a$ et $b$ tels que $a^2=b^2+\numprint{1517}$.
\end{enumerate}

\tcblower

\begin{enumerate}
\item La liste des nombres premiers inférieurs à 50 est:
\begin{center}
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
\end{center}

\item $\sqrt{\numprint{1517}}\approx38,95$.

On teste alors si les nombres premiers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 divisent \numprint{1517}.

\begin{console}
>>> L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
>>> for i in L:
    	if 1517%i == 0: print(i)
 37
\end{console}

On trouve que 37 divise \numprint{1517} donc \numprint{1517} n'est pas premier.

\item $\begin{aligned}[t]
a^2=b^2+\numprint{1517} & \iff a^2-b^2=\numprint{1517}\\
                        & \iff (a-b)(a+b)=37\times41\\
                        & \iff \begin{cases}
                        a-b=37\\
                        a+b=41
                        \end{cases}\\
                        & \iff a = 39 \text{ et } b=2.
\end{aligned}$

\medskip

\uline{Ainsi, le seul couple $\coord{a}{b}\in\N^2$ tel que $a^2=b^2+\numprint{1517}$ est \coord{39}{2}.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
En utilisant l'égalité:
\[
a^3-b^3 = (a-b)(a^2 + ab + b^2)
\]
trouver les valeurs de l'entier naturel $n$ pour lesquelles $n^3-27$ est un nombre premier.

\tcblower

On a:
\[
n^3-27 = n^3-3^3 = (n-3)(n^2+3n+9).
\]
Ainsi,
\begin{align*}
n^3-27 \in\mathbb{P} & \iff n-3=1\text{ ou }n^2+3n+9=1\\
& \iff n=4.
\end{align*}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Pour quel(s) nombre(s) premier(s) $p$ l'entier naturel $7p+1$ est-il un carré parfait ?

\tcblower

$\begin{aligned}[t]
7p+1 \text{ est un carré parfait} \iff \exists n\in\N,\ 7p+1=n^2\\
& \iff n^2-1=7p\\
& \iff (n+1)(n-1)=7p\\
& \iff \begin{cases}
n+1=7\\
n-1=p
\end{cases}\qquad\text{ou}\qquad\begin{cases}
n+1=p\\
n-1=7
\end{cases}\\
& \iff n=\frac{p+7}{2}.
\end{aligned}$
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
\begin{enumerate}
\item Montrer que pour tout entier naturel $n$, les nombres $n$, $n+2$ et $n+10$ sont distincts modulo 3.

\item En déduire que l'on ne peut pas trouver un entier naturel $n>3$ tel que $n$, $n+2$ et $n+10$ soient tous les trois premiers.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Rappelons que $a$ et $b$ sont distincts modulo 3 si et seulement si $(a-b)$ est un multiple de 3.

\medskip

$n-(n+2)=-2$ n'est pas un multiple de 3, donc $n$ n'est pas congru à $n+2$ modulo 3.

$n-(n+10)=-10$ donc même conclusion.

$(n+2)-(n+10)=-8$ donc même conclusion.

\medskip

\uline{Ainsi, $n$, $n+2$ et $n+10$ sont distincts modulo 3.}

\item Notons $n\equiv r_1\mod3$, $n+2\equiv r_2\mod3$ et $n+10\equiv r_3\mod 3$.

D'après la question précédente, $r_1$, $r_2$ et $r_3$ dont deux à deux distincts. Or, il n'existe que 3 restes possibles dans la division euclidienne par 3 : 0, 1 ou 2.

Par conséquent, l'un des restes est nul et donc, l'un des nombres $n$, $n+2$ et $n+10$ est divisible par 3. Ce nombre n'est donc pas premier car il ne peut pas être égal à 3 (par hypothèse : $n>3$).
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que si $p$ et $8p^2+1$ sont premiers alors $p=3$.

\tcblower

\begin{itemize}
\item Si $p\equiv0\mod3$, alors $p$ est un multiple de 3. Or, $p$ est premier donc $p=3$ nécessairement.

\item Si $p\equiv1\mod3$, alors $p^2\equiv1\mod3$ et donc $8p^2\equiv8\equiv2\mod3$, soit\\ $8p^2+1\equiv0\mod3$.

Donc $8p^2+1$ est un multiple de 3 et aussi premier. Donc $8p^2+1=3$, ce qui est impossible car $p\in\N$.

Ainsi, $p$ ne peut pas être congru à 1 modulo 3.

\item Si $p\equiv2\mod3$, alors $8p^2+1\equiv0\mod3$, ce qui nous ramène à la même conclusion qu'au point précédent.
\end{itemize}

Ainsi, $p\in\mathbb{P}$ et $8p^2+1\in\mathbb{P}$ $\iff p=3$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer par l'absurde que si $p$ est un nombre premier, alors il n'existe pas de rationnel $x$ tel que $x^2=p$.

\tcblower

Raisonnons par l'absurde ; supposons donc qu'il existe un rationnel $x=\dfrac{a}{b}$ tel que $x^2=p$ et $\pgcd{a}{b}=1$.

Alors, $\dfrac{a^2}{b^2}=p$, soit $a^2=pb^2$.

D'après le théorème de Gauss, $p$ divise donc $a^2$, donc $p$ divise $a$ et alors $p^2$ divise $a^2$, donc divise $pb^2$. Ainsi, $p$ divise $b^2$, donc $p$ divise $b$.

Or, $pgcd\coord{a}{b}=1$ donc il n'est pas possible que $p$ divise à la fois $a$ et $b$.

\medskip

On aboutit à une contradiction ; par conséquent, notre hypothèse de départ est fausse.

\uline{Ainsi, il n'existe pas de rationnel $x$ tel que $x^2=p$.}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{exocor}{}
Soit $n$ un entier naturel non nul.

On pose alors $a_n=2n$ et $b_n=3n+1$.

Démontrer l'équivalence suivante :
\[
\pgcd{a_n}{b_n}=1 \iff n\in2\N*
\]
où $2\N*$ est l'ensemble des entiers naturels pairs non nuls.

\tcblower

\begin{align}
3n+1 & = 2n+(n+1)\qquad,\qquad n+1<2n\text{ donc }n>1\\
2n   & = 1\times(n+1)+(n-1)\qquad,\qquad n-1<n+1\text{(toujours vrai)}\\
n+1  & = 1\times(n-1) + 2\qquad,\qquad2<n-1\text{ donc }n>3.\label{eqexspear17}
\end{align}

Deux cas se présentent pour $n>3$ :

\begin{itemize}
\item $n\in2\N \iff n=2k$, $k\in\N$. Alors, l'égalité \ref{eqexspear17} donne :
\begin{align*}
2k+1 & = (2k-1)+2\\
2k-1 & = k + (k-1)\\
k & = (k-1)+\pmb{1}
\end{align*}
Dans ce cas, $\pgcd{a_n}{b_n}=1$.

\item $n\notin2\N \iff n=2k+1$, $k\in\N$. Alors, l'égalité \ref{eqexspear17} donne :
\begin{align*}
(2k+1)+1 & = (2k+1-1)+\pmb{2}\\
2k & = 2k+0
\end{align*}

Dans ce cas, $\pgcd{a_n}{b_n}=2$.
\end{itemize}

De plus,
\begin{itemize}
\item Pour $n=1$ : $a_1=2$ et $b_1=4$ donc $\pgcd{a_1}{b_1}=2$.
\item Pour $n=2$ : $a_2=4$ et $b_2=7$ donc $\pgcd{a_2}{b_2}=1$.
\item Pour $n=3$ : $a_3=6$ et $b_3=10$ donc $\pgcd{a_3}{b_3}=2$.
\end{itemize}

On a donc bien :
\[
\pgcd{a_n}{b_n}=1 \iff n\in2\N*.
\]
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Décomposer en produit de facteurs premiers les nombres suivants, puis calculer le nombre de leurs diviseurs.
\begin{enumerate}
\begin{multicols}{4}
\item \numprint{1345}
\item 456
\item \numprint{1650}
\item 360
\end{multicols}
\end{enumerate}

\tcblower

\begin{enumerate}
\item \begin{tabular}[t]{r|l}
1345 & 5\\
269 & 269\\
1& 
\end{tabular}

Ainsi, \numprint{1345} admet 4 diviseurs:\\1, 5, 269 et \numprint{1345}

\item \begin{tabular}[t]{r|l}456&2\\228&2\\114&2\\57&3\\19&19\\1&\\\end{tabular}

Ainsi, $456=2^3\times3\times19$.

Les diviseurs de 456 sont alors de la forme $2^\alpha\times3^\beta\times19^\gamma$ avec $\alpha\in\{0;1;2;3\}$, $\beta\in\{0;1\}$ et $\gamma\in\{0;1\}$.

Il y a alors 4 choix pour $\alpha$, 2 pour $\beta$ et $\gamma$ et donc $4\times2\times2=16$ diviseurs de 456.

\item \begin{tabular}[t]{r|l}1650&2\\825&3\\275&5\\55&5\\11&11\\1&\\\end{tabular}

Ainsi, $\numprint{1650}=2\times3\times5^2\times11$.
Les diviseurs de \numprint{1650} sont donc de la forme $2^\alpha\times3^\beta\times5^\gamma\times11^\delta$, avec $\alpha$, $\beta$ et $\delta$ dans $\{0;1\}$ et $\gamma\in\{0;1;2\}$.

Par conséquent, \numprint{1650} possède alors $2\times2\times2\times3=24$ diviseurs.

\item \begin{tabular}[t]{r|l}360&2\\180&2\\90&2\\45&3\\15&3\\5&5\\1&\\\end{tabular}

Ainsi, $360=2^3\times3^2\times5$ et donc, 360 admet $4\times3\times2=24$ diviseurs.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%


\begin{exocor}{}
Compléter la fonction Python suivante afin qu'elle retourne un dictionnaire dont les clés sont les diviseurs de $n$ et leur valeur, les exposants des diviseurs dans la décomposition en produit de facteurs premiers de $n$.

\medskip

\begin{python}
def decomp(n):
    D = dict() # dictionnaire vide
    
    k = 2
    
    while n ...:
        exposant = 0
        while n%k == 0:
            exposant = ...
            n = ...
        if exposant != 0:
            D[k] = exposant
        k = k+1
        j = 2
        while k%j == 0:
            k = k + 1 
        
    return D
        
    return D
\end{python}

\tcblower

Voici le programme complété:

\begin{python}
def decomp(n):
    D = dict() # dictionnaire vide
    
    k = 2
    
    while n > 1:
        exposant = 0
        while n%k == 0:
            exposant = exposant + 1
            n = n/k
        if exposant != 0:
            D[k] = exposant
        k = k+1
        j = 2
        while k%j == 0:
            k = k + 1 
        
    return D
\end{python}

On a par exemple:

\begin{console}
>>> decompose(360)
{2: 3, 3: 2, 5: 1}
\end{console}

qui nous dit alors que $360=2^3 \times 3^2 \times 5^1$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
On rappelle que la factorielle de $n$ est le nombre:
\[
\fact{n}=2\times3\times4\times\cdots\times n.
\]
\begin{enumerate}
\item Combien y a-t-il de nombres pairs strictement compris entre $2^k$ et $2^{k+1}$, pour $k\in\N*$ ?
\item Par quelle puissance de 2 au maximum peut-on diviser $\fact{n}$ si $n=2^4$?
\item Imaginer un programme Python, composé de deux fonctions:
\begin{itemize}
\item une fonction \texttt{fact(n)} qui retourne $\fact{n}$;
\item une fonction \texttt{maxpow(n)} qui retourne le plus grand exposant de 2 dans la décomposition en produit de facteurs premiers de $\fact{(2^n)}$.
\end{itemize}
\end{enumerate}


\tcblower


\begin{enumerate}
\item Entre $2^k$ et $2^{k+1}$ (non compris), il y a $2^{k+1}-2^k = 2^k-1$ nombres. Le nombre avant $2^{k+1}$ étant nécessairement pair, on peut alors dire qu'il y a:
\[
\dfrac{2^k-2}{2}=2^{k-1}-1
\]
nombres pairs, pour $k\in\N*$.

\bigskip

\item $\fact{(2^4)}=2^1\times3\times2^2\times5\times6\times7\times2^3\times\cdots\times2^4$.

Dans cette décomposition, il y a d'une part toutes les puissances de 2, mais aussi les nombres pairs entre ces puissances, nombres qui peuvent s'écrire sous la forme $q \times2^p$, $p\geqslant1$.

\begin{itemize}
\item Entre $2^2$ et $2^3$, il y a 1 multiple de 2 : $6=2\times3$.
\item Entre $2^3$ et $2^4$, il y a 3 multiples de 2: $10=2\times5$, $12=2^2\times3$ et $14=2\times7$.
\end{itemize}
Finalement, l'exposant de 2 dans la décomposition de $\fact{(2^4)}$ le plus grand est:
\[
(1+2+3+4) + 1+1+2+1=15.
\]

\item Voici un programme possible:
\begin{python}
def fact(n):
    f = 1
    for i in range(1,n+1):
        f = f * i
        
    return f  
    

def maxpow(n):
    N = fact(2**n)
    p = 0
    while N%2 == 0:
        p = p+1
        N = N//2
        
    return p
\end{python}

Ces fonctions ont tout de même leur limite (surtout \texttt{fact(n)}. En effet, à partir de\linebreak $n=15$, cette dernière fonction est longue pour renvoyer le résultat.
On peut tout de même contrôler que $2^{\numprint{65535}}$ est la plus grande puissance de 2 qui divise $\fact{(2^{16})}$.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Soient $x=\numprint{280280}$, $y=\numprint{347116}$ et $z=\numprint{740278}$.
\begin{enumerate}
\item Décomposer en produit de facteurs premiers $x$, $y$ et $z$.
\item En déduire $\pgcd{x}{y}$, $\pgcd{y}{z}$ et $\pgcd{x}{z}$.
\item Peut-on calculer un PGCD de $x$, $y$ et $z$ ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item On a:
\begin{itemize}
\item $x=\numprint{280280}=2^3\times5^1\times7^2\times11^1\times13^1$.
\item $y=\numprint{347116}=2^2\times7^3\times11^1\times23^1$.
\item $z=\numprint{740278}=2^1\times7^1\times11^2\times19^1\times23^1$.
\end{itemize}

\bigskip


\item On peut alors déduire que:
\begin{itemize}
\item $d_1=\pgcd{x}{y} = 2^2\times7^2\times11^1$.
\item $d_2=\pgcd{y}{z} = 2^1\times7^1\times11^1\times23^1$.
\item $d_3=\pgcd{x}{z} = 2^1\times7^1\times11^1$.
\end{itemize}

\bigskip

\item Le PGCD de $x$, $y$ et $z$ peut se calculer à partir de la décomposition en produit de facteurs premiers des nombres.

Ce la donne : $\text{pgcd}(\coordEsp{x}{y}{y})=2^1\times7^1\times11^1$.
\end{enumerate}
\end{exocor}

\subsection*{Petit théorème de Fermat}

\begin{exocor}{}
Soit $p$ un nombre premier différent de 3.

Montrer que pour tout entier naturel $n$, $3^{n+p}-3^{n+1}$ est divisible par $p$.

\tcblower

Pour tout entier naturel $n$, 
\begin{align*}
3^{n+p}-3^{n+1} \text{ est divisible par }p & \iff 
3^{n+p}-3^{n+1}\equiv0\mod p\\
& \iff 3^{n+p}\equiv3^{n+1}\mod p\\
& \iff 3^n\times 3^p  \equiv 3^n\times 3\mod p\\
& \iff 3^p\equiv3\mod p\qquad\text{car }p\neq3.
\end{align*}

Cette dernière congruence est vraie d'après le petit théorème de Fermat (car $p$ est premier et $p$ ne divise pas 3). 


Par conséquent, pour tout entier naturel $n$, $3^{n+p}-3^{n+1}$ est divisible par $p$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{démonstration du petit théorème de Fermat}
Soient $p$ un nombre premier, $n$ un entier naturel et $a$ non divisible par $p$.

\begin{enumerate}
\item Montrer par l'absurde que le reste des divisions euclidiennes par $p$ de $a$, $2a$, ... , $(p-1)a$ sont tous distincts.

\item En déduire que $a^{p-1}\equiv1\mod p$.

\item Montrer que la réciproque est fausse en utilisant le nombre $p=3\times11\times17=561$.
\end{enumerate}

\tcblower

\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}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que pour tout entier naturel $a$, $a^{13}-a$ est divisible par 26.

\tcblower

\begin{itemize}
\item Si $a$ est divisible par 13 alors $a^{13}-a=a\big(a^{12}-1\big)$ aussi.

De plus, $a$ et $a^{13}$ ont la même parité. En effet, le produit de deux nombres impairs est impair et celui de deux nombres pairs est pair.

Ainsi, $a^{13}-a$ est divisible par 2 (la différence de deux nombres de même parité est paire).

2 et 13 étant premiers entre eux, on en conclut que $a^{13}-a$ est divisible par $2\times13$, donc par 26.

\bigskip

\item Si $a$ n'est pas divisible par 13, d'après le petit théorème de Fermat,
\[
a^{13}\equiv a\mod p
\]
donc 
\[
a^{13}-a\equiv0\mod p,
\]
ce qui signifie que $a^{13}-a$ est divisible par 13.

De plus, il est divisible par 2 (pour les raison évoquées précédemment), donc divisible par 26.
\end{itemize}


\end{exocor}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
Montrer que pour tout entier naturel $n$, $3^{6n}-1$ est divisible par 7.

\tcblower

D'après le petit théorème de Fermat,
\[
3^6\equiv3^{7-1}\equiv 1\mod7.
\]
Ainsi, pour tout entier naturel $n$,
\[
3^{6n}\equiv\big(3^6\big)^n \equiv1^n\equiv 1\mod 7
\]
et donc:
\[
3^{6n}-1\equiv0\mod7.
\]
$3^{6n}-1$ est donc bien divisible par 7, quel que soit l'entier naturel $n$.
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{exocor}{théorème des restes chinois}
\label{last-thmFermat}
Soient $m$ et $n$ deux entiers naturels premiers entre eux.

\begin{enumerate}
\item  Démontrer que si $\coord{a}{b}\in\Z\times\Z$, alors le système $\begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}$ admet une unique solution $x$ modulo $mn$.

\item Application : dans une boutique qui vend des macarons, il y a des boîtes de rangement par 5 et par 9.

Une société souhaite acheter un certain nombre de macarons. La préparatrice constate que si elle ne prend que des rangements par 5, il lui reste à la fin 3 macarons. Si elle ne prend que des rangements par 9, il lui reste au final 2 macarons.

Combien la société a-t-il commandé de macarons sachant que ce nombre est compris entre 100 et 140 ?
\end{enumerate}

\tcblower

\begin{enumerate}
\item Nous allons démontrer l'équivalence entre le système et l'unicité de la solution en démontrant la double implication.

\begin{itemize}
\item Montrons que $\begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}\quad \Rightarrow \quad x\equiv x_0 \mod(mn)$.

$m$ et $n$ sont premiers entre eux donc d'après le théorème de Bézout, il existe un couple $\coord{u}{v}$ d'entiers relatifs tels que $um+vn=1$.

Le système $\begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}$ peut s'écrire :
\[
\begin{cases}
x=mk+a\\
x=nk'+b
\end{cases}\quad,\quad \coord{k}{k'}\in\Z\times\Z
\]
soit, en multipliant la 1\iere{} ligne par $nv$ et la 2\ieme{} par $mu$ :
\[
\begin{cases}
(nv)x=(nv)mk+(nv)a\\
(mu)x=(mu)nk'+(mu)b
\end{cases}\quad,\quad \coord{k}{k'}\in\Z\times\Z.
\]
En ajoutant les deux lignes, on obtient :
\[
(nv+mu)x=mn(vk+uk')+nva+mub
\]
soit :
\[
x=mn(vk+uk')+nva+mub.
\]
Ainsi, si $x$ est solution du système $\begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}$, 

alors $x\equiv nva+mub\mod(mn)$.

\item Montrons maintenant que $x\equiv nva+mub\mod(mn)\quad\Rightarrow \quad \begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}$.

Puisque $m$ et $n$ sont premiers entre eux, il existe un couple $\coord{u}{v}$ d'entiers relatifs tels que $um+vn=1$, soit $nv=1-mu$.

Ainsi, 
\begin{align*}
x\equiv nva+mub\mod(mn) & \Rightarrow x\equiv nva\mod m\\
& \Rightarrow x\equiv(1-mu)a \mod m\\
& \Rightarrow x\equiv a\mod m.
\end{align*}
De même,
\[ 
x\equiv b\mod n.
\]
$x$ est donc solution du système $\begin{cases}
x\equiv a\mod m\\
x\equiv b\mod n
\end{cases}$.
\end{itemize}

\item Notons $x$ le nombre de macarons commandés par la société. D'après l'énoncé, on a :
\[
\begin{cases}
x\equiv3\mod5\\
x\equiv2\mod9
\end{cases}
\]
5 et 9 étant premiers entre eux, on utilise le théorème des restes chinois : il existe un couple \coord{u}{v} d'entiers relatifs tels que $5u+9v=1$. 

On trouve facilement $\coord{u}{v}=\coord{2}{-1}$.

Dans ce cas, $x\equiv 9\times(-1)\times3 + 5\times5\times2\mod(5\times9)$, soit $x\equiv23\mod45$.

Le nombre compris entre 100 et 140 correspondant est $x=23+2\times45=113$.

\medskip

\uline{La société a donc commandé 113 macarons.}
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{}
On considère la fonction Python suivante:
\begin{python}
def test(n):
    if 2**(n-1)%n == 1:
        return True
    else:
        return False
\end{python}

Expliquer en quoi cette fonction peut nous aider à savoir si un nombre $n$ est premier ou pas.

Proposer une légère modification afin qu'elle remplisse son rôle sans ambiguïté.

\tcblower

Dans cette fonction, \og \texttt{2**(n-1)\%n} \fg{} représente le reste de la division euclidienne de $2^{n-1}$ par $n$. Autrement dit, cela représente la congruence de $2^{n-1}$ modulo $n$.

\medskip

D'après le petit théorème de Fermat, si $n$ est premier (donc ne divise par 2) alors $2^{n-1}\equiv1\mod p$.

Ainsi, si le reste calculé est différent de 1, alors $n$ n'est pas premier. Par conséquent, si \texttt{test(n)} renvoie \og False \fg, $n$ n'est assurément pas premier.

Mais attention, si la fonction renvoie \og True \fg, cela ne signifie pas nécessairement que $n$ est premier.

En effet, \texttt{test(341)} renvoie \og True \fg{} et pourtant, $341=11\times31$.

\medskip

%Ce test n'est donc pas fait pour prouver qu'un nombre est premier mais au contraire pour prouver qu'un nombre n'est pas premier. 
On peut alors modifier cette fonction afin qu'elle soit moins ambigüe:
\begin{python}
def test(n):
    if 2**(n-1)%n != 1:
        return f"{n} n'est assurément pas un nombre premier."
    else:
        return f"{n} est potentiellement premier, mais il faut effectuer d'autres tests pour s'en assurer."
\end{python}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{nombres de Carmichael}
Un entier naturel $n$ est appelé \textit{nombre de Carmichael} si pour tout entier $a$, $a^n\equiv a\mod n$.
\begin{enumerate}
\item Montrer que si $n=p_1p_2\cdots p_k$, où les $p_k$ sont des nombres premiers distincts, et si $p_i-1$ divise $n-1$ pour $1\leqslant i\leqslant k$, alors $n$ est un nombre de Carmichael.
\item Montrer que 561 est un nombre de Carmichael.
\end{enumerate}

\tcblower

\begin{enumerate}
\item Soit $a$ un entier premier avec $n=p_1p_2\cdots p_k$.

Pour tout $1\leqslant i\leqslant k$, $p_i$ ne divise par $a$ donc d'après le petit théorème de Fermat,
\[
a^{p_i-1} \equiv 1 \mod p_i.
\]
Or, par hypothèse, $p_i-1$ divise $n-1$ donc:
\[
a^{n-1} \equiv a^{q_i(p_i-1)} \equiv \big(a^{p_i-1}\big)^{q_i}\equiv 1^{q_i}\equiv 1\mod p_i.
\]
Ainsi, $p_i$ divise $a^{n-1}-1$.

Les $p_i$ étant premiers entre eux, $n=p_1p_2\cdots p_k$ divise $a^{n-1}-1$ et donc\linebreak $a^{n-1}\equiv1\mod n$.

$n$ est donc un nombre de Carmichael.

\item $561=3\times11\times17$.

\begin{itemize}
\item $3-1$ divise $561-1=560$;
\item $11-1=10$ divise $561-1=560$;
\item $17-1=16$ divise 560.
\end{itemize}

Ainsi, 561 est bien un nombre de Carmichael.
\end{enumerate}
\end{exocor}

\subsection*{Chiffrement}

\begin{exocor}{chiffrement affine}
Le chiffrement affine consiste à attribuer à chaque lettre de l'alphabet un nombre (sa position) en convenant d'avoir 0 pour A, 1 pour B, etc.

On choisit deux nombres $a$ et $b$. On note $x$ le rang d'une lettre et $r(x)$ tel que \mbox{$ax+b\equiv r(x) \mod 26$}. La lettre correspondant à $r(x)$ est la lettre codée.

\begin{enumerate}
\item Dans cette question, on prend $a=17$ et $b=2$.

Montrer que la lettre \og Q \fg{} est chiffrée en la lettre \og N \fg.

\item Montrer que le déchiffrement n'est pas possible si $a$ et 26 ne sont pas premiers entre eux. 

\item En utilisant le théorème de Gauss, justifier que si $\pgcd{a}{26}=1$ alors le déchiffrement est possible. 

\item En prenant $a=17$ et $b=2$, retrouver la lettre qui, une fois chiffrée, donne \og Q \fg. 

\item Proposer une fonction Python \texttt{chiffrement\_affine(a,b,lettre)} qui prend en argument $a$ et $b$, ainsi que la lettre que l'on souhaite chiffrer.

\item Proposer une fonction Python \texttt{dechiffrement\_affine(a,b,lettre)} qui permet de déchiffrer une lettre.
\end{enumerate}

\tcblower

\begin{enumerate}
\item La lettre \og Q \fg{} occupe la place 16; donc $x=16$. On calcule alors:
\[
ax+b \equiv 17\times16+2\equiv14\mod 26.
\]
14 est la position de la lettre \og O \fg.

\underline{Ainsi, \og Q \fg{} est chiffrée en \og O \fg.}

\item Raisonnons par l'absurde.

Supposons donc que $\pgcd{a}{26}\neq 1$. Notons $x$ et $x'$ les rangs de deux lettres différentes. 
\[
\begin{cases}
ax+b\equiv r(x)\mod26\\
ax'+b\equiv r(x')\mod26
\end{cases}
\iff
\begin{cases}
ax+b &= 26q+r(x),\ q\in\N*\\
ax'+b &= 26q'+r(x'),\ q'\in\N*
\end{cases}
\]
Alors,
\begin{align*}
r(x)-r(x') & = 26(q'-q)+a(x-x')\\
& = 26(q'-q)+a\dfrac{26}{\pgcd{a}{26}}\quad\text{en prenant }x\text{ et }x' \text{ tels que }x-x'=\dfrac{26}{\pgcd{a}{26}}\\
& = 26\left(q'-q+\dfrac{a}{\pgcd{a}{26}}\right)\\
& \equiv 0\mod 26.
\end{align*}

Il est donc possible de trouver deux $x$ et $x'$ différents tels que $r(x)\equiv r(x')\mod 26$.

Dans ce cas, le décryptage est impossible.

\uline{Par conséquent, si $\pgcd{a}{26}\neq1$, une lettre chiffrée peut corresponde à plusieurs lettres.}

\item Supposons que $\pgcd{a}{26}=1$. Soient deux nombres $x$ et $x'$ tels que $r(x)=r(x')$. 
\[
\begin{cases}
ax+b\equiv r(x)\mod26\\
ax'+b\equiv r(x)\mod26
\end{cases}
\iff
\begin{cases}
ax+b &= 26q+r(x),\ q\in\N*\\
ax'+b &= 26q'+r(x),\ q'\in\N*
\end{cases}
\]
Alors,
\[ a(x-x')=26(q-q').\]
Or, $\pgcd{a}{26}=1$, donc d'après le théorème de Gauss, 26 divise $(x-x')$. 

De plus, $0\leqslant x \leqslant 25$ et $0\leqslant x' \leqslant 25$.

Par conséquent, $-25 \leqslant x-x' \leqslant 25$.

On en déduit alors que $x-x'=0$ (seul 0 est divisible par 26 sur $\llbracket -25;25\rrbracket$).

\uline{Dans ce cas, on est assuré que le décryptage est possible (à une lettre codée ne correspond qu'une solution décodée).}

\item On part du principe que $y\equiv ax+b\mod 26$ est le rang de la lettre codée. Alors, en convenant de noter $a'$ l'inverse de $a$ modulo 26, on a :
\begin{align*}
ax+b\equiv y\mod 26 & \Leftrightarrow aa'x+ba'\equiv a'y\mod 26\\
& \Leftrightarrow x\equiv a'(y-b)\mod 26.
\end{align*}

Pour décoder la lettre \og Q \fg, dont le rang est $y=16$, on fait :
\begin{align*}
x & \equiv 23(16-2)\mod 26\\
& \equiv 322 \mod 26\\
& \equiv 12\times26+10\mod 26\\
&\equiv 10 \mod 26.
\end{align*}

Et 10 est le rang de la lettre \og K \fg.
\newpage
\item Voici une fonction possible.
\begin{python}
from string import ascii_uppercase

def chiffrement_affine(a,b,lettre):
    lettre = lettre.upper() # on convertir la lettre en majuscule... au cas où...
    x = ascii_uppercase.index(lettre)
    r = (a * x + b) % 26
    
    return ascii_uppercase[r]
\end{python}

J'ai ici fait appel à \texttt{ascii\_uppercase} (du module \texttt{string}) qui désigne la chaîne de caractères \og ABC...XYZ \fg. 

\item Voici une fonction possible:
\begin{python}
def dechiffrement_affine(a,b,lettre):
    lettre = lettre.upper()
    x = ascii_uppercase.index(lettre)
    
    # calcule l'inverse de a modulo 26
    
    i = 0
    while (a*i%26 != 1):
        i = i + 1
    
    # calcule le rang de la lettre initiale
    
    y = ( i * (x-b) ) % 26
    
    return ascii_uppercase[y]
\end{python}
\end{enumerate}
\vspace*{5cm}~
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{chiffrement de Vigenère}
Le chiffrement de Vigenère nécessite un \og mot-clé \fg.

Comme dans le chiffrement affine, chaque lettre est affectée de son rang (0 pour \og A \fg, 1 pour \og B \fg, etc.). Nous allons noter $\rg(...)$ le rang de la lettre entre parenthèses. Donc $\rg(A)=0$.

Notons le message à chiffrer : $M_0M_1M_2\cdots M_n$ comportant $n+1$ lettres.

Notons le mot-clé: $C_0C_1\cdots C_p$ comportant $p+1$ lettres.

Si $p<n$ alors on répète $k$ fois le mot-clé jusqu'à ce que sa longueur soit au moins égale à $n+1$, et on le tronque de sorte que sa longueur soit exactement égale à $n+1$.

Ainsi, le mot-clé devient : $C_0C_1\cdots C_pC_0\cdots C_pC_0\cdots C_j$, tel que $n+1=k(p+1)+j+1$. 

\medskip

Le message chiffré sera alors de la forme $M'_0M'_1\cdots M'_n$ tel que:
\[
\forall i\in\llbracket 0;n\rrbracket,\ \rg(M'_i)\equiv \rg(M_i) + \rg(C_i)\mod 26.
\]

Prenons le message \og MATHEMATIQUES \fg{} et le mot-clé \og SYMPA \fg. Cela donne:
\begin{center}
\fontsize{8}{10}\selectfont
\begin{tabular}{|*{13}{Sc|}}
\hline\rowcolor{blue!10}
M & A & T & H & E & M & A & T & I & Q & U & E & S\\
\hline
12 & 0 & 19 & 7 & 4 & 12 & 0 & 19 & 8 & 16 & 20 & 4 & 18\\
\hline\rowcolor{green!10}
S & Y & M & P & A & S & Y & M & P & A & S & Y & M\\
\hline
18 & 24 & 12 & 15 & 0 & 18 & 24 & 12 & 15 & 0 & 18 & 24 & 12\\
\hline
$12+18$ & $0+24$ & $19+12$ & $7+15$ & $4+0$ & $12+18$ & $0+24$ & $19+12$ & $8+15$ & $16+0$ & $20+18$ & $4+24$ & $18+12$\\
$=30$ & $=24$ & $=31$ & $=22$ & $=4$ & $=30$ & $=24$ & $=31$ & $=23$ & $=16$ & $=38$ & $=28$ & $=30$\\
$\equiv 4$ & $\equiv 24$ & $\equiv 5$ & $\equiv 22$ & $\equiv 4$ & $\equiv 4$ & $\equiv 24$ & $\equiv 5$ & $\equiv 23$ & $\equiv 16$ & $\equiv 12$ & $\equiv 2$ & $\equiv 4$\\
\hline\rowcolor{yellow!10}
E & Y & F & W & E & E & Y & F & X & Q & M & C & E\\
\hline
$4-18$ & $24-24$ & $5-12$ & $22-15$ & $4-0$ & $4-18$ & $24-24$ & $5-12$ & $23-15$ & $16-0$ & $12-18$ & $2-24$ & $4-12$\\
$\equiv 12$ & $\equiv 0$ & $\equiv 19$ & $\equiv 7$ & $\equiv 4$ & $\equiv 12$ & $\equiv 0$ & $\equiv 19$ & $\equiv 8$ & $\equiv 16$ & $\equiv 20$ & $\equiv 4$ & $\equiv 18$\\
\hline\rowcolor{blue!10}
M & A & T & H & E & M & A & T & I & Q & U & E & S\\
\hline
\end{tabular}
\end{center}

\begin{minipage}{0.33\textwidth}
\textbf{Légende :}
\begin{quote}
\begin{tabular}{|Sl|}
\hline\rowcolor{blue!10}
Message décodé\\
\hline\rowcolor{green!10}
Clé\\
\hline\rowcolor{yellow!10}
Message codé\\
\hline
\end{tabular}
\end{quote}
\end{minipage}
\begin{minipage}{0.66\textwidth}
Toutes les congruences sont modulo 26.
\end{minipage}

Proposer une fonction Python \texttt{chiffrement\_vigenere(message,key} qui renvoie le message passé en argument avec le mot-clé passé en second argument.

\tcblower

Voici une proposition:
\begin{python}
from string import ascii_uppercase

def chiffrement_vigenere(message,key):
    message = message.upper()
    key = key.upper()
    chiffrement = ''   
    if len(key) > len(message):
        key = key[:len(message)]
    elif len(key) < len(message):
        while len(key) < len(message):
            key += key
        key = key[:len(message)]       
    for p in range( len(message) ):
        x = ascii_uppercase.index(message[p])
        y = ascii_uppercase.index(key[p])
        r = (x+y)%26
        chiffrement += ascii_uppercase[r]     
    return chiffrement
\end{python}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{code barre}
Les codes EAN 13 sont des codes constitué de 13 chiffres, le dernier étant appelé la \textit{clé} du code, et permet de vérifier l'exactitude des 12 premiers. 

Si $a_1a_2\cdots a_{12}a_{13}$ désigne l'un de ces codes, $a_{13}$ est déterminé de sorte que:
\[
3\sum_{k=1}^6 a_{2k} + \sum_{k=0}^6 a_{2k+1} \equiv 0 \mod 10.
\]

\begin{enumerate}
\item Calculer la clé du code commençant par \og 301776063299 \fg.
\item Proposer une fonction Python \texttt{ean13\_key(code)} renvoyant la clé de contrôle du code mis en argument.

\textit{On pourra convertir le code en chaîne de caractère avec la fonction \texttt{str(code)}, et parcourir cette chaîne de caractères en convertissant chaque caractères en un entier avec la fonction \texttt{int(caractère)}.} 

\item Montrer que si un seul chiffre est erroné dans un code EAN13 alors l'erreur est détectée.

\item Supposons que deux chiffres consécutifs $a_{2k-1}$ et $a_{2k}$ soient permutés (erreur fréquente).

Montrer alors que, pour que l'erreur ne soit pas détectée, il faut et il suffit que\linebreak $a_{2i-1} \equiv a_{2i} \mod 5$.

En déduire que ce type d'erreur n'est pas détectée une fois sur dix.
\end{enumerate}

\tcblower

\begin{enumerate}
\item On cherche $a_{13}$ de sorte que:
\[
3(0+7+6+6+2+9) + (3+1+7+0+3+9+a_{13})\equiv 0\mod 10.
\]
On a alors: $113+a_{13}\equiv0\mod10$, et donc: $a_{13}\equiv7\mod10$.

\underline{La clé de ce code est donc égale à 7.}

\item Voici une proposition de code:
\begin{python}
def ean13_key(code):
    code = str(code)
    if len( code ) != 12:
        return False
    else:
        s = 0
        for k in range(len(code)):
            if k%2 != 0:
                s = s + 3 * int( code[k] )
            else:
                s = s + int( code[k] )
                
        return 10 - s%10
\end{python}

Il faut ici faire attention au fait que le premier chiffre (à gauche) n'est as \texttt{a[1]} mais \texttt{a[0]}. Il y a donc un décalage: ici, ce sont les chiffres de rang impairs que l'on multiplie par 3.

\item Supposons qu'un seul chiffre est erroné dans un code $a_1a_2\cdots a_{12}a_{13}$.

La question est: est-il possible que ce code produise la même clé de contrôle ?

Supposons que ce soit le cas. 

\begin{itemize}
\item Supposons que le chiffre erroné soit $a'_{11}\neq a_{11}$ (ou n'importe quel chiffre de rang impair).
\begin{align*}
3\sum_{k=1}^6 a_{2k} + \sum_{k=0}^6 a_{2k+1} \equiv 0 \mod 10\\
3\sum_{k=1}^6 a_{2k} + \sum_{k=0}^4 a_{2k+1} + a'_{11} + a_{13} \equiv 0 \mod 10.
\end{align*}
En soustrayant les deux congruences, on a:
\[
a_{11}-a'_{11}\equiv0 \mod 10\qquad\text{soit}\qquad a'_{11}\equiv a_{11} \mod10.
\]
Or, $0 \leqslant a_k \leqslant 9$ et $0 \leqslant a'_k \leqslant 9$ donc cela implique que $a_{11}=a'_{11}$, ce qui est impossible par hypothèse.

\medskip


\item Supposons que le chiffre erroné soit $a'_2\neq a_2$.
\begin{align*}
3a_2 + 3\sum_{k=2}^6 a_{2k} + \sum_{k=0}^6 a_{2k+1} \equiv 0 \mod 10\\[10pt]
3a'_2 + 3\sum_{k=2}^6 a_{2k} + \sum_{k=0}^6 a_{2k+1} \equiv 0 \mod 10.
\end{align*}
En soustrayant, on obtient:
\[
3(a_2 - a'_2) \equiv 0 \mod 10.
\]
3 et 10 sont premiers entre eux donc d'après le théorème de Gauss, 
\[
a_2 - a'_2 \equiv 0 \mod 10\qquad\text{et donc}\qquad a_2 \equiv a'_2 \mod 10.
\]
Donc $a_2 = a'_2$, ce qui est contradictoire avec notre hypothèse.
\end{itemize}
\underline{Ainsi, s'il n'y a qu'un seul chiffre erroné, l'erreur est détectée.}

\item Supposons que deux chiffres consécutifs $a_{2i-1}$ et $a_{2i}$ soient permutés (erreur fréquente).

On note:
\[
S=3\sum_{k=2}^6 a_{2k} + \sum_{k=0}^6 a_{2k+1} = \cdots + a_{2i-1} + 3a_{2i} + \cdots
\]
et
\[
S' = \cdots + a_{2i} + 3a_{2i-1} + \cdots
\] 
\begin{align*}
\text{L'erreur n'est pas détectée} & \iff \begin{cases}
S \equiv 0 \mod 10\\
S' \equiv 0 \mod 10
\end{cases}\\[10pt]
& \iff S-S' = a_{2i-1} -a_{2i}  + 3\big(a_{2i} - a_{2i-1}\big) \equiv 0 \mod 10\\[10pt]
 & \iff 2a_{2i-1} \equiv 2a_{2i}  \mod10\\[10pt]
 & \iff a_{2i-1} \equiv a_{2i} \mod 5.
\end{align*}
(2 et 10 ne sont pas premiers entre eux donc quand on divise par 2, on divise aussi le modulo par 2).

\medskip

Ainsi, étant donné par exemple $a_{2i}$ la probabilité pour que $a_{2i} \equiv a_{2i-1} \mod 5$ tout en ayant $a_{2i} \neq a_{2i-1}$ est $\dfrac{1}{10}$. 

Il y a en effet deux chiffres congrus à $a_{2i}$ modulo 5: : $a_{2i}$ et $a_{2i}\pm5$, mais $a_{2i-1}$ doit être différent de $a_{2i}$ sans quoi, la permutation des deux chiffres ne change rien au code et donc, celui-ci n'est pas erroné.
\end{enumerate}
\end{exocor}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exocor}{chiffrement RSA}
Soient $p$ et $q$ deux nombres premiers distincts.

On pose $N=pq$ et $n=(p-1)(q-1)$.

\bigskip

\partie{A}

\begin{enumerate}
\item À l'aide du petit théorème de Fermat, montrer que pour tout entier naturel $a$ premier avec $p$ et $q$,
\[
a^{(p-1)(q-1)} \equiv 1 \mod p \qquad\text{et}\qquad  a^{(p-1)(q-1)} \equiv 1 \mod q.
\]
\item En déduire que $a^{(p-1)(q-1)} \equiv 1 \mod N$.
\item Démontrer que pour tout entier naturel $a$, si $k$ est un entier qui vérifie $k\equiv1\mod n$, alors $a^k \equiv a \mod N$.
\end{enumerate}

\bigskip

\partie{B}

Soit $c$ un entier premier avec $n$ et strictement inférieur à $n$.

\begin{enumerate}
\item Justifier que l'équation $(E) : cx-ny=1$ admet des solutions.
\item Soit \coord{x_0}{y_0} une solution de $(E)$.

Prouver que \coord{x}{y} est solution de $(E)$ si et seulement si $x=x_0+kn$ et $y=y_0+kc$, où $k\in\Z$.

\item En déduire qu'il existe un unique entier naturel $d<n$ tel que $cd\equiv1 \mod n$.
\end{enumerate}

\bigskip

\partie {C}

Déduire des parties A et B que, quels que soient les entiers naturels $a$ et $b$, on a l'implication suivante:
\[
b\equiv a^c\mod N \Rightarrow b^d \equiv a \mod N.
\]
\begin{rem}[principe du chiffrement RSA]
Un message $a$ doit être envoyé par Alice à Bob, avec une clé publique $c$.

Alice calcule $b$ tel que $b\equiv a^c \mod N$. $b$ est alors transmis à Bob.

Bob calcule ensuite $b^d\equiv a\mod N$, où $d$ est la clé privée que seul Bob détient.
\end{rem}

\tcblower

\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*}
\end{exocor}

\corriges
