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 de la primalité relative

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)$.

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

4.1. Le théorème chinois des restes

Il existe une expression commode de l’indicateur d’Euler $\phi(n)$ d’un entier naturel non nul $n$ en fonction des facteurs premiers de $n$. Cette expression s’obtient à partir du théorème dit « chinois » des restes, lequel permet de trouver, étant donnés une suite finie d’entiers naturels non nuls $n_1,\ldots,n_r$ deux-à-deux premiers entre eux, et des restes $x_1,\ldots,x_r$ modulo $n_1,\ldots,n_r$ (c’est-à-dire $x_i\in [[0,n_i-1]]$ pour tout $i$), un reste $x$ unique modulo le produit $n=n_1\times \ldots\times n_r$ et congru à chacun des $x_i$ modulo $r_i$. Ce théorème peut s’énoncer dans le cadre de la théorie des anneaux, en considérant que si $A_1,\ldots,A_r$ sont $r$ anneaux unitaires, l’anneau produit des $A_i$ est par définition l’ensemble produit $A=A_1\times \ldots \times A_n$, où l’on définit l’addition et la multiplication coordonnée-par-coordonnée : si $(a_1,\ldots,a_r),(b_1,\ldots,b_r)\in A$, alors on pose $(a_1,\ldots,a_r)+(b_1,\ldots,b_r)=(a_1+b_1,\ldots,a_r+b_r)$ et $(a_1,\ldots,a_r).(b_1,\ldots,b_r)=(a_1b_1,\ldots,a_rb_r)$. Dans ce cas, le zéro de $A$ est le $r$-uplet $(0,\ldots,0)$ et l’unité est le $r$-uplet $(1,\ldots,1)$. En choisissant $A_i=\mathbb Z/n_i\mathbb Z$ pour $i=1,\ldots,r$, puisque chaque $n_i$ divise $n$ on a un homomorphisme naturel d’anneaux $f:\mathbb Z/n\mathbb Z\to A$, qui associe à la classe $[m]_n$ d’un entier relatif modulo $n$ ses $r$ classes $([m]_{n_1},\ldots, [m]_{n_r})$ modulo les $n_i$.

Théorème 4
Si $n_1,\ldots,n_r$ sont des entiers naturels non nuls et deux-à-deux premiers entre eux et $n=n_1\times\ldots\times n_r$, alors l’homomorphisme $f:[m]_n\in\mathbb Z/n\mathbb Z\mapsto ([m]_{n_1},\ldots,[m]_{n_r})\in \mathbb Z/n_1\mathbb Z\times\ldots\times \mathbb Z/n_r\mathbb Z$, est un isomorphisme.

Ce théorème se démontre par récurrence sur $r\geq 2$, en utilisant des relations de Bézout, et sa traduction en termes de restes est exactement la propriété énoncée.

4.2. Expression de l’indicateur d’Euler

Du théorème chinois des restes, on déduit alors facilement que dans cette situation, on a $\phi(n)=\phi(n_1)\times\ldots\times \phi(n_r)$, si bien qu’on peut en tirer une expression de $\phi(n)$ lorsqu’on connaît une décomposition de $n$ en nombres premiers $n=p_1^{a_1}\ldots p_r^{a_r}$. En effet, par définition les nombres $n_i=p_i^{a_i}$ sont deux-à-deux premiers entre eux, et on a donc :

Corollaire 1
Si $n$ est un entier naturel non nul et $n=p_1^{a_1}\ldots p_r^{a_r}$ est sa décomposition en nombres premiers, alors on a $\phi(n)=n\times (1-1/p_1)\times \ldots \times (1-1/p_n)$.

La démonstration repose sur le calcul de $\phi(p ^k)=p^k-p^{k-1}$, pour une puissance $p^k$ d’un nombre premier $p$. En effet, les nombres entre $1$ et $p^k$ qui ne sont pas premiers à $p^k$ sont les multiples de $p$, et ce sont les nombres de la forme $m\times p$ pour $m=1,\ldots,p^{k-1}$, qui sont donc au nombre de $p^k-p^{k-1}$.

4.3. Structure des unités de $\mathbb Z/n\mathbb Z$

Du théorème 4, on peut également élucider la structure du groupe multiplicatif des unités de $\mathbb Z/n\mathbb Z$ lorsque $n$ est impair. En effet, de la décomposition $n=p_1^{a_1}\ldots p_r^{a_r}$ de $n$ en facteurs premiers, et de l’isomorphisme d’anneaux (uniatires) $\mathbb Z/n\mathbb Z\cong \mathbb Z/p_1^{a_1}\mathbb Z\times\ldots \times \mathbb Z/p_r^{a_r} \mathbb Z$ qu’on en déduit du théorème des restes, on a directement une décomposition du groupe multiplicatif $(\mathbb Z/n\mathbb Z)^\times$ sous la forme du produit $(\mathbb Z/p_1^{a_1}\mathbb Z)^\times\times\ldots\times (\mathbb Z/p_r^{a_r}\mathbb Z)^\times$. Or, on démontre (de manière plus élaborée) que si $p$ est impair, le groupe multiplicatif $(\mathbb Z/p^k\mathbb Z)^\times$ (de cardinal $\phi(p^k)=p^k-p^{k-1}$ par ce qui précède…) est toujours cyclique, et donc isomorphe au groupe additif $(\mathbb Z/\phi(p^k)\mathbb Z,+)$.

Dans le cas où $n$ est pair, c’est que l’un des facteurs premiers de $n$, on peut supposer que c’est $p_1$ si on ordonne ceux-ci, est $2$, de sorte qu’il reste à élucider la structure du groupe multiplicatif $(\mathbb Z/2^k\mathbb Z)^\times$ en général. Or, si $k=1$, ce groupe est trivial, si $k=2$ il est cyclique d’ordre $2$ (ne contenant que les éléments $[1]$ et $[3]$ avec $[3]^2=[1]$), et si $k\geq 3$ on sait démontrer que $(\mathbb Z/2^k\mathbb Z)^\times$ est isomorphe au produit direct de ses sous-groupes engendrés respectivement par $[-1]$ et $[5]$. En somme, les anneaux quotients de $\mathbb Z$ sont donc bien compris, et l’élucidation de leur structure additive et multiplicative est un raffinement de la théorie des nombres premiers entre eux.