\documentclass[12pt]{amsart}
\usepackage{kbexo}
%\soltrue
\begin{document}
\course{MHT633 -- Arithmétique et Cryptologie}
\num{1}
\exotitle[Arithmétique]

\exocor
Soit $a$ un nombre rationnel tel que $18a$ et $25a$ sont des nombres entiers.
Montrez que $a$ est aussi entier.
\cor
Tout nombre rationnel est le quotient de deux nombres entiers premiers
entre eux. Soit donc $a=p/q$ avec $(p,q)=1$.
Si $18a$ est entier, alors $q$ divise $18p$. On rappelle:
\begin{lemme*}[Gauss]
$a,b,c$ étant des nombres entiers, si $a$ divise $bc$ et si $a$ est
  premier avec $b$ alors $a$ divise $c$. 
\end{lemme*}
Comme $(p,q)=1$ on peut conclure que $q$ divise $18$. De même $q$
divise $25$. Finalement, si $q$ divise $18$ et $25$ alors $q$ divise
leur pgcd qui vaut $1$, donc $q=1$, ce qui prouve que $a$ est entier.
\endexo

\exocor
Montrez qu'il existe une infinité de nombres premiers de la forme $4n+3$.
\cor
Rappelons la démonstration du fait qu'il y a une infinité de
nombres premiers: si $p_1, \dots, p_n$ sont premiers  alors
$N=p_1\dots p_n+1$ n'est divisible par aucun des $p_i$; comme c'est un entier
au moins égal à $2$, il possède un diviseur premier $p\not\in
\set{p_1,\dots,p_n}$. 

Supposons maintenant qu'en outre $p_i\equiv -1\mod 4$ pour tout
$i=1,\dots,n$; ceci implique qu'ils sont impairs.
L'idée est de construire un N qui soit premier aux $p_i$ et qui
vérifie également $N\equiv -1\mod 4$. En effet, $N$ possède alors
au moins un diviseur premier égal à $-1\pmod{4}$: sinon tous ses
diviseurs premiers seraient égaux à $1\pmod{4}$ et donc leur produit
aussi.

On a $(p_1\dots p_n)^2\equiv 1 \pmod 4$ donc on peut prendre
$$ N= (p_1\dots p_n)^2 + 2. $$
Remarquons qu'on utilise ici fondamentalement le fait que les 
congruences modulo un entier se multiplient!
\endexo

\exocor Pour quels entiers $n$ le nombre $n^2-1$ est-il premier ?
\cor
Comme $n^2-1=(n-1)(n+1)$, il est nécessaire que $n-1=\pm 1$ ou $n+1=\pm 1$
ce qui conduit à examiner les cas $n=0,2,-2$, pour lesquels $n^2-1$ vaut
respectivement $1,3,3$. Rappelons que le nombre $1$ n'est pas premier.
\endexo

\exo Trouvez tous les entiers $p$ et $q$ tels que $4p+7q=pq$.
\cor
{ Si $4p+7q=pq$ alors $p$ divise $7q$ et $q$ divise $4p$. Ca nous
  arrangerait que $p$ et $q$ soient premiers entre eux pour conclure
  que $p$ divise $4$ et $q$ divise $7$ par le lemme de Gauss. On se
  ramène à ce cas en posant $(p,q)=d$ et $p=dp'$, $q=dq'$ avec
  $(p',q')=1$.
La condition $4p+7q=pq$ devient $4p'+7q'=p'q'd$ et le même
raisonnement montre que $p'$ divise $4$ et $q'$ divise $7$. Il reste
à examiner tous les cas. }
\endexo

\exocor Soit $a$ et $b$ des entiers distincts.
\Q Montrez que $a-b$ divise $a^2-b^2$ et déterminez le quotient.
\Q Montrez que $a-b$ divise $a^3-b^3$ et déterminez le quotient.
\Q Montrez que $a-b$ divise $a^n-b^n$ pour tout $n$
\Q Montrez que $a+b$ divise $a^{2n+1}+b^{2n+1}$ pour tout $n$.
\Q Trouvez la factorisation en nombres premiers de $5^{10}-2^{10}$.

\cor
\Q $a^2-b^2=(a-b)(a+b)$ \label{a}
\Q $a^3-b^3=(a-b)(a^2+ab+b^2)$ \label{b}
\Q $a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\dots+b^{n-1})$ \label{c}
\Q $a^{2n+1}+b^{2n+1}=(a+b)(a^{2n}-a^{2n-1}b+\dots-a b^{2n-1}+b^{2n})$.
On a simplement remplacé $n$ par $2n+1$ et $b$ par $-b$ dans la formule
précédence.
\Q On applique successivement \eqref{a}, \eqref{b}, \eqref{c}:
\begin{align*}
5^{10}-2^{10}&=(5^5-2^5)(5^5+2^5)\\
&= (5-2)(5^4+2\cdot 5^3+2^2\cdot 5^2+2^3\cdot 5+2^4)\\
&\quad\times
(5+2)(5^4-2\cdot 5^3+2^2\cdot 5^2-2^3\cdot 5+2^4)\\
&=3\cdot 1031\cdot 7\cdot 451.
\end{align*}
On vérifie directement que 3, 7 et 1031 sont premiers et que $451 = 11 \cdot
41$.
\endexo

\exocor[Nombres de Fermat]
\Q Vérifiez que les nombres $3=2+1$, $5=2^2+1$, $17=2^4+1$, $257=2^8+1$,
$65537=2^{16}+1$ sont premiers.

\Q En déduire la factorisation de $2^{32}-1$.

\Q Montrez que, si $N=2^k + 1$ est premier, alors $k$ est nécessairement une
  puissance de $2$. 

\Q Fermat conjecturait que les nombres de la forme $2^{2^n}+1$ sont premiers.
Cela est vrai pour $n=0,1,2,3,4$ mais n'est pas vrai pour $n=5$. Montrez, à
l'aide des observations suivantes, que $641$ divise $2^{2^5}+1$:
\qq $641=2^9+2^7+1$ donc $2^7\cdot 5\equiv -1\pmod{641}$,
\qq $2^4 \equiv -5^4\pmod{641}$.

\cor

\Q Vous verrez plus tard des critères d'irréductibilité 
plus efficaces que de vérifier qu'aucun nombre premier plus petit
que $\sqrt{N}$ ne divise $N$.
\Q On factorise:
\begin{align*}
2^{32}-1 &= (2^{16}-1)(2^{16}+1)\\
&= (2^{8}-1)(2^8+1)(2^{16}+1)\\
&= (2^{4}-1)(2^4+1)(2^8+1)(2^{16}+1)\\
&= (2^{2}-1)(2^2+1)(2^4+1)(2^8+1)(2^{16}+1)\\
&= (2-1)(2+1)(2^2+1)(2^4+1)(2^8+1)(2^{16}+1)\\
&= 3\cdot 5\cdot 17\cdot 257\cdot 65537
\end{align*}
\Q Si $k=2^eb$ avec $b$ impair, alors l'identité 
$$y^b+1=(y+1)(y^{b-1}-y^{b-2}+\dots+1),$$
appliquée en $y = 2^{2^e}$, montre que $2^{2^e}+1$ divise $2^k+1$. Si $b\neq 1$
c'est un diviseur non trivial.
\Q Montrons les deux observations:
\qq $641=2^9+2^7+1$ donc $2^7\cdot 5= 2^7(2^2+1)=2^9+2^7=641-1
\equiv -1\pmod{641}$.
\qq En effet $5^4=625\equiv -16\pmod{641}$.

\noindent Comme $32=4\cdot 7+4$, on a dans $\ZM/641\ZM$:
\begin{align*}
2^{32} = (2^7)^4\cdot 2^4 
&= (2^7)^4 \cdot (-5^4)\\
&= -(2^7\cdot5)^4\\
&= -(-1)^4 = -1
\end{align*}
donc $641$ divise $2^{32}+1$.
\endexo


\exocor
Montrez qu'un entier est divisible par $4$ si et seulement si le nombre formé
par ses deux derniers chiffres dans son écriture décimale est divisible par~$4$.
\cor
Comme $10^k\equiv 0\pmod{4}$ pour $k\geq 2$, un nombre $N$ d'écriture 
décimale $\overline{a_n\dots a_1a_0} = 10^n a_n + \dots + a_0$ est congru à
$\overline{a_1a_0} = 10 a_1 + a_0 \pmod{4}$.

\endexo

\exocor
Trouvez le pgcd et une relation de Bezout pour les couples $(a,b)$ suivants:
$$ (34,21), \quad (136,51), \quad (481,325), \quad (8771, 3206) $$
puis répondez aux questions
\Q $a$ est-il inversible modulo $b$ ? Si oui quel est son inverse ?
\Q $b$ est-il inversible modulo $a$ ? Si oui quel est son inverse ?
\cor
L'algorithme d'Euclide appliqué à un couple de nombres entiers
$(a,b)\neq (0,0)$ calcule le pgcd de $a$ et $b$. On effectue les
divisions euclidiennes successives en posant $r_0=a$, $r_1=b$, puis en
effectuant les divisions euclidiennes suivantes:
\begin{align*}
r_0&=r_1q_1+r_2\\
r_1&=r_2q_2+r_3\\
 &\dots \\
r_{i-1}&=r_iq_i+r_{i+1}\\
&\dots\\
r_{t-1}&=r_tq_t+r_{t+1},\quad\text{avec $r_t\neq 0$, $r_{t+1} = 0$}.\\
\end{align*}
Le pgcd de $a$ et $b$ est alors $d = r_t$, le dernier reste non nul. Une
relation de Bezout est une équation de la forme $d=au+bv$ où $d=(a,b)$.
Rappelons que $a$  est inversible modulo $b$, c'est-à-dire $a\in
(\ZM/b\ZM)^*$ si et seulement si $(a,b)=1$. Une relation de Bezout $au+bv=1$
montre que $au\equiv 1\pmod{b}$ et donc $a^{-1}=u$ dans $(\ZM/b\ZM)^*$; de
même, $b^{-1} = v$ dans $(\ZM/ a\ZM)^*$.

Pour extraire une relation de Bezout, on peut «remonter» les équations
données par les divisions euclidiennes successives de l'algorithme d'Euclide,
mais il est plus efficace d'appliquer l'algorithme dit d'\emph{Euclide
étendu}: celui-ci calcule en même temps que la suite des $q_i$ et des $r_i$,
deux suites $u_i$ et $v_i$ vérifiant les relations de récurrence:
\begin{align*}
u_{i+1}&=u_{i-1}-q_i u_i\\
v_{i+1}&=v_{i-1}-q_i v_i
\end{align*}
et les conditions initiales:
$$
\begin{pmatrix}
u_0 & v_0\\
u_1&v_1\end{pmatrix}
=\begin{pmatrix}
1 & 0\\
0& 1\end{pmatrix}.
$$
Le dernier couple $(u_t,v_t)$ calculé donne une relation de Bezout
entre $a$ et $b$. L'intérêt de cet algorithme réside dans le
fait que son exécution ne nécessite pas de garder en mémoire tous
les $(q_i, r_i, u_i, v_i)$ mais seulement les deux précédents.

\misctitle{Exemple} $a=34$, $b=21$. 
$$
\begin{array}{|ccccc|l}
i&r_i & q_i & u_i & v_i &\\
\cline{1-5}
0 & 34 & & 1 & 0 \\
1 & 21 & 1 & 0 & 1\\
2 & 13 & 1 & 1 & -1 & L_2 \leftarrow L_0 - q_1L_1\\
3 & 8 & 1 & -1 & 2  & L_3 \leftarrow L_1 - q_2L_2\\
4 & 5 & 1 & 2 & -3  & L_4 \leftarrow L_2 - q_3L_3 \\
5 & 3 & 1 & -3 &5   & L_5 \leftarrow L_3 - q_4L_4 \\
6 &2& 1& 5& -8      & L_6 \leftarrow L_4 - q_5L_5\\
7 & 1& 2& -8& 13    & L_7 \leftarrow L_5 - q_6L_6 \\
8 & 0 &&&\\
\end{array}
$$
On trouve la relation de Bezout $(-8)\cdot 34+13\cdot 21=1$; dans
$\ZM/21\ZM$, on a $34^{-1}=-8$; dans $\ZM/34\ZM$, on a $21^{-1}=13$.

\misctitle{Preuve de l'algorithme d'Euclide étendu} on  exprime le
passage de $(r_{i-1},r_i)$ à $(r_i,r_{i+1})$ par la relation matricielle
$$
\begin{pmatrix}
r_i\\
r_{i+1}\end{pmatrix}
=\begin{pmatrix}
0 & 1\\
1& -q_i\end{pmatrix}
\begin{pmatrix}
r_{i-1}\\
r_{i}\end{pmatrix},
$$
ce qui conduit par itération à:
$$
\begin{pmatrix}
r_i\\
r_{i+1}\end{pmatrix}
=\begin{pmatrix}
0 & 1\\
1& -q_i\end{pmatrix}
\begin{pmatrix}
0 & 1\\
1& -q_{i-1}\end{pmatrix}
\dots
\begin{pmatrix}
0 & 1\\
1& -q_1\end{pmatrix}
\begin{pmatrix}
r_{0}\\
r_{1}\end{pmatrix}.
$$
En posant, pour $i\geq 1$,
$$
U_i
=\begin{pmatrix}
0 & 1\\
1& -q_i\end{pmatrix}
\begin{pmatrix}
0 & 1\\
1& -q_{i-1}\end{pmatrix}
\dots
\begin{pmatrix}
0 & 1\\
1& -q_1\end{pmatrix},
\quad\text{et} \quad
U_0
=\begin{pmatrix}
1 & 0\\
0& 1\end{pmatrix},
$$
on a 
$$
U_i
=\begin{pmatrix}
0 & 1\\
1& -q_i\end{pmatrix}
U_{i-1},\quad \text{pour tout $i\geq 1$}.
$$
En posant $U_i = \smallmat{u_i & v_i\\s_i &t_i}$, on en déduit les relations 
$$
\left\{
\begin{aligned}
u_i&=s_{i-1},\\
v_i&=t_{i-1},\\
s_i&=u_{i-1}-q_i u_i &= u_{i+1},\\
t_i&=v_{i-1}-q_i v_i &= v_{i+1}.
\end{aligned}
\right.
$$
À la dernière étape, on a
$$
\begin{pmatrix}
r_t = (a,b)\\
r_{r+1}=0\end{pmatrix}
= U_t
\begin{pmatrix}
a\\
b\end{pmatrix}
$$
dont la première ligne donne la relation de Bezout $(a,b)=u_t a+v_t b$.

\misctitle{Une dernière optimisation} puisque le calcul des $u_i$ ne fait pas
intervenir les $v_i$, ce n'est pas la peine de remplir la colonne des $v_i$
dans le tableau ci-dessus, on peut se contenter des $u_i$, puisque de $d =
(a,b)$, $u = u_t$, $a$, et $b$, on déduit $v = (d - au)/b$.

\exocor
Trouvez tous les entiers $x$ et $y$ tels que $32x+10y=6$. 
\cor
$32x+10y=6$ ssi $16x+5y=3$. Comme $(16,5)=1$ et que $16-3\cdot
  5=1$ on a $16^{-1}=1\mod 5$ et $5^{-1}=-3\mod 16$. On a
$16x=3\mod 5$ ssi $x=3\mod 5$ et $5y=3\mod 16$ ssi $y=-9\mod 16$.
En remplaçant $x=3+5x'$ et $y=-9+16y'$ on trouve que $16x+5y=3$ ssi
$x'=-y'$.
finalement les solutions $(x,y)$ sont tous les $(3+5q, -9-16q)$ avec
$q\in \ZM$.
\endexo

\exocor La date de naissance d'Alice est telle que le jour multiplié
  par $12$ ajouté au mois multiplié par $31$ fait $442$. Déterminez la.
\cor
 On doit donc résoudre $12J+31M=442$. Par l'algorithme d'Euclide étendu on trouve $13\cdot 12-5\cdot
  31=1$.
Comme dans l'exercice précédent on a $J=11\mod 31$ et $M=10\mod
12$. Comme $1\leq M\leq 12$ la seule solution est $M=10$ et donc $J=11$.
\endexo

\exocor
Calculez les inverses multiplicatifs des nombres suivants ou bien
montrez qu'ils ne sont pas inversibles:
\Q $3\in \ZM/37\ZM$
\Q $4\in \ZM/14\ZM$.
\cor
\Q $(3,37)=1$ donc $3\in (\ZM/37\ZM)^*$; une relation de Bezout
  $37-3\cdot 12=1$ montre que $3^{-1}=12\mod 37$.
\Q $(4,14)=2>1$ donc $4$ n'est pas inversible modulo $14$.
\endexo

\exocor
\Q Quels sont les inversibles de $\ZM/4\ZM$,\; $\ZM/6\ZM$,\; $\ZM/12\ZM$ ?
\Q Si $p$ est premier, quels sont les inversibles de $\ZM/p^2\ZM$ ?
\cor
On rappelle que $a$ est un inversible de l'anneau  $\ZM/n\ZM$
si et seulement si $(a,n)=1$. On a donc:
$(\ZM/4\ZM)^*=\{1,3\}$, $(\ZM/6\ZM)^*=\{1,3,5\}$, $(\ZM/12\ZM)^*=\{1,5,7,11\}$.
Si $p$ est premier, les inversibles de $\ZM/p^2\ZM$ sont les $a\mod p^2$
tels que $p$ ne divise pas $a$. Il y en a donc $p^2-p$.
\endexo

\exo
Résoudre les équations suivantes:

(a) $2x = 37$ dans $\ZM/21\ZM$,\quad
(b) $5x=15$ dans $\ZM/25\ZM$,\quad
(c) $3x=7$ dans $\ZM/18\ZM$.

\noindent Explicitez la résolution générale de l'équation $ax=b$ dans
$\ZM/c\ZM$.
\cor
\qq
Comme $(2,21)=1$, $2$ est inversible modulo $21$. On a donc
  $2x=37\mod 21=16\mod 21$ ssi $x=8\mod 21$.
\qq $5x=15\mod 25$ ssi $x=3\mod 5$ ssi $x=3,8,13,18,23\mod 25$.
\qq $3x=7\mod 18$ n'a pas de solution car $3$ ne divise pas $7$.

Tout d'abord, il faut remarquer que dans un anneau $A$
  quelconque, si $a$ est un élément inversible de $A$, 
l'équation $ax=b$ est équivalente à $x=a^{-1}b$.
Ainsi, dans le cas particulier $A=\ZM/n\ZM$ on a : si $(a,n)=1$,
$ax=b\mod n$ ssi $x=a^{-1}b\mod n$.

Si $(a,n)=d>1$, on va se ramener au cas précédent en factorisant $d$
dans $a$ et $n$. Soit donc $a=da'$ et $n=dn'$. L'équation devient 
$da'x=b\mod dn'$. Puisque $d$ divise $da'x$ et $dn'$ il doit aussi
diviser $b$. Écrivons $b=db'$; on a 
$da'x=db'\mod dn'$. En remontant dans $\ZM$, on obtient
$da'x=db'\mod dn'$ ssi il existe $q\in \ZM$ tel que 
$da'x=db'+q dn'$ ssi il existe $q\in \ZM$ tel que $a'x=b'+qn'$
ssi $a'x=b'\mod n'$. En résumé on voit qu'on a divisé toute 
l'équation par $d$ {\em y compris le module $n$}. Comme maintenant 
$(a',n')=1$, on peut résoudre comme précédemment  en $x={a'}^{-1}b' \mod n'$. 
On a alors plusieurs solutions modulo $n$. En effet, si $\alpha$ est
un représentant de ${a'}^{-1}b' \mod n'$, les solutions modulo $n$ 
sont les $\alpha + kn' \mod n$ avec $k=0,1,\dots, d-1$ et il y en a
$d$.
En résumé on a:
\begin{lemme*} Résolution de $ax=b\mod n$:
\begin{enumerate}
\item Si $(a,b)=1$ une solution unique $x=a^{-1}b\mod n$.
\item Si $(a,b)=d> 1$ et $d$ ne divise pas $b$, pas de solution
\item Si $(a,b)=d> 1$ et $d$ divise $b$ il y a $d$ solutions: avec 
$a=a'd$, $b=b'd$, $n=n'd$, avec $\alpha=b'{a'}^{-1} \mod n'$, ce sont
  les $x=\alpha+kn'\mod n$ avec $k\in \{0,\dots,d-1\}$.
\end{enumerate}
\end{lemme*}
\endexo

\exocor
Résoudre les systèmes d'équations:
$$
(a)\;\left\{
\begin{aligned}
x+y &=6\\
2x-y&=8
\end{aligned}
\right.,\quad x,y\in \ZM/11\ZM
\qquad
(b)\;\left\{
\begin{aligned}
3x+17y& =9\\
9x+6y &= 6
\end{aligned}
\right.,\quad x,y\in \ZM/51\ZM.
$$

Explicitez les opérations transformant un système linéaire en un système
équivalent lorsque les coefficients sont dans un anneau $A$ (commutatif
unitaire).
\cor

Sur un anneau $A$, les transformations élémentaires suivantes 
conduisent à un système linéaire équivalent:
\begin{enumerate}
\item Échange de deux lignes
\item Multiplication d'une ligne par un élément inversible de $A$
\item Remplacement d'une ligne $L_i$ par $L_i+aL_j$ avec $a\in A$.
\end{enumerate}

Le premier système se résoud très facilement:
\begin{equation*}
\left\{
\begin{array}{ll}
x+y& =6\mod 11\\
2x-y&=8\mod 11
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{ll}
y& =6-x\mod 11\\
3x-6&=8\mod 11
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{ll}
y& =9\mod 11\\
x&=8\mod 11
\end{array}
\right.
\end{equation*}
Dans le deuxième, on a $51=3\cdot 17$. Tous les termes sont
divisibles par $3$ sauf $17y$. Il est donc nécessaire que $3$ divise
$y$.
En posant $y=3z$ on obtient 

\begin{align*}
\left\{
\begin{array}{ll}
3x+17y& =9 \mod 51\\
9x+6y&=6 \mod 51
\end{array}
\right.
&\Leftrightarrow
\left\{
\begin{array}{ll}
x+17z& =3 \mod 17\\
3x+6z&=2 \mod 17
\end{array}
\right.\\
&\Leftrightarrow
\left\{
\begin{array}{ll}
x& =3 \mod 17\\
z&=13 \mod 17
\end{array}
\right.\\
&\Leftrightarrow
\left\{
\begin{array}{ll}
x& =3, 20, 37 \mod 51\\
y&=39 \mod 51
\end{array}
\right.
\end{align*}
\endexo

\exocor Trouver tous les $x\in\ZM$ vérifiant
$$
\left\{
\begin{aligned}
2x& \equiv 37\pmod{5},\\
3x& \equiv 48\pmod{7}.
\end{aligned}
\right.
$$
\cor
 Comme $2\in (\ZM/5\ZM)^*$ et $3\in (\ZM/7\ZM)^*$, on obtient
$$
\left\{
\begin{array}{rcl}
2x& = &37\mod 5\\
3x&= &48\mod 7
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{rcl}
2x& = &2\mod 5\\
3x&= &6\mod 7
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{rcl}
x& = &1\mod 5\\
x&= &2\mod 7
\end{array}
\right.
$$
On utilise la relation de Bezout $3\cdot5-2\cdot 7=1$ pour remarquer que 
$$
15=
\begin{cases}
0\mod 5\\
1\mod 7
\end{cases}
\quad\text{ et }\quad
-14=
\begin{cases}
1\mod 5\\
0\mod 7
\end{cases}.
$$
On en déduit que
$$
2\cdot15-14=16=
\begin{cases}
1\mod 5\\
2\mod 7
\end{cases}.
$$
Alors $x$ vérifie le système $\Leftrightarrow$ $x-16$ est divisible par $5$ et
$7$ $\Leftrightarrow$ $x-16$ est divisible par $35$. Finalement l'ensemble des
solutions est l'ensemble des $x=16\mod 35$.
\endexo

\exocor
Résoudre les équations du second degré:
\qq $x^2+x+7=0$ dans $\ZM/13\ZM$.
\qq $x^2-2x+3=0$ dans $\ZM/4\ZM$.
\qq $x^2-4x+3=0$ dans $\ZM/12\ZM$.

\noindent Explicitez une méthode de résolution générale.
\cor
Pour résoudre une équation du second degré 
du type $x^2+2bx+c=0$ dans un anneau $A$,
on peut procéder comme dans $\RM$ en «complétant le carré»:
\begin{align*}
x^2+2bx+c=0 \Leftrightarrow (x+b)^2 -b^2+c=0.
\end{align*}
Il faut ensuite discuter:


\begin{itemize}
\item Si $b^2-c$ n'est pas un carré dans $A$, il n'y a pas de solution. 

\item Si $b^2-c=a^2$ alors
\begin{align*}
x^2+bx+c=0 \Leftrightarrow (x+b)^2 -a^2=0 \Leftrightarrow (x+b-a)(x+b+a)=0.
\end{align*}
Alors $x=-b+a$ ou $x=-b-a$ ou $(x+b-a, x+b+a)$ est un couple de 
diviseurs de zéro (attention à ne pas oublier ce dernier cas\dots).
\end{itemize}
L'équation $ax^2+bx+c=0$ se ramène au cas précédent si d'une
part
$a$ est un inversible de $A$ et d'autre part si $2$ est inversible
dans $A$ : on peut alors toujours écrire $a^{-1}b=2b'$.

\qq $x^2+x+7=0$  dans $\ZM/13\ZM$:
  $x^2+x+7=(x+7)^2-49+7=(x+7)^2-3 \mod 13$. On a $3=16=4^2\mod 13$
  donc on obtient $(x+7-4)(x+7+4)=(x+3)(x+11)$ soit $x=10,2\mod 13$.
\qq $x^2-2x+3=0$ dans $\ZM/4\ZM$:
$x^2-2x+3=(x-1)^2+2$. Les carrés dans $\ZM/4\ZM$ sont $0,1$. Comme $2$
  n'est pas un carré il n'y a pas de solutions.
\qq $x^2-4x+3=0$ dans $\ZM/12\ZM$:
$x^2-4x+3=(x-2)^2-1=(x-3)(x-1)$. Les diviseurs de zéro dans
  $\ZM/12\ZM$ sont: $\set{2,3,4,6,8,9,10}$. À part les solutions $x=1,3 \mod
12$, il faut examiner les couples de diviseurs de $0$: $x-1 =
2,3,4,6,8,9,10$, correspond respectivement à $x-3=0,1,2,4,6,7,8$. Les
couples $(x-1,x-3) = (6,4), (8,6)$ donnent deux nouvelles solutions
$x = 7,9 \mod 12$. On obtient 4 solutions en tout.

En fait, sur cet exemple, il est plus rapide et moins risqué de rechercher
tous les $y$ modulo $12$ tels que $y^2 = 1$, et poser $x = y+2$. Un tel $y$
est inversible, donc à chercher parmi $\pm 1,\pm 5$ modulo $12$: tous les 4
conviennent (leur carré est $1$) et on retrouve les mêmes solutions que
par l'autre méthode.
\endexo
\end{document}
