PGCD, Bézout et Gauss · Terminale maths expertes

Avant de commencer5 questions pour vérifier tes bases

Pourquoi ce chapitre ?

Le problème fondamental : quels nombres peut-on fabriquer ?

Avec des combinaisons entières de 6 et 10, tu peux fabriquer $$4=10-6$$ et $2=2\times6-10$ , mais jamais 3 : chaque combinaison est paire. Le PGCD va préciser cette obstruction. Bézout montrera ensuite qu'elle est la seule obstruction pour une équation $$ax+by=c$$ dans les entiers.

Prérequis. Divisibilité, combinaison linéaire entière, division euclidienne et congruences de la fiche 4. Pour les divisions de l'algorithme, les restes sont positifs ou nuls.

Ces notions appartiennent au socle. Le PPCM et le théorème chinois final sont des prolongements construits à partir de Bézout et Gauss.

L'idée avant la formule

Pourquoi remplacer une paire par une autre ?

Les diviseurs communs de 84 et 30 divisent aussi $84-2\times30=24$ . Inversement, ceux de 30 et 24 divisent $2\times30+24=84$ . Les paires $$(84,30)$$ et $$(30,24)$$ ont donc exactement les mêmes diviseurs communs. La seconde paire est plus petite : on a progressé sans perdre l'information cherchée.

Le calcul peut se lire dans les deux sens

Les divisions suivantes conduisent à $$30=24+6$$ , puis $24=4\times6$ . Le PGCD est 6. Relis maintenant à l'envers :

\begin{aligned}6 &= 30-24\\[.35em] &= 30-(84-2\times30)\\[.35em] &= 3\times30-84.\end{aligned}

Cette égalité indique les coefficients qui fabriquent le PGCD. Les signes négatifs sont autorisés, puisque l'on travaille dans $\Z$ .

Une solution n'est pas toutes les solutions

Si $$3x+5y=1$$ , le couple $$(2,-1)$$ convient. En ajoutant 5 à x et en retirant 3 à y, la somme reste inchangée : on ajoute 15 puis on enlève 15. Le paramètre entier décrira ces déplacements. Gauss permettra de prouver qu'ils couvrent toutes les solutions, et pas seulement une famille commode.

Le cours formel

PGCD et entiers premiers entre eux

Deux entiers sont premiers entre eux lorsque leur PGCD vaut 1. Cela ne signifie pas qu'ils sont chacun premiers : 8 et 15 sont premiers entre eux bien que chacun soit composé.

À toi d’essayer

Premiers entre eux ne veut pas dire premiers

8 et 9 sont-ils premiers entre eux ? Et 8 et 12 ? Donne un diviseur commun maximal dans chaque cas.

Pour démarrer. Compare les diviseurs positifs, et non le fait que chaque nombre soit premier ou composé.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Liste les diviseurs positifs de 8.

Indice 2 · Un pas de plus

Compare les listes, pas seulement la parité.

Voir l’explication

Les diviseurs positifs de 8 sont $$1,2,4,8$$ ; ceux de 9 sont $$1,3,9$$ . Leur seule valeur commune est 1, donc leur PGCD vaut 1 : 8 et 9 sont premiers entre eux. Ceux de 12 sont $$1,2,3,4,6,12$$ . Avec 8, les valeurs communes sont $$1,2,4$$ , donc le PGCD vaut 4. Les nombres 8 et 9 sont pourtant composés, puisqu'ils ont des diviseurs autres que 1 et eux-mêmes. « Premiers entre eux » est une relation entre deux nombres, pas une propriété individuelle de chacun.

Algorithme d'Euclide et invariant des diviseurs

La procédure s'arrête : les restes non nuls forment une suite strictement décroissante d'entiers naturels. À la dernière étape, le PGCD de $$(r,0)$$ vaut $$r$$ ; l'invariance prouve que c'est le PGCD initial.

À toi d’essayer

Lire la dernière ligne

Calcule le PGCD de 84 et 30.

Pour démarrer. À chaque étape, le diviseur et le reste deviennent le nouveau couple.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Commence par $84=2\times30+24$ .

Indice 2 · Un pas de plus

Puis divise 30 par 24, et 24 par le nouveau reste.

Voir l’explication

$84=2\times30+24$ , donc le PGCD est celui de 30 et 24. Puis $30=1\times24+6$ , donc celui de 24 et 6. Enfin $24=4\times6+0$ , donc celui de 6 et 0, égal à 6. Les restes étaient $$24,6,0$$ ; le dernier non nul est 6. Vérification : $84=6\times14$ et $30=6\times5$ . Les diviseurs communs sont tous les diviseurs de 6, soit $$1,2,3,6$$ si on les demande positifs ; le PGCD ne désigne que le plus grand.

Remonter Euclide et démontrer Bézout

Démonstration · Existence et caractérisation

Construire la combinaison. Pour des nombres positifs, les deux nombres de départ s'écrivent $$a=1a+0b$$ et $$b=0a+1b$$ . Supposons que deux nombres successifs d'Euclide s'écrivent $$r=au+bv$$ et $$s=au'+bv'$$ . Le reste suivant est $$r-qs$$ , donc

\[r-qs=a(u-qu')+b(v-qv').\]

Les nouveaux coefficients sont entiers puisque tous les coefficients précédents et le quotient $$q$$ le sont. Cette propriété est vraie au départ et se conserve à chaque division. Le dernier reste non nul $$d$$ est donc encore une combinaison $$au+bv$$ : c'est l'identité annoncée.

Si un entier initial est négatif, l'algorithme travaille sur sa valeur absolue ; on change ensuite le signe de son coefficient pour réécrire l'identité avec l'entier initial. Si l'un est nul, par exemple $b=0,a\ne0$ , $$d=|a|$$ s'écrit $$a$$ ou $$-a$$ selon son signe.

Caractériser le PGCD 1. Si le PGCD vaut 1, l'identité construite fournit $$au+bv=1$$ . Inversement, supposons une telle identité connue. Tout diviseur commun positif $$h$$ divise $$a$$ et $$b$$ , donc la combinaison $$au+bv=1$$ . Le seul diviseur positif de 1 est 1 ; ainsi tous les diviseurs communs positifs se réduisent à 1, et le PGCD vaut 1. Nous avons prouvé les deux directions.

Démonstration · Conséquences de Bézout

Notons $d=\gcd(a,b)>0$ et choisissons $$u,v$$ tels que $$au+bv=d$$ . Si $$h$$ divise $$a$$ et $$b$$ , il divise toute combinaison entière, donc il divise $$d$$ . Réciproquement, $$d$$ divise $$a$$ et $$b$$ par définition ; si $$h$$ divise $$d$$ , la transitivité montre que $$h$$ divise aussi $$a$$ et $$b$$ . Les diviseurs de $$d$$ sont donc exactement les diviseurs communs.

Divisons maintenant l'identité de Bézout par $$d$$ , non nul : $$(a/d)u+(b/d)v=1$$ . Les nombres $$a/d$$ et $$b/d$$ sont entiers parce que $$d$$ les divise. Ils possèdent une combinaison entière égale à 1 ; la caractérisation de Bézout prouve donc qu'ils sont premiers entre eux. Il ne s'agit pas simplement de dire qu'ils sont « plus petits » : c'est l'identité égale à 1 qui justifie leur coprimalité.

À toi d’essayer

Fabriquer le 1 qui permet de simplifier

À partir de $17=2\times7+3$ et $7=2\times3+1$ , écris 1 comme combinaison de 17 et 7.

Pour démarrer. Isole 1 dans la dernière division, puis remplace 3 avec la première.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Isole le dernier reste non nul.

Indice 2 · Un pas de plus

Remplace 3 dans $1=7-2\times3$ .

Voir l’explication

La seconde division donne $1=7-2\times3$ . La première donne $3=17-2\times7$ . Substituer en conservant les parenthèses donne

\begin{aligned}1 &= 7-2(17-2\times7)\\[.35em] &= 7-2\times17+4\times7\\[.35em] &= 5\times7-2\times17.\end{aligned}

Vérification : $$35-34=1$$ . Les coefficients de 17 et 7 sont respectivement $$-2$$ et 5. Cette identité prouve leur coprimalité, car tout diviseur commun diviserait 1. Elle fournit aussi l'inverse 5 de 7 modulo 17.

Le théorème de Gauss

Une preuve à construire

Construire la simplification

Si $7\mid3n$ , démontre $7\mid n$ sans utiliser directement le nom du théorème.

Pour démarrer. Multiplie l’égalité $1=7-2\times3$ par $$n$$ , puis utilise l’hypothèse.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Cherche une combinaison de 7 et 3 égale à 1.

Indice 2 · Un pas de plus

Utilise $1=7-2\times3$ , puis multiplie par n.

Voir la preuve expliquée

L'hypothèse signifie $$3n=7k$$ pour un entier $$k$$ . Puisque $7-2\times3=1$ , multiplier par $$n$$ donne $$n=7n-2(3n)$$ . Remplaçons $$3n$$ par $$7k$$ :

\begin{aligned}n &= 7n-14k\\[.35em] &= 7(n-2k).\end{aligned}

Le nombre $$n-2k$$ est entier, donc 7 divise $$n$$ . Le calcul montre le quotient entier qui justifie la conclusion ; il ne se contente pas de supprimer le facteur 3 dans la divisibilité initiale.

À toi d’essayer

Vérifier avant de supprimer un facteur

Si $15\mid4n$ , que peux-tu conclure ? Pourquoi le même raisonnement ne donne-t-il pas $15\mid n$ à partir de $15\mid5n$ ?

Pour démarrer. Vérifie le PGCD avant d’invoquer Gauss et cherche un contre-exemple lorsque l’hypothèse échoue.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Compare les PGCD de 15 avec 4 puis avec 5.

Indice 2 · Un pas de plus

Pour réfuter la seconde implication, cherche un petit n.

Voir l’explication

Les diviseurs de 15 sont $$1,3,5,15$$ ; aucun sauf 1 ne divise 4, donc $\gcd(15,4)=1$ . Gauss donne $15\mid n$ à partir de $15\mid4n$ . On peut voir l'identité $1=4\times4-15$ , donc $$n=4(4n)-15n$$ , multiple de 15. Avec le facteur 5, le PGCD vaut 5 et non 1. Pour $$n=3$$ , $$5n=15$$ est divisible par 15, mais $$n=3$$ ne l'est pas. Cet exemple prouve que la seconde implication est fausse.

Inverses et congruences linéaires

Démonstration · Existence et unicité

Nécessité. Si $$u$$ est un inverse de $$a$$ modulo $$n$$ , $au\equiv1$ signifie $$au-1=nk$$ pour un entier $$k$$ . Réarrangeons : $$au+n(-k)=1$$ . C'est une identité de Bézout pour $$a,n$$ , donc $\gcd(a,n)=1$ .

Suffisance. Si $\gcd(a,n)=1$ , Bézout fournit $$au+nv=1$$ . Modulo $$n$$ , le terme $$nv$$ disparaît car c'est un multiple de $$n$$ ; il reste $au\equiv1$ . Le coefficient $$u$$ est donc un inverse.

Unicité modulo $$n$$ . Si $$u$$ et $$v$$ sont deux inverses, $$au-1$$ et $$av-1$$ sont multiples de $$n$$ . Leur différence $$a(u-v)$$ l'est aussi. Comme $\gcd(n,a)=1$ , Gauss donne $n\mid(u-v)$ , soit $u\equiv v\pmod n$ . Les inverses peuvent être des entiers différents, mais ont tous le même reste : par exemple $$-5$$ et 38 représentent le même inverse modulo 43.

Démonstration · Pourquoi le module change

La congruence $ax\equiv b\pmod n$ signifie qu'il existe un entier $$y$$ tel que $$ax-ny=b$$ . Posons $d=\gcd(a,n)$ . Puisque $$d$$ divise $$a$$ et $$n$$ , il divise le membre gauche pour tous entiers $$x,y$$ . Donc $d\mid b$ est nécessaire ; si cette condition échoue, nous arrêtons : aucune solution.

Si $d\mid b$ , écrivons $$a=da'$$ , $$n=dn'$$ et $$b=db'$$ . L'égalité devient $$d(a'x-n'y)=db'$$ . Comme $$d>0$$ , elle équivaut à $$a'x-n'y=b'$$ , donc à $a'x\equiv b'\pmod{n'}$ . Le module est bien devenu $$n/d$$ , car le coefficient de l'entier libre $$y$$ a aussi été divisé.

Les nombres $$a',n'$$ sont premiers entre eux. Si $n'\ge2$ , un inverse fournit une classe $$x=x_0+n'k$$ . Si $$n'=1$$ , tous les entiers conviennent. Dans le premier cas, prenons $k=0,\ldots,d-1$ : les valeurs obtenues représentent $$d$$ classes distinctes modulo $$dn'=n$$ . En effet, deux valeurs diffèrent de $n'(k-\ell)$ , multiple de $$n$$ seulement si $d\mid(k-\ell)$ ; dans cette liste cela impose $k=\ell$ . Les autres $$k$$ répètent ces classes.

Pour $6x\equiv9\pmod{15}$ , le PGCD des deux coefficients 6 et 15 vaut 3, et il divise 9. Diviser l'égalité entière $$6x-15k=9$$ par 3 donne $$2x-5k=3$$ , soit $2x\equiv3\pmod5$ . L'inverse de 2 modulo 5 est 3, car $2\times3=6\equiv1$ . Multiplier par 3 donne $x\equiv9\equiv4\pmod5$ , donc $$x=4+5t$$ . Dans l'intervalle $0\le x<15$ , les valeurs de $$t$$ sont 0,1,2 : les restes sont $$4,9,14$$ . Les produits par 6 valent 24,54,84, tous de reste 9 modulo 15.

À toi d’essayer

Utiliser le bon coefficient de Bézout

Utilise $1=5\times7-2\times17$ pour résoudre $7x\equiv3\pmod{17}$ .

Pour démarrer. Réduis l’identité de Bézout modulo 17 pour savoir quel terme disparaît.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le coefficient placé devant 7 est son inverse modulo 17.

Indice 2 · Un pas de plus

Multiplie les deux membres de la congruence par 5.

Voir l’explication

Dans $1=5\times7-2\times17$ , le second terme est multiple de 17. Il reste $5\times7\equiv1\pmod{17}$ : l'inverse de 7 est donc 5. Multiplier $7x\equiv3$ par 5 donne $x\equiv15\pmod{17}$ . La famille est $$x=15+17k$$ . Pour la contrôler,

\begin{aligned}7x-3 &= 105+119k-3\\[.35em] &= 17(6+7k),\end{aligned}

bien multiple de 17. Le coefficient $$-2$$ accompagne le module ; ce n'est pas l'inverse demandé.

Équations diophantiennes : toutes les solutions

Démonstration · Nécessité, construction, exhaustivité

1. Tester l'existence. Le PGCD $$d$$ divise $$a$$ et $$b$$ , donc toute combinaison $$ax+by$$ . Si $$d$$ ne divise pas $$c$$ , l'équation est impossible. Si $$c=dt$$ , Bézout fournit $$au+bv=d$$ ; multiplier par $$t$$ donne $$a(ut)+b(vt)=c$$ . Le couple $$(x_0,y_0)=(ut,vt)$$ est une solution particulière.

2. Ne pas confondre un couple avec toutes les solutions. Prenons une solution quelconque $$(x,y)$$ et soustrayons $$ax_0+by_0=c$$ : $$a(x-x_0)+b(y-y_0)=0$$ . Posons $$a'=a/d,b'=b/d$$ , premiers entre eux. Après division par $$d$$ , $$a'(x-x_0)=-b'(y-y_0)$$ .

Le membre droit est divisible par $$b'$$ , donc $b'\mid a'(x-x_0)$ . Gauss permet de supprimer $$a'$$ parce que $\gcd(a',b')=1$ : $b'\mid(x-x_0)$ . Écrivons $$x-x_0=b'k$$ avec $k\in\Z$ . En remplaçant, $$a'b'k=-b'(y-y_0)$$ . Comme $b'\ne0$ , on divise par lui : $$y-y_0=-a'k$$ .

3. Vérifier que toute la famille convient. Pour tout entier $$k$$ , substituer $$x=x_0+b'k$$ , $$y=y_0-a'k$$ donne

\begin{aligned}ax+by &= ax_0+by_0+(ab'-ba')k\\[.35em] &= c,\end{aligned}

car

\begin{aligned}ab' &= ba'\\[.35em] &= ab/d.\end{aligned}

Chaque solution figure donc dans la famille, et chaque membre de la famille est solution. Ces deux sens assurent l'exhaustivité.

Si un coefficient est nul, traite l'équation directement. Par exemple $$0x+by=c$$ impose $$y=c/b$$ entier, puis $$x$$ est libre. Si les deux coefficients sont nuls, tout couple convient pour $$c=0$$ , aucun sinon.

À toi d’essayer

Passer d’un couple à tous les couples

Résous $$3x+5y=1$$ dans les entiers, puis impose x et y positifs ou nuls.

Pour démarrer. Soustrais le couple particulier, puis impose les deux inégalités sur le même paramètre.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le couple $$(2,-1)$$ est une solution particulière.

Indice 2 · Un pas de plus

Écris $$x=2+5k$$ et $$y=-1-3k$$ .

Voir l’explication

Le couple $$(2,-1)$$ vérifie $$6-5=1$$ . Pour toute autre solution, $$3(x-2)+5(y+1)=0$$ , donc $5\mid3(x-2)$ . Comme 3 et 5 sont premiers entre eux, $$x-2=5k$$ . Alors $3\times5k+5(y+1)=0$ , donc $$y=-1-3k$$ . Toute la famille $$(2+5k,-1-3k)$$ redonne 1. Pour la positivité, $k\ge-2/5$ impose $k\ge0$ , et $k\le-1/3$ impose $k\le-1$ , car $$k$$ est entier. Ces deux conditions sont incompatibles : aucune solution positive ou nulle.

Euclide étendu et PPCM

def bezout(a, b):
    r0, r1 = abs(a), abs(b)
    u0, u1, v0, v1 = 1, 0, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q*r1
        u0, u1 = u1, u0 - q*u1
        v0, v1 = v1, v0 - q*v1
    return r0, u0*(1 if a >= 0 else -1), v0*(1 if b >= 0 else -1)

Au départ,

\begin{aligned}r_0 &= |a|\\[.35em] &= |a|\times1+|b|\times0\end{aligned}

\begin{aligned}\text{et }r_1 &= |b|\\[.35em] &= |a|\times0+|b|\times1.\end{aligned}

Les deux restes sont donc accompagnés de coefficients qui permettent de les reconstruire à partir des entrées.

Supposons ces deux identités vraies avant un tour. Le nouveau reste est $$r_0-qr_1$$ . En remplaçant chaque reste par sa combinaison, il devient $$|a|(u_0-qu_1)+|b|(v_0-qv_1)$$ . Voilà pourquoi on effectue sur les coefficients exactement la même soustraction que sur les restes. L'ancien reste $$r_1$$ et ses coefficients deviennent la première ligne ; le nouveau reste et ses coefficients deviennent la seconde. Python évalue les membres droits avant les affectations, ce qui conserve les anciennes valeurs pendant le calcul.

Les restes positifs diminuent strictement, donc la boucle s'arrête. À l'arrêt, $$r_1=0$$ et $$r_0=d$$ , le PGCD. On a $$d=|a|u_0+|b|v_0$$ . Si $$a<0$$ , remplacer $$u_0$$ par $$-u_0$$ transforme $$|a|u_0$$ en $$a(-u_0)$$ ; on fait de même pour $$b$$ . Les signes dans le retour assurent donc $$au+bv=d$$ pour les entrées signées. Si les deux entrées sont nulles, la boucle est ignorée et le retour respecte la convention $$d=0$$ .

Posons $d=\gcd(a,b)$ , $$a=da'$$ et $$b=db'$$ . Le cours a prouvé que $$a',b'$$ sont premiers entre eux. Le nombre $$M=da'b'$$ est positif ; il vaut $$ab'$$ et aussi $$ba'$$ , donc est multiple de $$a$$ et de $$b$$ .

Prenons maintenant un multiple commun positif $$m$$ . Comme $a\mid m$ , écrivons $$m=da'k$$ . Comme $b\mid m$ , il existe aussi $\ell$ tel que $m=db'\ell$ . Diviser l'égalité $da'k=db'\ell$ par $$d>0$$ donne $a'k=b'\ell$ , donc $b'\mid a'k$ . Gauss s'applique puisque $\gcd(a',b')=1$ : $b'\mid k$ . Écrivons $$k=b't$$ . Alors

\begin{aligned}m &= da'b't\\[.35em] &= Mt.\end{aligned}

Le nombre $$t$$ est un entier positif puisque $$m,M>0$$ , donc $t\ge1$ et $m\ge M$ . Ainsi $$M$$ est lui-même un multiple commun et aucun multiple commun positif n'est plus petit. Enfin

\begin{aligned}ab/d &= (da')(db')/d\\[.35em] &= da'b'\\[.35em] &= M,\end{aligned}

ce qui prouve la formule.

À toi d’essayer

PGCD ou PPCM selon la question

Deux événements reviennent tous les 12 et 18 jours et ont lieu ensemble aujourd’hui. Quand se reproduiront-ils ensemble pour la première fois ?

Pour démarrer. Le jour recherché doit être un multiple de chacune des deux périodes.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Cherche un multiple commun positif, pas un diviseur.

Indice 2 · Un pas de plus

Le PGCD vaut 6 et le produit vaut 216.

Voir l’explication

Les jours du premier événement sont les multiples de 12 ; ceux du second les multiples de 18. La première rencontre après aujourd'hui est donc le plus petit multiple commun positif. Euclide donne $$18=12+6$$ puis $12=2\times6$ , donc le PGCD vaut 6. Le PPCM vaut $12\times18/6=36$ . Vérification :

\begin{aligned}36 &= 3\times12\\[.35em] &= 2\times18.\end{aligned}

Le jour 6 ne conviendrait pas, car ce n'est un multiple ni de 12 ni de 18 ; le PGCD est utilisé dans le calcul, mais n'est pas la période de rencontre.

Boîte à outils : rendre la solution exhaustive

Trouver tous les couples et imposer une contrainte

Une congruence avec plusieurs classes

Pour $12x\equiv18\pmod{30}$ , le PGCD vaut 6. Comme 6 divise 18, la réduction donne $2x\equiv3\pmod5$ . L'inverse de 2 modulo 5 est 3 : $x\equiv4\pmod5$ . Entre 0 et 29, les solutions sont 4,9,14,19,24,29 : six classes, exactement le PGCD initial.

Pour $12x\equiv17\pmod{30}$ , la condition d'existence échoue puisque 6 ne divise pas 17. Il ne faut pas poursuivre une recherche d'inverse qui ne peut pas résoudre cette équation.

Une méthode pour inverser de grands coefficients

PGCD d'une famille : ne pas s'arrêter aux possibilités

Une combinaison peut montrer qu'un PGCD divise une constante sans déterminer sa valeur. Pour $d=\gcd(n+1,3n-1)$ , la combinaison $$3(n+1)-(3n-1)=4$$ impose $d\mid4$ . Mieux, l'invariance des diviseurs donne $d=\gcd(n+1,4)$ . Ainsi d=1 si n est pair, d=2 si $n\equiv1\pmod4$ , et d=4 si $n\equiv3\pmod4$ . Il faut distinguer les cas pour donner une réponse complète.

À toi d’essayer

Déterminer un PGCD variable

Calcule $\gcd(n,2n+3)$ pour n entier positif.

Pour démarrer. Compare les diviseurs communs avant et après la soustraction $$2n+3-2n$$ .

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Soustrais deux fois n au second terme.

Indice 2 · Un pas de plus

Le PGCD est celui de n et 3.

Voir l’explication

Un diviseur commun à $$n$$ et $$2n+3$$ divise aussi $$2n+3-2n=3$$ . Inversement, un diviseur commun à $$n$$ et 3 divise $$2n+3$$ . Les ensembles de diviseurs communs sont donc identiques et le PGCD est $\gcd(n,3)$ . Comme 3 est premier, il vaut 3 si 3 divise $$n$$ , sinon 1. Ces deux sens sont nécessaires : la seule combinaison montrerait que le PGCD divise 3, sans suffire à conclure dans chaque cas.

Exercices progressifs

Les exercices 1 à 5 consolident les bases, 6 à 10 relient les notions et 11 à 15 demandent davantage d'initiative. Cherche d'abord, puis utilise un indice si tu en as besoin.

Exercice 1 : PGCD et signes ★☆☆

Calcule $\gcd(-18,30)$ , $\gcd(0,27)$ et $\gcd(8,15)$ .

Exercice 2 : Euclide ★☆☆

Calcule $\gcd(414,162)$ .

Exercice 3 : Vérifier Bézout ★☆☆

Vérifie $35\times(-1)+12\times3=1$ . Que peux-tu conclure ? Donne un inverse de 12 modulo 35.

Exercice 4 : Simplifier avec Gauss ★☆☆

Si $9\mid7n$ , prouve que $9\mid n$ .

Exercice 5 : Inverse modulaire ★☆☆

Détermine un inverse de 7 modulo 20 et résous $7x\equiv9\pmod{20}$ .

Exercice 6 : Remonter Euclide ★★☆

Trouve des entiers u,v tels que $$37u+26v=1$$ .

Exercice 7 : Pas de solution ★★☆

Pourquoi $$12x+18y=5$$ n’a-t-elle aucune solution entière ?

Exercice 8 : Toutes les solutions ★★☆

Résous $$7x+5y=1$$ dans $\Z^2$ .

Exercice 9 : Congruence non inversible ★★☆

Résous $8x\equiv12\pmod{20}$ .

Exercice 10 : Combiner des divisibilités ★★☆

Si un entier n est divisible par 8 et par 9, montre qu’il est divisible par 72. L’analogue avec 6 et 9 donne-t-il 54 ?

Exercice 11 : Solutions positives ★★★

Une commande de 100 objets utilise des boîtes de 6 ou de 14 objets. Trouve les couples $(x,y)\in\N^2$ tels que $$6x+14y=100$$ .

Exercice 12 : PGCD dépendant d’un entier ★★★

Pour $n\in\N$ , détermine $\gcd(n+2,2n+1)$ .

Exercice 13 : Une fraction irréductible ★★★

Montre que $$(2n+1)/(3n+2)$$ est irréductible pour tout $n\in\N$ .

Exercice 14 : Une racine rationnelle, prolongement ★★★

Soit $$P(X)=X^3-2X+2$$ . Si $$p/q$$ est une racine rationnelle avec $$q>0$$ et $\gcd(p,q)=1$ , montre que $$q=1$$ et $p\mid2$ . Conclus.

Exercice 15 : Invariant de l’algorithme ★★★

Exécute bezout(30, 18) et explique le rôle des coefficients.

Problème : Pour aller plus loin

Ce prolongement est accessible à partir du cours : les résultats supplémentaires sont guidés, et leur mémorisation n'est pas un préalable. Tu peux répartir la recherche sur plusieurs séances.

Deux horloges et le théorème chinois

Deux signaux se déclenchent tous les 7 et 11 jours. On cherche un jour $$x$$ congru à 3 modulo 7 et à 5 modulo 11. Le but est de résoudre ce cas puis de démontrer une règle générale. Durée indicative : 75 à 100 minutes.

Partie I : Résoudre à la main

Écris $$x=3+7k$$ et déduis une congruence pour k modulo 11.
Trouve k puis toutes les valeurs de x. Donne la première valeur positive.
Pourquoi deux solutions diffèrent-elles d'un multiple de 77 ?

Partie II : Construire une solution générale

Soient $m,n\ge2$ premiers entre eux et $$mu+nv=1$$ .

Pour deux entiers a,b, vérifie que $$x_0=anv+bmu$$ satisfait $x_0\equiv a\pmod m$ et $x_0\equiv b\pmod n$ .
Montre que toutes les solutions sont $$x_0+mnk$$ , $k\in\Z$ .
Pourquoi y a-t-il un unique représentant dans $\{0,\ldots,mn-1\}$ ?

Partie III : Lorsque les modules ne sont pas premiers entre eux

Montre que $x\equiv1\pmod6$ et $x\equiv2\pmod9$ sont incompatibles.
Résous en revanche $x\equiv1\pmod6$ et $x\equiv4\pmod9$ .
Pour $d=\gcd(m,n)$ , démontre que $a\equiv b\pmod d$ est une condition nécessaire à l'existence d'une solution.

Pistes

L'inverse de 7 modulo 11 est 8. Dans II, réduis séparément l'expression proposée modulo m et n. Dans III, commence par réduire les deux restes modulo 3.

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Démonstration · Solution expliquée

Au départ,

\begin{aligned}r_0 &= 30\\[.35em] &= 1\times30+0\times18\end{aligned}

\begin{aligned}\text{et }r_1 &= 18\\[.35em] &= 0\times30+1\times18.\end{aligned}

Le quotient 1 donne le reste $$12=30-18$$ , donc ses coefficients sont $$(1,-1)$$ . Le quotient suivant est encore 1 :

\begin{aligned}6 &= 18-12\\[.35em] &= 18-(30-18)\\[.35em] &= -30+2\times18,\end{aligned}

coefficients $$(-1,2)$$ . Enfin $12=2\times6+0$ arrête l'algorithme.

Le dernier reste non nul et ses coefficients donnent $$(6,-1,2)$$ . Vérification : $30(-1)+18\times2=6$ . À chaque ligne, la même opération « première ligne moins quotient fois seconde » est effectuée sur les restes et sur leurs coefficients. Ainsi l'algorithme conserve une expression exacte des restes avec les nombres de départ.

Corrigé du problème

Partie I : Transformer le système en une congruence

1. $x\equiv3\pmod7$ signifie $$x=3+7k$$ pour un entier $$k$$ . Remplaçons dans la seconde condition : $3+7k\equiv5\pmod{11}$ . Soustraire 3 donne $7k\equiv2\pmod{11}$ .

2. Le produit

\begin{aligned}7\times8 &= 56\\[.35em] &= 5\times11+1\end{aligned}

montre que 8 est un inverse de 7 modulo 11. Multiplier donne $k\equiv16\equiv5\pmod{11}$ . Donc $$k=5+11t$$ , puis

\begin{aligned}x &= 3+7(5+11t)\\[.35em] &= 38+77t.\end{aligned}

Pour $$t=0$$ , $$x=38$$ ; pour $t\le-1$ , $x\le-39$ , et pour $t\ge1$ , $x\ge115$ . La première valeur positive est donc 38. Vérification :

\begin{aligned}38 &= 5\times7+3\\[.35em] &= 3\times11+5.\end{aligned}

3. Si $$x,x'$$ satisfont les deux congruences, $$x-x'$$ est divisible par 7 et par 11. Écrivons $$x-x'=7h$$ . Comme 11 divise $$7h$$ et est premier avec 7, Gauss donne $$h=11s$$ . Donc $$x-x'=77s$$ . La période 77 vient de cette preuve, pas seulement des premiers jours essayés.

Partie II : Construire et prouver toutes les solutions

1. L'identité $$mu+nv=1$$ donne, modulo $$m$$ , $nv\equiv1$ et $mu\equiv0$ . Ainsi

\begin{aligned}x_0 &= anv+bmu\equiv a\times1+b\times0\\[.35em] &= a.\end{aligned}

Modulo $$n$$ , les rôles s'échangent : $nv\equiv0$ , $mu\equiv1$ , donc $x_0\equiv a\times0+b\times1=b$ . Le choix des deux termes construit une contribution utile dans un module et nulle dans l'autre.

2. Pour toute solution $$x$$ , les deux différences $$x-x_0$$ sont divisibles par $$m$$ et par $$n$$ . Comme ils sont premiers entre eux, leur produit divise la différence : $$x=x_0+mnk$$ . Réciproquement, ajouter un multiple de $$mn$$ ajoute un multiple de chacun des modules ; toute valeur de cette forme conserve donc les deux congruences. Cela prouve l'exhaustivité et la validité de la famille.

3. La division euclidienne de $$x_0$$ par $$mn$$ donne $$x_0=mnq+r$$ avec $0\le r<mn$ . Le reste $$r=x_0-mnq$$ appartient à la famille et fournit un représentant dans l'intervalle. Si deux représentants y existaient, leur différence serait un multiple de $$mn$$ strictement compris entre $$-mn$$ et $$mn$$ , donc zéro. Le représentant est unique.

Partie III : Comprendre l'obstacle d'un diviseur commun

1. Si $$x=1+6k$$ , alors $x\equiv1\pmod3$ . Si $x=2+9\ell$ , alors $x\equiv2\pmod3$ . Un entier ne peut avoir deux restes différents dans la même division euclidienne : le premier système est impossible.

2. Pour le second, $$x=1+6k$$ et $x\equiv4\pmod9$ donnent $6k\equiv3\pmod9$ . Cela signifie $6k-3=9\ell$ . Diviser par 3 donne $2k-1=3\ell$ , soit $2k\equiv1\pmod3$ . L'inverse de 2 modulo 3 est 2, donc $k\equiv2\pmod3$ , soit $$k=2+3t$$ . Ainsi

\begin{aligned}x &= 1+6(2+3t)\\[.35em] &= 13+18t.\end{aligned}

Contrôle : $$x-1=6(2+3t)$$ et $$x-4=9(1+2t)$$ , donc les deux conditions sont satisfaites. La période est 18, PPCM de 6 et 9.

3. En général, $d=\gcd(m,n)$ divise $$m$$ et $$n$$ . Si $$x-a=mk$$ et $x-b=n\ell$ , les deux différences sont divisibles par $$d$$ . Leur soustraction donne $b-a=mk-n\ell$ , encore divisible par $$d$$ . Donc $a\equiv b\pmod d$ est nécessaire. Cette dernière preuve montre qu'une solution impose cette condition ; elle ne prétend pas à elle seule construire une solution lorsque la condition est satisfaite.

Faire le point par une variante autonome

Essaie cette variante sans relire le corrigé précédent. Explique le choix de ta méthode, puis utilise les contrôles pour décider quelle notion retravailler.

À toi d’essayer

Une équation entière jusqu’au bout

Résous $$4x+7y=1$$ dans les entiers. Déduis un inverse de 4 modulo 7 et les solutions positives ou nulles.

Pour démarrer. Après le couple $$(2,-1)$$ , soustrais les équations pour trouver les pas de la famille.

Tu peux chercher, prendre un indice ou lire l’explication, à ton rythme.

Indice 1 · Une piste

Le couple $$(2,-1)$$ convient.

Indice 2 · Un pas de plus

Toutes les solutions sont $$(2+7k,-1-4k)$$ .

Voir l’explication

$4\times2+7(-1)=1$ . Pour une autre solution, $$4(x-2)+7(y+1)=0$$ . Gauss donne $7\mid(x-2)$ , car $\gcd(4,7)=1$ . Écrivons $$x=2+7k$$ ; remplacer donne $$y=-1-4k$$ . Toute cette famille vérifie

\begin{aligned}4x+7y &= 8+28k-7-28k\\[.35em] &= 1.\end{aligned}

Modulo 7, l'identité particulière donne $4\times2\equiv1$ , donc 2 est un inverse de 4. Pour $x,y\ge0$ , on aurait $k\ge-2/7$ , donc $k\ge0$ , et $k\le-1/4$ , donc $k\le-1$ . Aucune valeur entière ne satisfait les deux.

Fiche-mémoire

Euclide : $\gcd(a,b)=\gcd(b,r)$ ; le dernier reste non nul est le PGCD.
Bézout : $$au+bv=d$$ ; une combinaison égale à 1 caractérise les entiers premiers entre eux.
Gauss : $a\mid bc$ et $\gcd(a,b)=1$ impliquent $a\mid c$ .
a est inversible modulo n exactement si $\gcd(a,n)=1$ .
$$ax+by=c$$ est soluble exactement si $d\mid c$ ; les solutions s'obtiennent par un paramètre entier.
Pour $ax\equiv b\pmod n$ , divise les trois termes par le PGCD lorsque celui-ci divise b.

Contrôle. Ai-je vérifié une identité de Bézout ? La coprimalité exigée par Gauss est-elle établie ? Mon paramètre est-il entier ? Ai-je imposé les éventuelles contraintes de positivité à la fin ?

Maîtrise du chapitre

Validation contrôlée

Réponds aux QCM, sélectionne les bonnes propositions ou remets les étapes dans l'ordre. Le site vérifie chaque réponse avant d'ouvrir la balise suivante.

Avant le cours, vérifie tes bases

Pourquoi ce chapitre ?

Le problème fondamental : quels nombres peut-on fabriquer ?

L'idée avant la formule

Pourquoi remplacer une paire par une autre ?

Le calcul peut se lire dans les deux sens

Une solution n'est pas toutes les solutions

Le cours formel

PGCD et entiers premiers entre eux

Algorithme d'Euclide et invariant des diviseurs

Remonter Euclide et démontrer Bézout

Le théorème de Gauss

Inverses et congruences linéaires

Équations diophantiennes : toutes les solutions

Euclide étendu et PPCM

Boîte à outils : rendre la solution exhaustive

Trouver tous les couples et imposer une contrainte

Une congruence avec plusieurs classes

Une méthode pour inverser de grands coefficients

PGCD d'une famille : ne pas s'arrêter aux possibilités

Exercices progressifs

Exercice 1 : PGCD et signes ★☆☆

Exercice 2 : Euclide ★☆☆

Exercice 3 : Vérifier Bézout ★☆☆

Exercice 4 : Simplifier avec Gauss ★☆☆

Exercice 5 : Inverse modulaire ★☆☆

Exercice 6 : Remonter Euclide ★★☆

Exercice 7 : Pas de solution ★★☆

Exercice 8 : Toutes les solutions ★★☆

Exercice 9 : Congruence non inversible ★★☆

Exercice 10 : Combiner des divisibilités ★★☆

Exercice 11 : Solutions positives ★★★

Exercice 12 : PGCD dépendant d’un entier ★★★

Exercice 13 : Une fraction irréductible ★★★

Exercice 14 : Une racine rationnelle, prolongement ★★★

Exercice 15 : Invariant de l’algorithme ★★★

Problème : Pour aller plus loin

Deux horloges et le théorème chinois

Partie I : Résoudre à la main

Partie II : Construire une solution générale

Partie III : Lorsque les modules ne sont pas premiers entre eux

Pistes

Corrigés détaillés

Corrigé 1

Corrigé 2

Corrigé 3

Corrigé 4

Corrigé 5

Corrigé 6

Corrigé 7

Corrigé 8

Corrigé 9

Corrigé 10

Corrigé 11

Corrigé 12

Corrigé 13

Corrigé 14

Corrigé 15

Corrigé du problème

Partie I : Transformer le système en une congruence

Partie II : Construire et prouver toutes les solutions

Partie III : Comprendre l'obstacle d'un diviseur commun

Faire le point par une variante autonome

Fiche-mémoire

Maîtrise du chapitre

Pour relier les notions