Arithmétique dans ℤ

Divisibilité. $a\mid b$ signifie qu'il existe $k\in\Z$ tel que $b=ka$. Attention à l'orientation : $a\mid b$ se lit « $a$ divise $b$ », donc $a$ est le petit. Beaucoup d'erreurs viennent de là.

Pourquoi ce n'est pas un ordre sur $\Z$. La divisibilité est réflexive et transitive partout, mais l'antisymétrie tombe dans $\Z$ : $2\mid-2$ et $-2\mid2$ sans que $2=-2$. Sur $\N$, l'antisymétrie tient, et l'on obtient bien une relation d'ordre — partielle, puisque $3$ et $5$ ne sont pas comparables. C'est l'exemple d'ordre partiel promis au chapitre 1.

La division euclidienne est l'outil fondamental de tout le chapitre. Son énoncé contient deux affirmations distinctes qu'il faut savoir démontrer séparément : l'existence du couple $(q,r)$, qui repose sur le fait que toute partie non vide de $\N$ a un plus petit élément, et son unicité, qui se démontre en supposant deux couples et en majorant la différence des restes.

La condition sur le reste, $0\leqslant r<|b|$, est ce qui force l'unicité. Sans elle, $17=3\times5+2$ et $17=2\times5+7$ seraient deux écritures également valables.

Le PGCD est le plus grand pour deux ordres à la fois, et c'est ce qui fait sa force. C'est le plus grand diviseur commun au sens de l'ordre usuel, et c'est aussi le plus grand au sens de la divisibilité : tout diviseur commun de $a$ et $b$ divise $a\wedge b$. La seconde propriété est bien plus utile que la première, et c'est elle qu'on emploie en démonstration.

L'algorithme d'Euclide repose sur une observation d'une ligne : si $a=bq+r$, alors les diviseurs communs de $a$ et $b$ sont exactement ceux de $b$ et $r$ — parce qu'un diviseur commun divise toute combinaison linéaire. Donc $a\wedge b=b\wedge r$, et l'on recommence avec un reste strictement plus petit. Comme les restes forment une suite d'entiers naturels strictement décroissante, elle atteint $0$ : l'algorithme termine, et le dernier reste non nul est le PGCD.

La relation de Bézout — l'existence de $u$ et $v$ tels que $au+bv=a\wedge b$ — s'obtient en remontant les divisions de l'algorithme. C'est l'algorithme d'Euclide étendu, et c'est lui que vous coderez. Attention : le couple $(u,v)$ n'est pas unique, il y en a une infinité.

Le PPCM joue le rôle symétrique : c'est le plus petit multiple commun, et tout multiple commun en est un multiple. La relation $ (a\wedge b)\times(a\vee b)=|ab|$ permet de le calculer sans effort supplémentaire une fois le PGCD connu.

Le théorème de Bézout est une équivalence, et c'est ce qui le rend si utile : $a$ et $b$ sont premiers entre eux si et seulement si il existe $u,v$ avec $au+bv=1$. Le sens direct vient de la relation de Bézout du point b ; la réciproque est immédiate, puisqu'un diviseur commun divise alors $1$.

En pratique, c'est le moyen le plus rapide de démontrer que deux entiers sont premiers entre eux : on exhibe une combinaison valant $1$. Pour montrer que $n$ et $n+1$ sont premiers entre eux, il suffit d'écrire $1\times(n+1)-1\times n=1$.

Le lemme de Gauss — si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$ — est l'outil qui permet de « simplifier » une divisibilité. Sa démonstration tient en deux lignes à partir de Bézout : on multiplie $au+bv=1$ par $c$.

La distinction « dans leur ensemble » / « deux à deux » est explicitement signalée. $6$, $10$ et $15$ ont pour PGCD $1$, donc sont premiers entre eux dans leur ensemble ; pourtant aucun couple ne l'est. L'implication ne va que dans un sens.

Le crible d'Ératosthène repose sur une remarque qui rend l'algorithme efficace : si $n$ n'est pas premier, il admet un diviseur premier inférieur ou égal à $\sqrt n$. On peut donc s'arrêter là. C'est aussi le test de primalité naïf que vous coderez en informatique.

L'infinitude des nombres premiers se démontre par l'absurde, en une demi-page, selon un argument dû à Euclide : si $p_1,\dots,p_n$ étaient les seuls, l'entier $N=p_1\cdots p_n+1$ ne serait divisible par aucun d'eux, or il admet un diviseur premier. Contradiction. Sachez la refaire, elle est régulièrement demandée en colle.

La valuation $p$-adique $v_p(n)$ est l'exposant de $p$ dans la décomposition de $n$. Sa force est de transformer les questions multiplicatives en questions additives : $v_p(ab)=v_p(a)+v_p(b)$. Divisibilité, PGCD et PPCM se lisent alors terme à terme, avec des minimums et des maximums. C'est de loin l'outil le plus commode pour les exercices sur les exposants.

Une congruence est une égalité qui oublie les multiples de $n$. $a\equiv b\ [n]$ signifie que $n$ divise $a-b$. C'est la relation d'équivalence promise au chapitre 1, et ses classes forment une partition de $\Z$ — mais on s'arrête là, puisque l'ensemble quotient est hors programme.

Ce qu'on peut faire, et ce qu'on ne peut pas. On additionne, on multiplie, on élève à une puissance : les congruences se comportent comme des égalités. On ne peut pas simplifier : de $6\equiv0\ [4]$ et $6=2\times3$ on ne tire rien sur $2$ ou $3$. La simplification n'est licite que si le facteur simplifié est premier avec le module — c'est le lemme de Gauss déguisé.

L'inversibilité modulo $n$ est un résultat déguisé de Bézout : $a$ admet un inverse modulo $n$ si et seulement si $a\wedge n=1$, et cet inverse est le $u$ de la relation $au+nv=1$. C'est exactement ce que calcule l'algorithme d'Euclide étendu, et c'est le cœur du chiffrement RSA — que vous croiserez peut-être en informatique.

Le petit théorème de Fermat donne un raccourci pour les grandes puissances : modulo un nombre premier $p$, élever à la puissance $p$ ne change rien. C'est ce qui permet de calculer $2^{1000}$ modulo $7$ sans jamais écrire un nombre de plus de deux chiffres.