Méthodes : arithmétique des entiers

Calculer le reste $a^n$ dans la division par $k$

Pour calculer le reste de $a^n$ dans la division par $k$,

on commence par rechercher un entier $m\geq 1$ tel que $a^m\equiv 1\ [k]$ (on pourra calculer les puissances successives, ou utiliser le petit théorème de Fermat);
si $n\equiv r\ [m]$, alors $n=qm+r$ et $a^n\equiv (a^m)^qa^r\ [k]\equiv a^r\ [k]$;
il reste à calculer le reste de $a^r$ dans la division par $k$;

(voir cet exercice).

Calculer le pgcd de deux entiers $a$ et $b$

On peut utiliser l'algorithme d'Euclide (voir cet exercice).
On peut utiliser la décomposition en facteurs premiers des entiers concernés (voir cet exercice).
On peut utiliser la définition (voir cet exercice).

Résoudre une équation de Bézout $ax+by=c$

On commence par calculer $d=a\wedge b$.
Si $d$ ne divise pas $c$, alors puisque $d|ax+by$, l'équation ne peut pas avoir de solutions. Sinon, on peut tout diviser par $d$. Cela revient à supposer que $a$ et $b$ sont premiers entre eux, ce que nous supposerons désormais.
On cherche un couple d'entiers $(u,v)$ tel que $au+bv=1$. On sait qu'un tel couple existe par le théorème de Bézout, et on le détermine par l'algorithme d'Euclide étendu.
On pose $x_0=cu$ et $y_0=cv$. Alors $(x_0,y_0)$ est une solution particulière de $ax+by=c$.
Soit $(x,y)$ une solution. Alors on retranche $ax_0+by_0=c$ à $ax+by=c$, et on trouve $$a(x-x_0)=-b(y-y_0).$$ Puisque $a\wedge b=1$, ceci entraîne $a|y-y_0$ et donc $y=y_0+ak$, $k\in\mathbb Z$. On reporte alors ceci dans l'équation $a(x-x_0)=-b(y-y0)$ pour exprimer $x$ en fonction de $x_0$ et $k$.
Réciproquement, on doit prouver que les solutions trouvées conviennent.

(Voir cet exercice).

Résoudre une équation dans $\mathbb Z/n\mathbb Z$

Pour résoudre une équation linéaire, ou un système d'équations, dans $\mathbb Z/n\mathbb Z$, dans le cas où $n$ est premier, on procède comme si l'on travaillait dans $\mathbb R$ ou $\mathbb C$, notamment en utilisant la méthode du pivot de Gauss. On est souvent amené à calculer l'inverse d'un élément $\bar a$ de $\mathbb Z/n\mathbb Z$. Ceci se fait en utilisant l'algorithme d'Euclide (il s'agit en effet de trouver des coefficients de Bézout) (voir cet exercice).

Pour résoudre une équation du second degré, on met le polynôme sous forme canonique, c'est-à-dire qu'on le transforme pour l'écrire sous la forme $(x+\bar a)^2-\bar b=0$. On regarde alors si $\bar b$ est un carré dans $\mathbb Z/n\mathbb Z$. Si ce n'est pas le cas, l'équation n'admet pas de solutions. Si c'est le cas, ie si $\bar b=\bar c^2$, alors l'équation est équivalente à : $$(x+\bar a-\bar c)(x+\bar a+\bar c)=0.$$ On distingue alors deux cas :

si $n$ est premier, et donc $\mathbb Z/n\mathbb Z$ est un corps, alors on a deux solutions : $x=-\bar a+\bar c$ et $x=-\bar a-\bar c$.
si $n$ n'est pas premier, il faut plutôt chercher dans $\mathbb Z/n\mathbb Z$ toutes les solutions à l'équation $\bar y^2=\bar b$.

(voir cet exercice).