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