Premiers entre eux

Prenons 14 jetons rouges et 25 jetons jaunes. Les rouges peuvent former des paquets égaux de 2 ou de 7, tandis que les jaunes peuvent former des paquets égaux de 5. Aucun nombre de paquets supérieur à 1 ne convient aux deux couleurs. Leur seul diviseur commun positif est donc 1 : les nombres 14 et 25 sont premiers entre eux. Cela ne signifie pas que 14 ou 25 est premier ; c’est la relation entre les deux nombres qui compte.

Deux entiers relatifs a et b, non tous deux nuls, sont premiers entre eux, ou copremiers, lorsque leur plus grand commun diviseur vaut 1. Autrement dit, le seul entier positif qui divise à la fois a et b est 1. Cette condition s’écrit $\mathrm{P}\mathrm{G}\mathrm{C}\mathrm{D}(a,b)=1\backslash mathrm\{PGCD\}(a,b)=1$. Elle équivaut aussi à l’absence de facteur premier divisant à la fois a et b.

L’identité de Bézout donne un autre critère exact : il existe des entiers relatifs u et v tels que $au+bv=1au+bv=1$. Pour 14 et 25, on peut choisir u égal à 9 et v égal à −5, car $9\times 14-5\times 25=19\backslash times14-5\backslash times25=1$.

Enfin, le lemme de Gauss précise leur rôle en divisibilité. Si a et b sont premiers entre eux et si a divise le produit bc, alors a divise c. Les signes ne changent pas la propriété, car le PGCD est calculé à partir des valeurs absolues.

Vérifions que 14 et 25 sont premiers entre eux avec l’algorithme d’Euclide. Les données sont les deux entiers positifs 14 et 25. À chaque étape, on divise le plus grand nombre par le plus petit et on conserve le reste.

1. La division de 25 par 14 donne un quotient égal à 1 et un reste égal à 11 : $25=1\times 14+1125=1\backslash times14+11$.

2. La division de 14 par 11 donne un quotient égal à 1 et un reste égal à 3 : $14=1\times 11+314=1\backslash times11+3$.

3. La division de 11 par 3 donne un quotient égal à 3 et un reste égal à 2 : $11=3\times 3+211=3\backslash times3+2$.

4. La division de 3 par 2 donne un quotient égal à 1 et un reste égal à 1. La division suivante a un reste nul. Le dernier reste non nul est donc 1 : le PGCD de 14 et 25 vaut 1.

Un contrôle indépendant consiste à remonter les égalités. On obtient $9\times 14-5\times 25=19\backslash times14-5\backslash times25=1$, une identité de Bézout. Cette égalité confirme que tout diviseur commun de 14 et 25 divise 1.

Pour réduire une fraction, on calcule le PGCD du numérateur et du dénominateur. Si ce PGCD vaut 1, comme pour 14/25, la fraction est déjà irréductible. Sinon, on divise les deux termes par leur PGCD.

En arithmétique modulaire, un entier admet un inverse modulo un entier positif n exactement lorsqu’il est premier avec n. L’identité de Bézout fournit alors cet inverse ; en l’absence de coprimalité, il faut résoudre le problème sans division modulaire.

Dans un parcours cyclique de n positions, avancer toujours de k positions visite tout le cycle si k et n sont premiers entre eux. Sinon, le parcours reste dans un sous-ensemble ; une autre longueur de pas doit être choisie pour atteindre chaque position.

Nombres premiers. Un nombre premier possède exactement deux diviseurs positifs, 1 et lui-même. Deux nombres premiers entre eux ont seulement 1 comme diviseur commun positif. Ainsi, 14 et 25 sont composés, mais ils sont premiers entre eux.

Entiers distincts. Le fait que deux entiers soient différents ne suffit pas. Par exemple, 14 et 21 sont distincts, mais leur PGCD vaut 7 : ils ne sont pas premiers entre eux.

Premiers entre eux deux à deux. Dans une famille, cette expression exige un PGCD égal à 1 pour chaque paire. Avoir seulement un PGCD global égal à 1 est plus faible : 6, 10 et 15 ont un PGCD global égal à 1, mais aucune de leurs paires n’est copremière.

Présence de zéro. Si a est un entier non nul, le PGCD de 0 et de a est la valeur absolue de a. Par conséquent, 0 n’est copremier qu’avec 1 et −1. Pour 0 et 14, le PGCD vaut 14, non 1.

Entiers négatifs. Un signe moins n’ajoute aucun facteur premier. Il faut calculer le PGCD sur les valeurs absolues : −14 et 25 sont premiers entre eux comme 14 et 25. Les coefficients de Bézout changent éventuellement de signe.

Coefficients de Bézout non uniques. Une égalité telle que $9\times 14-5\times 25=19\backslash times14-5\backslash times25=1$ prouve la coprimalité, mais elle ne fournit pas une paire unique de coefficients. Ajouter 14 au coefficient de 25 et retrancher 25 à celui de 14 produit une autre égalité valide.

Recherche partielle des diviseurs. Ne trouver aucun petit facteur commun ne suffit pas à conclure. Par exemple, 77 et 121 ne partagent ni 2, ni 3, ni 5, mais leur PGCD vaut 11. L’algorithme d’Euclide fournit un test complet.

Le PGCD précise le calcul du plus grand diviseur partagé et le critère qui décide si deux entiers sont copremiers.

L’algorithme d’Euclide détaille la suite de divisions qui calcule efficacement le PGCD et permet de retrouver des coefficients de Bézout.

L’arithmétique modulaire montre pourquoi la coprimalité conditionne l’existence d’un inverse et de nombreuses divisions dans les calculs modulo un entier.