Deux nombres entiers sont dits premiers entre eux si ils n’ont pas de facteur premier en commun : il sont donc premiers « l’un par rapport à l’autre ». Le nombre des restes modulo un entier naturel non nul $n$ qui sont premiers avec $n$ est ce qu’on appelle l’indicateur d’Euler de $n$, et il s’interprète grâce au théorème de Bézout comme le nombre de restes inversibles modulo $n$. On en tire le petit théorème de Fermat, et du théorème chinois des restes, la structure des anneaux quotients de $\mathbb Z$ et de leurs groupes d’éléments inversibles.

1. Nombres premiers entre eux et indicatrice d’Euler

1.1. PGCD et nombre premiers entre eux

En arithmétique élémentaire (théorie des nombres entiers relatifs), on étudie les nombres premiers à partir des nombres premiers entre eux. Il s’agit d’une notion relative, qui relève de la « mesure » de combien deux nombres $m$ et $n$ sont premiers « l’un par rapport à l’autre ». Le concept essentiel utilisé ici est celui d’une « commune mesure arithmétique » de $m$ et $n$ appelée le plus grand commun diviseur de $m$ et $n$ ou p.g.c.d de $m$ et $n$. Le p.g.c.d de deux entiers relatifs $m$ et $n$ non nuls se définit simplement comme le plus grand entier naturel $d$ qui divise à la foi $m$ et $n$, qu’on note $pgcd(m,n)$.

Puisque $1$ divise toujours à la fois $m$ et $n$, cet entier existe bel et bien et est toujours supérieur à $1$. Lorsqu’il vaut précisément $1$, c’est qu’en quelque sorte $m$ et $n$ n’ont « pas de diviseur commun » (non trivial), et qu’on dit alors qu’ils sont premiers entre eux. On utilise cette notion pour démontrer le théorème fondamental de l’arithmétique, et en retour on peut déduire de celui-ci que deux entiers non nuls $m$ et $n$ sont premiers entre eux si et seulement si ils n’ont aucun facteur premier en commun.

Exemple 1
Les nombres $16$ et $9$ sont premiers entre eux, car les diviseurs de $16$ sont $1$, $2$, $4$ et $16$ tandis que les diviseurs de $9$ sont $1$, $3$, et $9$. En revanche, les nombres $12$ et $21$ ne sont pas premiers entre eux, puisque $3$ en est un diviseur commun, qui est aussi leur p.g.c.d, puisque $12=2^2.3$ et $21=3.7$ sont leurs décompositions en nombres premiers.

1.2. L’indicatrice d’Euler

Or, si $n$ est un entier relatif non nul, il existe toujours une infinité d’entiers relatifs $m$ premiers à $n$, c’est-à-dire tels que $m$ et $n$ sont premiers entre eux : il suffit de considérer tous les entiers relatifs $m$ dont la décomposition en nombres premiers ne mentionne aucun facteur premier de $n$. En revanche, si nous nous limitons aux seuls entiers naturels (non nuls) premiers à $n$ et inférieurs à $n$ (c’est-à-dire parmi les nombres $1,\ldots,n$), leur nombre est fini et présente un intérêt arithmétique singulier. On l’appelle l’indicateur d’Euler de $n$, qu’on note $\phi(n)$. Ainsi, on définit de cette manière une fonction $\phi:\mathbb Z^*\to \mathbb N$ ($\mathbb Z^*$ étant l’ensemble des entiers relatifs non nuls), qu’on appelle indicatrice d’Euler. Par exemple, pour un entier naturel premier $p$, on a $\phi(p)=p-1$, puisque par définition, les nombres $1,2,\ldots,p-1$ sont tous premiers à $p$.

Exemple 2
Les diviseurs positifs de $12$ sont $1$, $2$, $3$, $4$, $6$ et $12$. Les nombres $5$, $7$ et $11$ sont donc premiers à $12$, si bien que $\phi(12)=4$ (il ne faut pas oublier de compter $1$ !). Quelle est la valeur de $\phi(33)$ ?

2. Théorème de Bézout et inversion modulaire

2.1. Relations de Bézout entre nombres premiers entre eux

La notion de plus grand commun diviseur de deux entiers relatifs non nuls $m$ et $n$ conduit à l’existence de relations de Bézout, qui permettent de donner une interprétation modulaire de la primalité relative et de l’indicateur d’Euler. Le théorème de Bézout énonce en effet :

Théorème 1
Si $m$ et $n$ sont deux entiers relatifs non nuls, alors il existe deux entiers relatifs $u$ et $v$ tels que $m.u+n.v=pgcd(m,n)$.

Trouver deux tels entiers relatifs $u$ et $v$ (qui ne sont pas uniques), c’est trouver une « relation de Bézout » entre $m$ et $n$. Pour cela, on peut utiliser l’algorithme d’Euclide, qui procède par divisions euclidiennes successives. Or, dans le cas où $m$ et $n$ sont premiers entre eux, c’est-à-dire où $pgcd(m,n)=1$, le théorème de Bézout nous garantit qu’il existe $u,v\in\mathbb Z$ tels que $m.u+n.v=1$. Inversement, on montre facilement que si il existe une telle relation, alors $m$ et $n$ sont premiers entre eux.

Exemple 3
Puisque $pgcd(12,21)=3$, on peut trouver des entiers relatifs $u$ et $v$ tels que $12u+21v=3$ : on a $21=12+ç$ et $12=9+3$, d’où $3=12-9=12-(21-12)=12.2-21$, donc $u=2$ et $v=-1$ conviennent. De même, puisque $18$ et $55$ sont premiers entre eux, on peut trouver $u$ et $v$ tels que $18u+55v=1$, ici simplement $u=3$ et $v=-1$, puisque $55=18.3+1$.

2.2. Interprétation modulaire des nombres premiers entre eux

Un élément $a$ d’un anneau unitaire $A$ est dit inversible s’il possède un inverse, c’est-à-dire s’il existe $b\in A$ tel que $a.b=1$.

Exemple 4
Les seuls éléments inversibles de $\mathbb Z$ sont $1$ et $-1$, tandis que tout nombre rationnel non nul est inversible.

L’existence de relations de Bézout entre deux entiers relatifs premiers entre eux s’interprète en termes d’inversibilité en arithmétique modulaire (voir Division euclidienne). Soit en effet $n$ un entier naturel non nul et considérons l’anneau $\mathbb Z_n$ des restes dans la division euclidienne par $n$, avec ses opérations d’addition et de multiplication modulaires : on sait que $\mathbb Z_n$ est isomorphe comme anneau à l’anneau quotient $\mathbb Z/n\mathbb Z$ (voir Théorie des anneaux), on peut donc travailler dans celui-ci.

Si $m$ est un entier relatif non nul premier à $n$, par le théorème 1 de Bézout on peut trouver $u,v\in\mathbb Z$ tels que $m.u+n.v=1$. En prenant les classes des deux membres modulo $n$, on obtient l’égalité $[m].[u]+[n].[v]=[1]$, c’est-à-dire $[m].[u]=[1]$, puisque $[n]=[0]$ modulo $n$ : autrement dit, $[m]$ est inversible dans $\mathbb Z/n\mathbb Z$. Mais la réciproque est évidemment vraie : si $[m]$ est inversible modulo $n$, il existe $u\in\mathbb Z$ tel que $[m].[u]=[1]$, donc par définition on a $mu-1\in n\mathbb Z$, donc il existe $u\in\mathbb Z$ tel que $mu-1=nv$, ou encore $mu+n(-v)=1$, et $m$ est premier à $n$. Nous avons donc démontré :

Théorème 2
Si $m$ est un reste modulo $n>0$, alors $m$ est inversible dans $\mathbb Z_n$ si et seulement si $m$ et $n$ sont premiers entre eux.

Par définition de l’indicateur d’Euler $\phi(n)$, celui-ci peut donc s’interpréter comme le nombre de restes inversibles modulo $n$, si nous admettons que $\phi(1)=1$.

2.3. Le petit théorème de Fermat

L’interprétation de l’indicateur d’Euler $\phi(n)$ comme nombre de restes inversibles modulo $n$ repose sur l’interprétation structurelle de ces restes comme formant un anneau isomorphe à $\mathbb Z/n\mathbb Z$. L’ensemble des éléments inversibles de cet anneau forme également un groupe, d’élément neutre $[1]$, qui est donc de cardinal $\phi(n)$. Or, par le théorème de Lagrange tout élément inversible $[m]$ de $\mathbb Z/n\mathbb Z$ vérifie donc l’égalité $[m]^{\phi(n)}=[1]$. En traduisant ceci sur les entiers naturels $m$ dont la classe $[m]$ est inversible modulo $n$, nous pouvons reformuler ce résultat sous la forme du « petit théorème de Fermat » :

Théorème 3
Si $n$ est un entier positif et $m$ un entier relatif non premier à $n$, alors on a $m^{\phi(n)}\equiv 1\ mod(n)$, autrement dit $m^{\phi(n)}$ est congru à $1$ modulo $n$ (c’est-à-dire, $n$ divise $m^{\phi(n)}-1$).

Ce résultat est souvent plus connu et utilisé lorsque $n=p$ est un nombre premier : dans ce cas, puisque $\phi(p)=p-1$ ,on peut le reformuler comme suit :

Corollaire
Si $p$ est un entier naturel premier et $m$ est un entier relatif non nul, alors on a $m^{p-1}\equiv 1\ mod(p)$.

3. Théorème chinois et indicatrice d’Euler

3.1. Le théorème chinois des restes