Définition : Diviseur et combinaison entière

Pour \(a,d\in\mathbb{Z}\), écrire \(d\mid a\) signifie qu’il existe \(k\in\mathbb{Z}\) tel que \(a=dk\). On dit que \(d\) est un diviseur de \(a\), ou que \(a\) est un multiple de \(d\). Une combinaison linéaire entière de \(a\) et \(b\) est un nombre \(ua+vb\) avec \(u,v\in\mathbb{Z}\).

Propriété : Combinaisons et transitivité

Si \(d\mid a\) et \(d\mid b\), alors \(d\mid(ua+vb)\) pour tous \(u,v\in\mathbb{Z}\). Si \(d\mid a\) et \(a\mid b\), alors \(d\mid b\).

Démonstration : Revenir à des produits entiers

Écrivons \(a=dr\) et \(b=ds\). Alors \(ua+vb=d(ur+vs)\), et \(ur+vs\in\mathbb{Z}\). Pour la transitivité, \(a=dr\) et \(b=at\) donnent \(b=d(rt)\), avec \(rt\in\mathbb{Z}\).

Définition : Plus grand commun diviseur

Pour deux entiers \(a,b\) non tous deux nuls, leur PGCD, noté \(\operatorname{PGCD}(a,b)\), est le plus grand entier positif qui divise à la fois \(a\) et \(b\).

Convention : Zéro et ensembles utilisés

Dans ce cours, \(\operatorname{PGCD}(0,0)\) n’est pas défini : tous les entiers positifs divisent \(0\) et il n’en existe pas de plus grand. On prend \(\mathbb{N}=\{0,1,2,\ldots\}\). Les inconnues des équations arithmétiques appartiennent à \(\mathbb{Z}\), sauf indication contraire.

Méthode : Pour de petits nombres : lister les diviseurs

Chercher les paires de facteurs positifs, former les deux listes complètes, puis retenir leur plus grand élément commun. Pour de grands nombres, préférer Euclide (section 2).

Exemple expliqué : Déterminer \(\operatorname{PGCD}(30,42)\)

Les paires \(1\times30\), \(2\times15\), \(3\times10\), \(5\times6\) donnent les diviseurs de 30 : \(1,2,3,5,6,10,15,30\). Celles de 42 sont \(1\times42\), \(2\times21\), \(3\times14\), \(6\times7\) : ses diviseurs sont \(1,2,3,6,7,14,21,42\). Les diviseurs positifs communs sont \(1,2,3,6\), donc \(\boxed{\operatorname{PGCD}(30,42)=6}\).

Propriété : Signes, ordre et cas immédiats

Pour \((a,b)\ne(0,0)\),

Démonstration : Comparer les diviseurs positifs

L’ordre des deux entiers ne change pas leurs diviseurs communs ; changer un signe change seulement le signe du quotient entier. Tout diviseur de \(a\) divise \(0\) et \(a\), et \(|a|\) est leur plus grand diviseur positif si \(a\ne0\). Enfin, si \(b\mid a\), les diviseurs communs sont exactement les diviseurs de \(b\), par transitivité : leur maximum est \(|b|\).

Définition : Entiers premiers entre eux

Deux entiers \(a,b\), non tous deux nuls, sont premiers entre eux lorsque \(\operatorname{PGCD}(a,b)=1\). Ils n’ont alors aucun diviseur positif commun autre que \(1\).

Proposition : Deux entiers consécutifs

Pour tout \(n\in\mathbb{Z}\), \(\operatorname{PGCD}(n,n+1)=1\).

Démonstration : La différence suffit

Un diviseur positif commun divise \((n+1)-n=1\) ; il vaut donc \(1\). Les deux nombres ne peuvent pas être nuls ensemble. Ainsi leur PGCD vaut \(1\).

Piège à éviter : Ne pas confondre deux propriétés

Être différents ou ne pas être multiples l’un de l’autre ne suffit pas pour être premiers entre eux. Pour conclure, il faut une justification : diviseurs communs, Euclide ou, plus loin, une identité de Bézout.

Propriété : Rappel : division euclidienne

Pour \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^*\), il existe un unique couple \((q,r)\in\mathbb{Z}\times\mathbb{N}\) tel que

Lemme : Conserver les diviseurs communs

Soient \((a,b)\ne(0,0)\) et \(q\in\mathbb{Z}\). Les diviseurs communs à \(a\) et \(b\) sont exactement ceux de \(b\) et \(a-bq\). En particulier,

Démonstration : Les deux sens sont nécessaires

Si \(d\mid a\) et \(d\mid b\), alors \(d\mid(a-bq)\) par combinaison entière. Réciproquement, si \(d\mid b\) et \(d\mid(a-bq)\), alors \(d\mid\bigl((a-bq)+bq\bigr)=a\). Les deux ensembles de diviseurs sont égaux, donc leurs plus grands éléments positifs aussi. Le nouveau couple ne peut être \((0,0)\), sinon \(b=0\) et \(a-bq=a=0\).

Méthode : Calculer un PGCD par Euclide

1. Remplacer les deux nombres par leurs valeurs absolues ; traiter directement le cas où l’un vaut \(0\).

2. Diviser le plus grand par le plus petit, puis remplacer le couple dividende–diviseur par diviseur–reste.

3. Répéter jusqu’à un reste nul. Le diviseur de cette dernière division est le PGCD.

Contrôler les égalités et les restes, puis vérifier que le résultat divise les deux nombres. Cette dernière vérification seule ne prouverait pas sa maximalité.

Exemple expliqué : Un fil numérique pour Euclide puis Bézout

Théorème : Terminaison et correction d’Euclide

L’algorithme précédent s’arrête et donne le PGCD des deux entiers de départ.

Démonstration : Arrêt, puis valeur obtenue

Arrêt. Tant qu’un reste est non nul, il est strictement inférieur au diviseur qui le précède. Une suite strictement décroissante d’entiers naturels ne peut pas se poursuivre indéfiniment : un reste nul finit par apparaître.

Correction. Le lemme conserve les diviseurs communs à chaque division. Le dernier couple est \((d,0)\), où \(d>0\) ; son PGCD vaut \(d\) par la propriété sur les cas immédiats. C’est donc aussi le PGCD initial.

Piège à éviter : Si la première division est exacte

Si la première division est exacte, son diviseur est le PGCD : aucun reste non nul n’a été calculé. La formule « dernier reste non nul » doit se lire avec cette exception ; « diviseur de la dernière division » reste valable.

Corollaire : Diviseurs communs et diviseurs du PGCD

Pour \((a,b)\ne(0,0)\) et \(d=\operatorname{PGCD}(a,b)\), un entier divise \(a\) et \(b\) si et seulement s’il divise \(d\).

Démonstration : Le même ensemble jusqu’au bout

Euclide conserve exactement les diviseurs communs jusqu’à \((d,0)\). Ceux-ci sont les diviseurs de \(d\), car tout entier divise \(0\). Si un argument initial est nul, cette description est immédiate.

Propriété : Réduire un couple par son PGCD

Si \(d=\operatorname{PGCD}(a,b)\), alors \(a=dA\) et \(b=dB\), où \(A,B\in\mathbb{Z}\) sont premiers entre eux.

Démonstration : Il ne reste aucun diviseur commun positif supérieur à 1

Les quotients \(A=a/d\) et \(B=b/d\) sont entiers. Si \(e>0\) divise \(A\) et \(B\), alors \(de\) divise \(a\) et \(b\). Comme \(d\) est leur plus grand diviseur positif commun, \(de\le d\). Puisque \(d>0\), \(e\le1\), donc \(e=1\).

Exemple expliqué : Garder les signes en réduisant

\(\operatorname{PGCD}(-84,126)=42\) : \(126=84+42\), puis \(84=2\times42\). Le couple réduit est \((-2,3)\), car \(-84=42(-2)\) et \(126=42\times3\). Diviser seulement par \(6\) donnerait \((-14,21)\), dont le PGCD est encore \(7\).

Théorème : Identité de Bézout pour le PGCD

Pour \((a,b)\in\mathbb{Z}^2\setminus\{(0,0)\}\), il existe des entiers \(u,v\) tels que

Démonstration : Suivre les coefficients dans Euclide

Supposons d’abord \(a,b>0\). Au départ, \(a=1a+0b\) et \(b=0a+1b\) sont des combinaisons entières. Si deux restes successifs s’écrivent \(R=au+bv\) et \(S=au'+bv'\), le reste suivant, pour un quotient entier \(q\), est

Pour des entiers non nuls de signes quelconques, appliquer le raisonnement à \(|a|,|b|\) puis réintroduire leurs signes dans les coefficients. Si \(b=0\) et \(a\ne0\), l’identité \(|a|=(\pm1)a+0b\) convient, avec le signe de \(a\) ; si \(a=0\) et \(b\ne0\), on échange les rôles.

Méthode : Trouver les coefficients par remontée

Effectuer Euclide en conservant ses divisions. Partir de la ligne qui produit le PGCD non nul, isoler ce reste puis remplacer successivement les restes antérieurs. Regrouper seulement lorsque les deux nombres de départ sont retrouvés. Vérifier l’identité finale par un calcul direct. Si une entrée est nulle ou si la première division est exacte, les coefficients sont immédiats : utiliser les écritures de départ, comme dans la preuve précédente.

Exemple expliqué : Remonter les divisions de 187 par 119

Les divisions de la section 2 donnent \(\operatorname{PGCD}(187,119)=17\).

Théorème : Critère de Bézout

Pour deux entiers \(a,b\) non tous deux nuls,

Démonstration : Une équivalence

Si le PGCD vaut \(1\), l’identité de Bézout donne le couple cherché. Réciproquement, si \(au+bv=1\) avec \(u,v\) entiers, tout diviseur commun positif de \(a,b\) divise \(1\) ; le PGCD vaut donc \(1\).

Piège à éviter : Les coefficients doivent être entiers

\(6\times\frac16+10\times0=1\) ne prouve pas la coprimalité de \(6\) et \(10\) : \(1/6\notin\mathbb{Z}\), et leur PGCD est \(2\).

Caractérisation : Certifier un PGCD quelconque

Pour \((a,b)\ne(0,0)\) et un entier \(d>0\),

Démonstration : Diviseur commun et combinaison

Le sens direct réunit la définition du PGCD et Bézout. Réciproquement, soit \(g=\operatorname{PGCD}(a,b)\). Comme \(d\) est un diviseur commun positif, \(d\le g\). Comme \(g\) divise la combinaison \(au+bv=d>0\), on a \(g\le d\). Ainsi \(g=d\).

Exemple expliqué : Un certificat complet

\(84=12\times7\), \(132=12\times11\) et \(-3\times84+2\times132=-252+264=12\). Les deux divisibilités et l’identité prouvent \(\operatorname{PGCD}(84,132)=12\). En revanche \(2\times30-42=18\) ne prouve pas que le PGCD de \(30\) et \(42\) vaut \(18\) : \(18\) ne divise pas \(30\).

Propriété : Multiplier ou réduire les deux nombres

Si \((a,b)\ne(0,0)\) et \(k\in\mathbb{Z}\setminus\{0\}\), alors

Démonstration : Appliquer le certificat

Posons \(g=\operatorname{PGCD}(a,b)\). Pour \(k>0\), \(kg\) divise \(ka\) et \(kb\). Une identité \(au+bv=g\) donne \((ka)u+(kb)v=kg\) : le certificat prouve la formule. Pour \(k<0\), les signes ne changent pas le PGCD et l’on applique le cas positif à \(|k|\). Le second résultat s’obtient avec \(a=dA,b=dB\) : \(\operatorname{PGCD}(a,b)=d\operatorname{PGCD}(A,B)\).

Méthode : Un PGCD dépend d’un entier \(n\)

Chercher une combinaison qui élimine \(n\) et donne une constante non nulle. Le PGCD divise alors cette constante. Si elle vaut \(1\) ou \(-1\), la coprimalité est prouvée ; sinon, dresser les valeurs possibles et déterminer quand chacune convient, avec une réciproque. Une combinaison égale à \(0\) n’offre aucune liste finie de diviseurs possibles.

Exemple expliqué : Une combinaison égale à 1

Pour tout \(n\in\mathbb{Z}\),

Exemple expliqué : Des valeurs possibles à la réponse complète

Posons \(a=4n+1\), \(b=6n+5\) et \(d=\operatorname{PGCD}(a,b)\). La combinaison \(3a-2b=12n+3-12n-10=-7\) montre que le couple n’est pas nul et que \(d\mid7\). Ainsi \(d\in\{1,7\}\).

Si \(d=7\), alors \(7\mid a\) et \(7\mid\bigl(2a-7(n+1)\bigr)=n-5\) : \(n=7k+5\) pour un entier \(k\). Réciproquement, pour \(n=7k+5\),

Théorème : Gauss

Soient \(a,b,c\in\mathbb{Z}\) avec \(a\ne0\). Si

Démonstration : Multiplier une identité de Bézout

La coprimalité fournit \(u,v\in\mathbb{Z}\) tels que \(au+bv=1\). Puisque \(a\mid bc\), écrivons \(bc=ak\) avec \(k\in\mathbb{Z}\). En multipliant l’identité par \(c\),

Méthode : Retirer un facteur d’une divisibilité

Repérer le diviseur, le facteur à retirer et le facteur restant. Vérifier d’abord la coprimalité du diviseur avec le facteur retiré. Appliquer Gauss, puis contrôler que la conclusion porte sur le bon facteur.

Exemple expliqué : Résoudre \(21\mid8m\), avec \(m\in\mathbb{Z}\)

L’identité \(-3\times21+8\times8=-63+64=1\) prouve que \(21\) et \(8\) sont premiers entre eux. Si \(21\mid8m\), Gauss donne \(21\mid m\), donc \(m=21k\), \(k\in\mathbb{Z}\). Réciproquement, \(m=21k\) donne \(8m=21(8k)\). Les solutions sont exactement les multiples de \(21\).

Piège à éviter : La coprimalité n’est pas facultative

\(6\mid4\times3\), mais \(6\nmid3\). Ici \(\operatorname{PGCD}(6,4)=2\) : on ne peut pas appliquer Gauss pour retirer \(4\). Le fait que \(4\) soit non nul ne suffit pas.

Corollaire : Être divisible par deux nombres premiers entre eux

Si \(a,b\in\mathbb{Z}\setminus\{0\}\) sont premiers entre eux, alors, pour \(N\in\mathbb{Z}\),

Démonstration : Gauss dans un sens, transitivité dans l’autre

Si \(N=ak\) et \(b\mid N\), alors \(b\mid ak\). Comme \(\operatorname{PGCD}(b,a)=1\), Gauss donne \(b\mid k\), donc \(k=b\ell\) et \(N=ab\ell\). Réciproquement, \(N=ab\ell\) est multiple de \(a\) et de \(b\).

Exemple expliqué : Multiplier les diviseurs seulement après vérification

Puisque \(25-2\times12=1\), les entiers \(12\) et \(25\) sont premiers entre eux. Un entier est divisible par \(12\) et par \(25\) si et seulement s’il est divisible par \(300\). En revanche \(4\) et \(6\) divisent \(12\), mais leur produit \(24\) ne divise pas \(12\).

Définition : Fraction irréductible

Une fraction \(p/q\), avec \(p\in\mathbb{Z}\) et \(q\in\mathbb{N}^*\), est irréductible lorsque \(p\) et \(q\) n’ont pas de diviseur positif commun supérieur à \(1\). Cela équivaut à \(\operatorname{PGCD}(p,q)=1\).

Proposition : Réduire une fraction en une seule étape

Si \(d=\operatorname{PGCD}(p,q)\), avec \(q>0\), alors

Démonstration : Réutiliser le couple réduit

Comme \(d>0\) divise \(p,q\), les quotients sont entiers et \(q/d>0\). Ils sont premiers entre eux par la propriété du couple réduit. Diviser les deux termes par le même nombre non nul conserve la valeur de la fraction. Si \(p=0\), alors \(d=q\) et l’on obtient \(0/1\).

Définition : Ce que l’on cherche

Une équation diophantienne est une équation dont on recherche les solutions entières. Ici, \(a,b,c\in\mathbb{Z}\) sont fixés et l’on cherche tous les couples \((x,y)\in\mathbb{Z}^2\) vérifiant \(ax+by=c\).

Théorème : Condition d’existence

Si \((a,b)\ne(0,0)\) et \(d=\operatorname{PGCD}(a,b)\), alors

Démonstration : Une condition nécessaire et suffisante

Nécessité. Si \(ax+by=c\), le diviseur commun \(d\) divise la combinaison \(c\).

Suffisance. Bézout fournit \(u,v\in\mathbb{Z}\) tels que \(au+bv=d\). Si \(c=dh\) avec \(h\in\mathbb{Z}\), multiplier cette identité par \(h\) donne \(a(hu)+b(hv)=c\). Le couple \((hu,hv)\) est une solution.

Exemple expliqué : Existence et solution particulière de \(28x+44y=12\)

Pour résoudre \(28x+44y=12\) dans \(\mathbb{Z}^2\), Euclide donne

Théorème : Toutes les solutions, lorsque les deux coefficients sont non nuls

Soient \(a,b\in\mathbb{Z}\setminus\{0\}\), \(c\in\mathbb{Z}\) et \(d=\operatorname{PGCD}(a,b)\). Si \((x_0,y_0)\) est une solution entière de \(ax+by=c\), toutes les solutions entières sont

Démonstration : Nécessité, puis réciproque

Posons \(A=a/d\) et \(B=b/d\). Ils sont entiers, non nuls et premiers entre eux. Si \((x,y)\) est une solution, soustraire \(ax_0+by_0=c\) de \(ax+by=c\) donne

Réciproquement, pour tout entier \(k\),

Exemple expliqué : La famille complète pour \(28x+44y=12\)

Avec \(d=4\), \(A=7\), \(B=11\) et \((x_0,y_0)=(2,-1)\), les solutions sont

Méthode : Organiser une résolution complète

Pour \(a,b\) non nuls, suivre les étapes ci-dessous. Si un coefficient est nul, utiliser directement les cas du tableau suivant.

1. Identifier le domaine, puis calculer \(d=\operatorname{PGCD}(a,b)\).

2. Si \(d\nmid c\), conclure à l’absence de solution entière.

3. Sinon, trouver une particulière (par Bézout ou par un essai vérifié).

4. Écrire la famille avec les pas \(b/d\) et \(-a/d\) et un même entier \(k\).

5. Justifier qu’elle contient toutes les solutions et vérifier la réciproque.

6. Imposer ensuite les bornes du contexte, s’il y en a.

Si \(c=0\), le couple \((0,0)\) fournit immédiatement une particulière.

Propriété : Cas des coefficients nuls

Les cas suivants se traitent directement, sans diviser par zéro :

Démonstration : L’inconnue absente est libre

Si \(a=0\), l’équation devient \(by=c\) : \(y=c/b\) est entier exactement si \(b\mid c\), et \(x\) n’intervient plus. Le deuxième cas échange les rôles. Lorsque \(a=b=0\), l’équation devient \(0=c\) ; aucun calcul de \(\operatorname{PGCD}(0,0)\) n’est nécessaire.

Exemple expliqué : Des contraintes naturelles : deux formats de boîtes

On range \(330\) marqueurs dans des boîtes de \(14\) ou de \(22\), entièrement remplies. Si \(x\) et \(y\) comptent respectivement ces boîtes, on cherche \(14x+22y=330\) avec \(x,y\in\mathbb{N}\).

Euclide donne \(22=14+8\), \(14=8+6\), \(8=6+2\), \(6=3\times2\) : le PGCD vaut \(2\). Après réduction, \(7x+11y=165\) admet la particulière \((0,15)\). Toutes les solutions entières sont donc

Lecture. La droite représente les solutions réelles ; les trois points marqués sont les solutions entières non négatives, déterminées par le paramètre. Le pas est \((+11,-7)\). La figure illustre l’exhaustivité, elle ne la prouve pas.

Si l’on exige au moins une boîte de chaque format, ajouter \(x\ge1\) et \(y\ge1\) : \((0,15)\) est exclu, les deux autres couples restent.

Définition : Rappel : congruence modulo un entier

Pour \(n\ge2\) et \(s,t\in\mathbb{Z}\), on écrit \(s\equiv t\;[n]\) si \(n\mid(s-t)\). Cela équivaut à dire que \(s\) et \(t\) ont le même reste dans la division euclidienne par \(n\). L’écriture \(x\equiv r\;[n]\) décrit tous les entiers \(x=r+nk\), \(k\in\mathbb{Z}\).

Définition : Inverse modulo \(n\)

Un entier \(u\) est un inverse de \(a\) modulo \(n\) lorsque \(au\equiv1\;[n]\). Il ne s’agit pas du nombre réel \(1/a\).

Théorème : Existence et unicité modulo \(n\) de l’inverse

Pour \(a\in\mathbb{Z}\) et \(n\ge2\), un inverse de \(a\) modulo \(n\) existe si et seulement si \(\operatorname{PGCD}(a,n)=1\). Dans ce cas, il est unique modulo \(n\), donc possède un unique représentant dans \(\{0,1,\ldots,n-1\}\).

Démonstration : Bézout donne l’existence ; Gauss donne l’unicité

Si \(\operatorname{PGCD}(a,n)=1\), Bézout donne \(au+nv=1\) : \(au-1=-nv\) est multiple de \(n\), donc \(u\) est un inverse. Réciproquement, si \(au\equiv1\;[n]\), il existe \(k\in\mathbb{Z}\) tel que \(au-1=nk\). L’identité \(au+n(-k)=1\) prouve la coprimalité par Bézout.

Si \(u,v\) sont deux inverses, alors \(n\mid a(u-v)\). Comme \(\operatorname{PGCD}(n,a)=1\), Gauss donne \(n\mid(u-v)\) : \(u\equiv v\;[n]\). L’unicité du reste euclidien donne celle du représentant annoncé.

Méthode : Calculer un inverse

Effectuer Euclide sur \(a,n\). Si leur PGCD est \(1\), remonter jusqu’à \(au+nv=1\) ; le coefficient de \(a\) est l’inverse cherché. Le réduire modulo \(n\) si nécessaire, puis contrôler \(au-1\).

Exemple expliqué : Un inverse de 17 modulo 43

Pour inverser 17 modulo 43 : \(43=2\times17+9\), \(17=9+8\), \(9=8+1\).

Proposition : Simplifier un facteur à module inchangé

Si \(n\ge2\) et \(\operatorname{PGCD}(k,n)=1\), alors, pour \(s,t\in\mathbb{Z}\),

Démonstration : La condition qui autorise la simplification

Le sens direct signifie \(n\mid k(s-t)\) ; Gauss donne \(n\mid(s-t)\). Réciproquement, tout multiple de \(n\) reste multiple de \(n\) après multiplication par \(k\).

Piège à éviter : Un facteur non nul ne suffit pas

\(2\times1\equiv2\times4\;[6]\), puisque \(2-8=-6\). Pourtant \(1\not\equiv4\;[6]\). On a \(\operatorname{PGCD}(2,6)=2\), et non \(1\). La conclusion correcte après division est \(1\equiv4\;[3]\) : le module change.

Exemple expliqué : Une congruence à coefficient inversible

Résolvons \(17x\equiv9\;[43]\). Multiplier par l’inverse \(38\) donne

Propriété : Diviser aussi le module

Si \(d>0\) divise \(s,t,n\), alors

Démonstration : Diviser une égalité, et non effacer un facteur

La congruence de départ signifie \(s-t=nq\) pour un entier \(q\). Diviser par \(d\ne0\) donne \(s/d-t/d=(n/d)q\) ; multiplier par \(d\) prouve la réciproque.

Théorème : Résoudre \(ax\equiv b\;[n]\) dans le cas général

Soient \(a,b\in\mathbb{Z}\), \(n\ge2\) et \(d=\operatorname{PGCD}(a,n)\).

• Si \(d\nmid b\), il n’y a aucune solution entière.

• Si \(d\mid b\), poser \(A=a/d\), \(B=b/d\), \(N=n/d\). Si \(N\ge2\), on a \(\operatorname{PGCD}(A,N)=1\) ; avec un inverse \(u\) de \(A\) modulo \(N\),

  \[ax\equiv b\;[n]\quad\Longleftrightarrow\quad x\equiv uB\;[N].\]

• Si \(N=1\) et \(d\mid b\), tous les entiers conviennent ; on ne cherche pas d’inverse modulo \(1\).

Ainsi une solution existe si et seulement si \(d\mid b\).

Démonstration : Obstruction, réduction et construction

Si \(ax-b=nq\), alors \(b=ax-nq\) est une combinaison de \(a,n\) : \(d\) divise \(b\). Réciproquement, si \(b=dh\), une identité \(a\alpha+n\beta=d\) multipliée par \(h\) montre que \(x=h\alpha\) convient.

Pour décrire toutes les solutions, diviser \(ax-b=nq\) par \(d>0\) donne \(Ax-B=Nq\), donc \(Ax\equiv B\;[N]\). Le couple \((A,N)\) est obtenu en divisant \((a,n)\) par leur PGCD \(d\) : les deux entiers sont donc premiers entre eux. Si \(N\ge2\), multiplier par \(u\) donne \(x\equiv uB\;[N]\) ; la réciproque s’obtient en multipliant par \(A\). Si \(N=1\), alors \(d=n\) et \(n\) divise \(a\) et \(b\) : \(ax-b\) est multiple de \(n\) pour tout entier \(x\).

Corollaire : Représentants dans le module initial

Dans le cas soluble avec \(N\ge2\), soit \(r\) le reste de \(uB\) modulo \(N\). Toutes les solutions sont \(r+Nk\), \(k\in\mathbb{Z}\). Modulo \(n=dN\), elles donnent exactement \(d\) représentants dans \(\{0,\ldots,n-1\}\) :

Démonstration : Pourquoi la liste est complète et sans doublon

Écrire \(k=dh+j\), avec \(0\le j<d\), donne \(r+Nk=(r+jN)+nh\). La liste est donc complète. Ses termes sont compris entre \(0\) et \(n-1\). Si deux termes sont congrus modulo \(n\), alors \(n\mid N(i-j)\), donc \(d\mid(i-j)\) ; comme \(|i-j|<d\), on a \(i=j\).

Méthode : L’ordre des décisions

Calculer le PGCD du coefficient et du module ; vérifier qu’il divise le second membre ; réduire les trois nombres ; inverser le coefficient réduit si le module réduit est au moins \(2\) ; écrire toutes les solutions ; contrôler dans la congruence initiale.

Exemple expliqué : Un coefficient qui n’est pas inversible au départ

Résolvons \(18x\equiv30\;[42]\). On a \(42=2\times18+6\), \(18=3\times6\), donc \(d=6\), et \(6\mid30\).

Remarque : Coefficient nul

Pour \(0x\equiv b\;[n]\), tous les entiers sont solutions si \(n\mid b\), aucun sinon. C’est bien le critère précédent, puisque \(\operatorname{PGCD}(0,n)=n\).

Définition : Chiffrement affine

On associe les lettres A, B, …, Z aux rangs \(0,1,\ldots,25\). Pour une clé \((a,b)\in\mathbb{Z}^2\), le rang \(x\) est remplacé par le rang \(y\) défini par

Théorème : Quand le déchiffrement est-il unique ?

Le chiffrement affine permet de retrouver chaque lettre de façon unique si et seulement si \(\operatorname{PGCD}(a,26)=1\). Avec un inverse \(u\) de \(a\) modulo \(26\),

Démonstration : Un inverse, ou deux lettres confondues

Si \(\operatorname{PGCD}(a,26)=1\), les règles sur l’inverse donnent l’équivalence \(y\equiv ax+b\;[26]\Longleftrightarrow x\equiv u(y-b)\;[26]\). Une classe de congruence possède un unique rang entre \(0\) et \(25\).

Si \(d=\operatorname{PGCD}(a,26)>1\), les rangs \(0\) et \(26/d\) sont distincts et compris entre \(0\) et \(25\), mais leurs images diffèrent de \(a(26/d)=26(a/d)\), multiple de \(26\). Ils donnent la même lettre chiffrée : le retour n’est donc pas unique.

Exemple expliqué : Clé \((7,4)\) : MATH devient KEHB

\(7\times15=105=4\times26+1\) : l’inverse de \(7\) est \(15\) modulo \(26\). Le déchiffrement s’écrit donc \(x\equiv15(y-4)\;[26]\).

Pour décoder les rangs \(10,4,7,1\), calculer les restes modulo \(26\) :

Algorithme : Calcul du PGCD

def pgcd_euclide(a, b):
    if a == 0 and b == 0:
        raise ValueError("Deux entiers non tous nuls attendus")
    A = abs(a)
    B = abs(b)
    while B != 0:
        R = A % B
        A = B
        B = R
    return A

Démonstration : Invariant et arrêt

Avant chaque tour, \(\operatorname{PGCD}(A,B)=\operatorname{PGCD}(a,b)\) : c’est vrai à l’initialisation par la règle des signes, puis conservé par le lemme d’Euclide. Le calcul du reste se fait seulement lorsque \(B\ne0\) et donne \(0\le R<B\). Le nouveau \(B\) diminue donc strictement tant qu’il n’est pas nul. À l’arrêt \(B=0\), et le \(A>0\) renvoyé est le PGCD.

Piège à éviter : Ne pas écraser une ancienne valeur

Le reste R doit être calculé avant l’affectation A = B. Sinon l’ancien dividende est perdu. Une variable temporaire garde l’état nécessaire.

Algorithme : Euclide étendu : renvoyer \((d,u,v)\)

On conserve simultanément les identités \(A=ua+vb\) et \(B=sa+tb\).

def bezout_euclide(a, b):
    if a == 0 and b == 0:
        raise ValueError("Deux entiers non tous nuls attendus")
    A, B = abs(a), abs(b)
    u = 1 if a >= 0 else -1
    v = 0
    s = 0
    t = 1 if b >= 0 else -1
    while B != 0:
        q = A // B
        R = A - q * B
        U = u - q * s
        V = v - q * t
        A, B = B, R
        u, s = s, U
        v, t = t, V
    return A, u, v

Proposition : Garantie de l’algorithme étendu

Pour les entrées prévues, le programme termine et renvoie \((d,u,v)\) avec \(d=\operatorname{PGCD}(a,b)>0\) et \(au+bv=d\).

Démonstration : Conserver les deux identités

Initialisation. Le signe choisi pour \(u\) assure \(ua=|a|\), et \(v=0\) ; le signe de \(t\) assure \(tb=|b|\), et \(s=0\). Ainsi \(A=ua+vb\) et \(B=sa+tb\).

Un tour. Si ces deux identités sont vraies, le nouveau reste vaut

Arrêt. Les nombres \(A,B\) suivent Euclide : leur PGCD est conservé et \(B\) devient nul après un nombre fini de tours. Alors \(A=d\) et \(A=ua+vb\) fournit l’identité renvoyée, avec les entrées signées d’origine.

Exemple expliqué : Lire les états pour \(a=323\), \(b=187\)

Les colonnes sont liées par \(A=323u+187v\) et \(B=323s+187t\).

De l’étape 2 à l’étape 3, \(q=2\) :

Ne pas renvoyer \(s,t\) à la fin : ils décrivent le reste nul, \(11\times323-19\times187=3553-3553=0\). Si un argument est nul, l’initialisation et la même logique traitent le cas ; seule l’entrée \((0,0)\) est rejetée.

À retenir : Les conditions font partie des résultats

PGCD et Euclide. Pour \((a,b)\ne(0,0)\), \(d=\operatorname{PGCD}(a,b)>0\). Les signes ne changent pas le PGCD ; si \(a\ne0\), \(\operatorname{PGCD}(a,0)=|a|\). Les diviseurs communs sont exactement les diviseurs de \(d\). Euclide conserve ces diviseurs ; le diviseur de la dernière division donne \(d\).

Bézout. Il existe \(u,v\in\mathbb{Z}\) tels que \(au+bv=d\). En particulier, \(a,b\) sont premiers entre eux si et seulement si une combinaison entière vaut \(1\). Pour certifier un PGCD \(d>1\), vérifier aussi \(d\mid a\) et \(d\mid b\).

Gauss. Si \(a\ne0\), \(a\mid bc\) et \(\operatorname{PGCD}(a,b)=1\), alors \(a\mid c\). Si \(a,b\ne0\) sont premiers entre eux et divisent \(N\), alors \(ab\mid N\).

Équation entière. Pour \((a,b)\ne(0,0)\), \(ax+by=c\) admet des solutions entières si et seulement si \(\operatorname{PGCD}(a,b)\mid c\). Si \(a,b\ne0\), à partir d’une particulière \((x_0,y_0)\) et de \(d=\operatorname{PGCD}(a,b)\) :

Congruence. Pour \(n\ge2\), \(a\) est inversible modulo \(n\) exactement si \(\operatorname{PGCD}(a,n)=1\). Pour \(ax\equiv b\;[n]\), calculer \(d=\operatorname{PGCD}(a,n)\). Si \(d\nmid b\), aucune solution ; sinon réduire \(a,b,n\) par \(d\). Le coefficient réduit devient inversible si \(n/d\ge2\). Si \(n/d=1\), tous les entiers conviennent. Toujours vérifier dans le module initial.

Méthode : Reconnaître la forme, vérifier, agir