Méthodes : Arithmétique
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$;
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.
Démontrer qu'un entier dépendant d'un paramètre est divisible par un petit entier
Pour démontrer qu'un entier $f(n)$ dépendant d'un paramètre $n$ est divisible par un (petit) entier $m$, on peut raisonner par disjonction de cas :
- si $n\equiv 0\ [m]$, on prouve par des opérations algébriques sur les congruences que $f(n)\equiv 0\ [m]$;
- si $n\equiv 1\ [m]$, on prouve par des opérations algébriques sur les congruences que $f(n)\equiv 0\ [m]$;
- et ainsi de suite on traite tous les cas jusque $n\equiv m-1\ [m]$;
Équation de congruence du premier degré?