Convention : Les nombres utilisés

\(\mathbb{N}=\{0,1,2,\ldots\}\), \(\mathbb{N}^*=\{1,2,3,\ldots\}\), et \(\mathbb{Z}\) est l’ensemble des entiers relatifs. Dire \(k\in\mathbb{Z}\) autorise un nombre positif, nul ou négatif, mais pas \(\frac12\). Les lettres d’une égalité sont soumises aux conditions annoncées : une lettre n’est pas automatiquement positive.

Avant de commencer : Trois questions avant la définition

Les affirmations suivantes sont-elles vraies : \(-6\mid42\), \(8\mid22\), \(0\mid7\) ? Pour chacune, cherche s’il existe un multiplicateur entier.

Correction. \(42=(-6)\times(-7)\), donc la première est vraie. Pour la deuxième, l’unique multiplicateur possible serait \(22/8=11/4=2{,}75\), qui n’est pas entier : elle est fausse. Enfin \(0\times k=0\) pour tout entier \(k\), jamais 7 : la troisième est fausse. Si tu avais seulement calculé un quotient, le mot important à revoir dans la définition suivante est « entier ».

Définition : Diviseur et multiple

Pour \(d,a\in\mathbb{Z}\), on dit que \(d\) divise \(a\), et on écrit \(d\mid a\), lorsqu’il existe un entier \(k\) tel que

Exemple expliqué : Le sens de la barre

\(7\mid35\) signifie \(35=7\times5\). La barre se lit « divise » ; ce n’est ni une barre de fraction, ni une relation symétrique. En effet, \(35\nmid7\), car \(7/35=1/5\notin\mathbb{Z}\).

\(-4\mid28\) car \(28=(-4)\times(-7)\), et \(4\mid-28\) car \(-28=4\times(-7)\). Les signes des entiers n’empêchent pas la divisibilité. Le quotient entier change de signe lorsque l’un des facteurs change de signe.

Propriété : Zéro, signes et diviseur non nul

Tout entier divise 0. L’entier 0 ne divise que 0. Si \(d\mid a\), alors \(-d\mid a\) et \(d\mid-a\). Si \(d\mid a\) avec \(a\ne0\), alors \(d\ne0\) et \(|d|\le |a|\).

Démonstration : Revenir au multiplicateur

L’égalité \(0=d\times0\) prouve la première phrase, même pour \(d=0\). Si \(a=0\times k\), alors \(a=0\), ce qui prouve la seconde. Si \(a=dk\), alors \(a=(-d)(-k)\) et \(-a=d(-k)\), avec \(-k\) entier.

Enfin, si \(a=dk\ne0\), les deux facteurs \(d\) et \(k\) sont non nuls. Un entier non nul vérifie \(|k|\ge1\). Donc \(|a|=|d|\,|k|\ge |d|\). Cette borne permettra de chercher les diviseurs positifs d’un entier non nul dans une liste finie.

Représentation intuitive : Des pas de longueur fixe

Sur une droite graduée, les multiples de 4 sont les positions accessibles depuis 0 par des pas de longueur 4 : \(\ldots,-8,-4,0,4,8,\ldots\). Le nombre de pas, avec son signe, joue le rôle de \(k\). Cette image explique pourquoi un quotient non entier ne convient pas. Elle n’est pas une preuve générale, et un pas de longueur nulle ne permet d’atteindre que 0. Pour justifier, on revient toujours à \(a=dk\) avec \(k\in\mathbb{Z}\).

Définition : Combinaison linéaire entière

Si \(a,b\in\mathbb{Z}\), un entier de la forme \(ma+nb\), avec \(m,n\in\mathbb{Z}\), est une combinaison linéaire entière de \(a\) et \(b\). Les coefficients \(m\) et \(n\) peuvent être négatifs : une différence est donc aussi une combinaison.

Propriété : Un diviseur commun divise toute combinaison

Soient \(a,b,d,m,n\in\mathbb{Z}\). Si \(d\mid a\) et \(d\mid b\), alors

Démonstration : Faire apparaître le facteur commun

La première hypothèse donne \(a=du\) pour un entier \(u\), et la seconde \(b=dv\) pour un entier \(v\). On remplace donc chaque nombre par l’égalité qui lui correspond :

Méthode : Éliminer une lettre par une combinaison

Indice. Deux expressions dépendent du même entier et on cherche leurs diviseurs communs.

Premier geste. Choisir des coefficients qui rendent opposés les termes contenant cette lettre.

Développer les deux produits, distribuer le signe de soustraction, regrouper, puis conclure : tout diviseur commun divise le résultat obtenu. Une petite constante fournit une liste de possibilités. Il faut ensuite vérifier lesquelles conviennent ; une condition nécessaire n’est pas automatiquement suffisante.

Exemple expliqué : Une constante derrière deux expressions

Soit \(n\in\mathbb{Z}\). Posons \(A=2n+3\) et \(B=5n+4\). Si un entier positif \(d\) divise \(A\) et \(B\), il divise \(5A-2B\). Les coefficients 5 et 2 ont été choisis pour éliminer \(n\) :

Propriété : Transitivité

Si \(a\mid b\) et \(b\mid c\), alors \(a\mid c\).

Démonstration : Assembler les témoins

Il existe \(u,v\in\mathbb{Z}\) tels que \(b=au\) et \(c=bv\). En remplaçant \(b\), on trouve \(c=(au)v=a(uv)\). Comme \(uv\in\mathbb{Z}\), la divisibilité est établie. Cette propriété parle de divisibilité, pas seulement de taille des nombres.

Piège à éviter : Ce que la règle ne dit pas

De \(d\mid a+b\), on ne peut pas déduire \(d\mid a\) et \(d\mid b\). Par exemple, \(6\mid(5+13)\), mais 6 ne divise ni 5 ni 13. En revanche, si l’on sait aussi que \(d\mid a\), alors \(d\mid (a+b)-a=b\).

De même, \(6\mid3\times4\), mais 6 ne divise ni 3 ni 4. Une règle permettant de retirer un facteur d’un produit nécessitera une hypothèse supplémentaire ; on ne la suppose pas vraie ici.

À toi : Essai guidé : écrire puis combiner

1. Donne un témoin entier de \(-7\mid28\) et de \(5\mid-35\).

2. Un entier positif \(d\) divise \(4n+1\) et \(6n+5\), où \(n\in\mathbb{Z}\). Complète et développe la combinaison \(3(4n+1)-2(6n+5)\). Quelles valeurs peut prendre \(d\) ?

Indice, à lire seulement si nécessaire. Dans la deuxième question, les termes en \(n\) doivent s’annuler. Un diviseur positif de \(-7\) est aussi un diviseur de 7.

Correction expliquée : Essai guidé

1. \(28=(-7)\times(-4)\) et \(-35=5\times(-7)\). Les témoins sont \(-4\) et \(-7\).

2. Par la propriété des combinaisons, \(d\) divise

À toi : Tentative avant consultation

Soit \(n\in\mathbb{Z}\). Montre que le seul diviseur positif commun à \(n+2\) et \(3n+5\) est 1. Explique pourquoi ton raisonnement n’est pas seulement une vérification sur quelques valeurs de \(n\).

Indice, à lire seulement si nécessaire. Essaie de faire disparaître \(n\) dans une combinaison des deux expressions.

Ce que ta réponse doit montrer. Nommer un diviseur commun positif, construire une combinaison, justifier qu’il divise 1, puis vérifier que 1 convient.

Correction expliquée : Un argument valable pour tous les entiers

Soit \(d>0\) un diviseur commun. Il divise

À toi : Justification et variation de condition

Un élève écrit : « Si \(d\mid a+b\), alors \(d\mid b\). » Donne un contre-exemple, puis ajoute une hypothèse qui rend la phrase vraie. Justifie la phrase réparée en écrivant une combinaison.

Ce que ta réponse doit montrer. Un contre-exemple doit satisfaire l’hypothèse initiale et contredire sa conclusion. La nouvelle hypothèse doit être explicitement utilisée.

Correction expliquée : Réparer une implication

Avec \(d=4,a=1,b=3\), on a \(a+b=4\), donc \(4\mid(a+b)\), mais \(4\nmid3\). Ajoutons \(d\mid a\). Alors \(d\) divise \(1\times(a+b)+(-1)\times a=b\), ce qui établit la conclusion. Il ne suffit pas d’ajouter « les nombres sont entiers » : ils l’étaient déjà dans le contre-exemple.

Pour réparer une erreur : Si tu inverses diviseur et multiple

Première erreur. De \(9\mid27\), écrire \(9=27k\) inverse les rôles.

Rappel. Le nombre à droite de la barre est le produit du diviseur par un entier. Sur l’exemple plus simple \(3\mid12\), on écrit \(12=3\times4\), pas \(3=12\times4\).

Nouvel essai. Traduis \(-5\mid30\), puis contrôle le signe de ton témoin avant de lire.

Correction. \(30=(-5)\times(-6)\) ; les deux facteurs négatifs donnent bien un produit positif.

Retour. La ligne initiale devient \(27=9\times3\). Reprends maintenant la question 1 de l’essai guidé sans regarder sa correction.

Pour réparer une erreur : Si la soustraction change le mauvais signe

Première erreur. Dans l’exemple \(A=2n+3\), \(B=5n+4\), une copie écrit

Rappel sur un exemple plus simple. On distribue les deux facteurs avant de regrouper :

Correction. Les quatre produits donnent

Retour. Dans l’exemple initial, les termes sont \(10n+15-10n-8\), puis \((10n-10n)+(15-8)=7\). Retrouve maintenant cette ligne sans la copie fautive, puis explique pourquoi un diviseur commun doit diviser 7.

À toi : À reprendre plus tard, avant de relire

Soit \(n\in\mathbb{Z}\). Si un entier positif \(d\) divise \(5n+2\) et \(3n+1\), que peux-tu affirmer sur \(d\) ? Rédige sans tester de valeurs de \(n\).

Indice, à lire seulement si nécessaire. Les coefficients 3 et 5 permettent d’annuler les termes en \(n\).

Correction expliquée : Reprise différée

Le diviseur commun \(d\) divise \(3(5n+2)-5(3n+1)\). En développant,

À retenir : L’essentiel

Pour prouver \(d\mid a\), exhibe \(a=dk\) avec \(k\in\mathbb{Z}\). Un diviseur commun divise toute combinaison linéaire entière. Une combinaison bien choisie peut supprimer une inconnue ; il reste à contrôler les possibilités obtenues.

Avant de commencer : Commun à deux nombres

Parmi \(2,3,4,6,12\), quels nombres divisent à la fois 18 et 30 ? Le plus grand nombre de cette liste est-il nécessairement la réponse ?

Correction. 2, 3 et 6 divisent les deux nombres. 4 ne divise ni 18 ni 30 ; 12 ne divise pas 18. Le plus grand diviseur commun de la liste est donc 6, pas 12. Pour affirmer que c’est le plus grand de tous les diviseurs communs, il faut une liste exhaustive ou un argument de majoration. La méthode ci-dessous explique comment ne rien oublier.

Définition : Plus grand commun diviseur

Soient \(a,b\in\mathbb{Z}\), non tous les deux nuls. Le PGCD de \(a\) et \(b\), noté \(\operatorname{PGCD}(a,b)\), est le plus grand de leurs diviseurs positifs communs.

Si \(d=\operatorname{PGCD}(a,b)\), alors \(d>0\), \(d\mid a\), \(d\mid b\), et tout diviseur positif commun à \(a\) et \(b\) est inférieur ou égal à \(d\).

Démonstration : Pourquoi ce plus grand nombre existe

1 divise tous les entiers, donc l’ensemble des diviseurs positifs communs n’est pas vide. Au moins l’un de \(a,b\) est non nul ; supposons que ce soit \(a\). Chaque diviseur positif commun est alors compris entre 1 et \(|a|\). Il n’y a qu’un nombre fini d’entiers dans cet intervalle : on peut les ranger et choisir le plus grand. Celui-ci est unique, car deux plus grands éléments seraient chacun inférieur ou égal à l’autre. Si c’est seulement \(b\) qui est non nul, le même raisonnement utilise \(|b|\).

Convention : Le couple \((0,0)\)

Dans ce cours, \(\operatorname{PGCD}(0,0)\) n’est pas défini. Tous les entiers positifs divisent 0 : ils n’ont pas de plus grand élément. On rencontre parfois, notamment en informatique, la convention supplémentaire \(\operatorname{PGCD}(0,0)=0\). Elle prolonge une notation ; elle ne signifie pas que 0 serait le plus grand des diviseurs positifs de 0. Nous n’utilisons pas ce prolongement.

Méthode : Lister les diviseurs sans trou

Pour un petit entier positif \(A\), chercher les produits \(A=u\times v\) avec \(u\le v\). Les facteurs viennent par paires. Une fois \(u^2>A\), aucune nouvelle paire ne commence : si les deux facteurs étaient plus grands que \(\sqrt A\), leur produit dépasserait \(A\).

Faire cette liste pour chacun des deux nombres, garder seulement les éléments présents dans les deux listes, puis choisir le plus grand. Cette méthode est lisible sur de petits nombres ; elle devient coûteuse pour de grands nombres. L’algorithme d’Euclide sera alors préférable.

Exemple expliqué : Deux listes, puis leur intersection

Pour 30, les paires sont \(1\times30\), \(2\times15\), \(3\times10\), \(5\times6\). Il suffit de tester 1, 2, 3, 4 et 5, car \(5<\sqrt{30}<6\) ; parmi ces entiers, seul 4 ne fournit pas de paire. Pour 42, on obtient \(1\times42\), \(2\times21\), \(3\times14\), \(6\times7\). Ainsi :

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

Pour \(a,b\) non simultanément nuls,

Démonstration : Les mêmes diviseurs, ou un plus grand déjà visible

Être diviseur commun de \(a,b\) ne dépend pas de l’ordre des deux nombres. De plus, \(d\mid a\) équivaut à \(d\mid-a\) : le témoin change seulement de signe. Les ensembles de diviseurs positifs sont donc inchangés par la valeur absolue.

Tous les diviseurs de \(a\) divisent 0 ; le plus grand positif est \(|a|\), qui divise \(a\) et 0. Le même argument vaut pour le couple \((a,a)\).

Enfin, si \(b\mid a\), \(|b|\) est un diviseur positif des deux nombres. Un autre diviseur commun doit diviser \(b\ne0\), donc il ne dépasse pas \(|b|\). Cela prouve à la fois qu’il convient et qu’aucun plus grand ne convient.

Exemple expliqué : Un PGCD reste positif

\(\operatorname{PGCD}(-30,42)=\operatorname{PGCD}(30,42)=6\), \(\operatorname{PGCD}(-17,0)=17\), et \(\operatorname{PGCD}(48,-12)=12\), car \(-12\mid48\). Écrire \(\operatorname{PGCD}(-17,0)=-17\) contredirait la définition, qui choisit un diviseur positif.

Question d’élève : « Plus grand » signifie-t-il « multiple des autres » ?

La définition donne une comparaison de tailles, pas encore une relation de divisibilité. Par exemple \(4\le6\) n’implique pas \(4\mid6\). Il faudra démontrer un résultat supplémentaire pour affirmer que tout diviseur commun divise le PGCD. L’algorithme d’Euclide nous le permettra ; on ne le déduit pas ici du seul mot « grand ».

Exemple expliqué : Découper sans reste

Une plaque rectangulaire de \(168\,\mathrm{cm}\) sur \(252\,\mathrm{cm}\) est découpée suivant une grille en carrés identiques. On cherche le plus grand côté entier en centimètres, sans chute.

Si \(c\) est ce côté, \(168/c\) et \(252/c\) doivent être des entiers : \(c\mid168\) et \(c\mid252\). Tout tel \(c>0\) divise la différence \(252-168=84\), donc \(c\le84\). Or \(168=84\times2\) et \(252=84\times3\) : 84 convient. Par conséquent, \(\operatorname{PGCD}(168,252)=84\). Le côté maximal est \(84\,\mathrm{cm}\) et on obtient \(2\times3=6\) carrés.

Lecture du schéma. Le rectangle est partagé en six carrés : la longueur porte trois côtés de carré et la largeur en porte deux. La preuve du caractère maximal vient de la divisibilité par 84, non du dessin à l’échelle.

Représentation intuitive : Une unité de mesure commune, avec une limite

Pour deux longueurs entières exprimées dans la même unité, un diviseur commun est une taille de morceau qui mesure les deux sans reste ; le PGCD est la plus grande taille entière possible. Cette lecture suppose des longueurs et des morceaux positifs, un découpage régulier et une même unité. Elle n’explique pas à elle seule les arguments négatifs du PGCD : les signes se traitent par la propriété démontrée précédemment.

À toi : Essai guidé : liste et interprétation

1. Écris toutes les paires de facteurs positifs de 24 et de 36.

2. Déduis leurs diviseurs communs et leur PGCD.

3. Quelle est la plus grande longueur entière de morceaux permettant de couper deux rubans de \(24\,\mathrm{cm}\) et \(36\,\mathrm{cm}\) sans chute ? Combien de morceaux obtient-on au total ?

Indice, à lire seulement si nécessaire. La plus grande taille et le nombre total de morceaux sont deux réponses différentes.

Correction expliquée : Essai guidé

Les paires de 24 sont \((1,24),(2,12),(3,8),(4,6)\). Celles de 36 sont \((1,36),(2,18),(3,12),(4,9),(6,6)\). Les diviseurs communs positifs sont \(1,2,3,4,6,12\). Donc \(\operatorname{PGCD}(24,36)=12\).

Les morceaux mesurent \(12\,\mathrm{cm}\). Le premier ruban en fournit \(24/12=2\), le second \(36/12=3\), soit \(2+3=5\) morceaux. Le PGCD est une longueur dans cette interprétation, pas le nombre 5.

À toi : Tentative avant consultation

Détermine \(\operatorname{PGCD}(-45,60)\), puis tous les diviseurs relatifs communs à ces deux nombres. Justifie l’exhaustivité de ta liste.

Indice, à lire seulement si nécessaire. Commence par les diviseurs positifs de 45 et de 60. Chaque diviseur positif donne aussi son opposé.

Ce que ta réponse doit montrer. Traiter le signe, produire une liste complète, distinguer le PGCD positif de l’ensemble des diviseurs relatifs.

Correction expliquée : Signes et liste complète

Les diviseurs positifs de 45 sont \(1,3,5,9,15,45\). Ceux de 60 sont \(1,2,3,4,5,6,10,12,15,20,30,60\). L’intersection est \(\{1,3,5,15\}\), d’où \(\operatorname{PGCD}(-45,60)=15\).

Les diviseurs relatifs communs sont \(-15,-5,-3,-1,1,3,5,15\). Ils sont exhaustifs car tout diviseur relatif non nul donne, par valeur absolue, un diviseur positif des deux nombres. Zéro ne divise pas 45, donc il ne s’ajoute pas à la liste.

À toi : Justification : prouver un maximum

Soit \(a\in\mathbb{Z}\), \(a\ne0\). Explique pourquoi \(\operatorname{PGCD}(a,0)=|a|\). Une réponse « parce que 0 est divisible par tout » est-elle suffisante ?

Ce que ta réponse doit montrer. Montrer que \(|a|\) divise les deux nombres, puis qu’un diviseur positif commun ne peut pas le dépasser.

Correction expliquée : Les deux obligations d’une preuve de maximum

\(|a|\) divise \(a\), avec témoin 1 si \(a>0\) et \(-1\) si \(a<0\), et il divise 0 avec témoin 0. Si \(c>0\) divise \(a\ne0\), on écrit \(a=ck\) avec \(k\ne0\), donc \(|a|=c|k|\ge c\). Ainsi \(|a|\) est bien le plus grand. La phrase proposée ne disait pas pourquoi il n’existe pas de diviseur commun plus grand ; elle était incomplète.

À toi : Variation : une donnée nulle

Compare les situations \((-20,0)\), \((0,20)\) et \((0,0)\). Peut-on appliquer la même formule sans vérifier les conditions ?

Correction expliquée : La restriction ne disparaît pas

Les deux premiers PGCD valent 20, car leurs diviseurs positifs communs sont ceux de 20. Pour \((0,0)\), il n’existe pas de plus grand diviseur positif commun : quel que soit \(c>0\), \(c+1\) convient aussi. La formule avec un argument nul exige que l’autre soit non nul. Le cours laisse donc ce dernier couple hors du domaine de la définition.

Pour réparer une erreur : Si tu prends le plus grand nombre au lieu du plus grand diviseur

Erreur. « \(\operatorname{PGCD}(30,42)=42\), car 42 est plus grand. » La première condition perdue est : la réponse doit diviser les deux nombres. Or \(30/42=5/7\notin\mathbb{Z}\).

Exemple plus simple. Pour 8 et 12, les diviseurs communs sont \(1,2,4\). La réponse est 4 : \(8=4\times2\), \(12=4\times3\).

Nouvel essai. Calcule \(\operatorname{PGCD}(10,15)\), puis contrôle ta réponse par deux produits.

Correction. Les diviseurs positifs communs sont 1 et 5 ; le PGCD est 5. On vérifie \(10=5\times2\) et \(15=5\times3\).

Retour. Pour 30 et 42, reviens à la liste \(1,2,3,6\), puis à la conclusion 6. Le mot « commun » doit être contrôlé avant le mot « plus grand ».

À toi : À reprendre plus tard

On prépare des sachets identiques en utilisant exactement 54 cartes vertes et 90 cartes bleues, sans reste : chaque sachet doit avoir la même composition. Quel est le nombre maximal de sachets ? Quelle composition obtient-on ?

Indice, à lire seulement si nécessaire. Le nombre de sachets doit diviser chaque effectif ; un sachet contient des cartes des deux couleurs.

Correction expliquée : Reprise différée

Si \(s\) est le nombre de sachets, chaque sachet reçoit \(54/s\) cartes vertes et \(90/s\) bleues, donc \(s\mid54\) et \(s\mid90\). Les diviseurs positifs de 54 sont \(1,2,3,6,9,18,27,54\), ceux de 90 sont \(1,2,3,5,6,9,10,15,18,30,45,90\). Leur plus grand élément commun est 18.

On obtient au maximum 18 sachets, chacun avec \(54/18=3\) cartes vertes et \(90/18=5\) cartes bleues. Contrôle : \(18\times3=54\) et \(18\times5=90\). Ici le PGCD compte les sachets ; dans le découpage de rubans, il mesurait leur longueur. Le contexte décide de l’interprétation.

À retenir : L’essentiel

Le PGCD est positif et divise les deux nombres. Pour prouver qu’un entier est ce maximum, montrer qu’il convient et qu’aucun plus grand ne convient. Les signes ne changent pas le PGCD ; le couple \((0,0)\) est exclu de notre définition.

Avant de commencer : Lire correctement une division

Dans \(47=6\times7+5\), quel est le quotient de la division euclidienne de 47 par 6 ? Quel est le reste ? Pourquoi \(47=6\times6+11\) n’est-il pas une division euclidienne par 6 ?

Correction. Le quotient est 7, le reste 5. Une division euclidienne par un entier \(b>0\) exige \(0\le r<b\). La seconde égalité est vraie, mais son reste proposé 11 ne vérifie pas \(11<6\). Si tu avais accepté les deux écritures, c’est l’encadrement du reste qu’il faut remettre au centre de la méthode.

Propriété : Rappel : division euclidienne

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

Lemme : Conserver exactement les diviseurs communs

Soient \(a,b,q\in\mathbb{Z}\), avec \((a,b)\ne(0,0)\), et \(r=a-bq\). Un entier positif \(c\) divise \(a\) et \(b\) si et seulement s’il divise \(b\) et \(r\). Ainsi,

Démonstration : Il faut vérifier les deux sens

Du premier couple vers le second. Si \(c\mid a\) et \(c\mid b\), il existe \(u,v\in\mathbb{Z}\) tels que \(a=cu\) et \(b=cv\). Alors

Du second couple vers le premier. Si \(c\mid b\) et \(c\mid r\), écrivons \(b=cv\) et \(r=cw\), avec \(v,w\in\mathbb{Z}\). Comme \(a=bq+r\),

Méthode : Euclide, à la main

Quand ? Pour calculer un PGCD sans énumérer une longue liste de diviseurs.

Premier geste. Prendre les valeurs absolues. Si l’une est nulle, la réponse est l’autre, non nulle. Sinon, placer le plus grand en premier.

Effectuer une division euclidienne. Remplacer le couple « dividende, diviseur » par « diviseur, reste ». Répéter jusqu’au reste 0. La réponse est le diviseur de la dernière division. On l’appelle usuellement le « dernier reste non nul », en comptant aussi le diviseur initial si la première division est exacte.

Par exemple, \(24=4\times6+0\) donne directement \(\operatorname{PGCD}(24,6)=6\). Aucun reste calculé non nul n’a été produit : la réponse est ici le diviseur initial 6.

Contrôle à chaque ligne. Vérifier \(a=bq+r\) et \(0\le r<b\). À la fin, vérifier que le résultat divise les deux nombres de départ.

Exemple expliqué : De 425 et 272 à un petit diviseur

On ne connaît pas commodément tous les diviseurs de 425 et de 272. Les divisions successives donnent :

Théorème : Pourquoi l’algorithme s’arrête et pourquoi il est correct

Pour deux entiers non simultanément nuls, l’algorithme précédent se termine. Si l’un des nombres est nul, la réponse est la valeur absolue de l’autre. Sinon, le diviseur de la dernière division est leur PGCD : c’est le dernier reste non nul, ou le diviseur initial lorsque la première division est exacte.

Démonstration : Deux questions distinctes

Après les éventuels signes et cas nuls, on travaille avec \(A\ge B>0\). Tant qu’un reste est non nul, la division suivante utilise un entier strictement plus petit que le diviseur précédent. Une suite strictement décroissante d’entiers positifs ne peut pas continuer indéfiniment : au plus \(B\) valeurs positives différentes sont possibles à partir de \(B\). Il apparaît donc un reste nul. Cela prouve la terminaison.

Notons \(d>0\) le diviseur de la dernière division. Si la première division est exacte, \(d=B\) ; sinon \(d\) est le dernier reste non nul calculé. À chaque étape, le lemme conserve l’ensemble des diviseurs communs. À l’arrêt, le couple est \((d,0)\). Ses diviseurs positifs communs sont exactement ceux de \(d\), dont le plus grand est \(d\). Ainsi, le PGCD de départ est bien \(d\). Cela prouve la correction de l’algorithme. Un programme peut terminer et pourtant calculer une mauvaise valeur : les deux arguments étaient nécessaires.

Corollaire : Tous les diviseurs communs sont les diviseurs du PGCD

Soient \((a,b)\ne(0,0)\) et \(d=\operatorname{PGCD}(a,b)\). Pour tout entier positif \(c\),

Démonstration : Un résultat plus fort que le seul maximum

Le lemme, appliqué à toutes les divisions d’Euclide, donne les mêmes diviseurs communs au couple initial et au couple final \((d,0)\). Or tout entier divise 0 : être commun à \(d\) et 0 équivaut exactement à diviser \(d\). Les cas où un argument est nul au départ ont déjà cette forme. Ce raisonnement établit les deux sens.

Exemple expliqué : Finir une liste sans recommencer deux recherches

Puisque \(\operatorname{PGCD}(425,272)=17\), leurs diviseurs positifs communs sont 1 et 17. Pour obtenir les diviseurs relatifs communs, on ajoute leurs opposés : \(-17,-1,1,17\). Il n’est plus nécessaire de lister tous les diviseurs de 425 et de 272.

Méthode : Variante : des soustractions successives

Pour \(a\ge b>0\), le lemme avec \(q=1\) permet de remplacer \((a,b)\) par \((a-b,b)\), puis de remettre le plus grand en premier. La somme des deux nombres positifs diminue tant qu’ils ne sont pas égaux, donc le processus s’arrête à deux nombres égaux. Leur valeur commune est le PGCD.

Exemple : \((84,60)\to(60,24)\to(36,24)\to(24,12)\to(12,12)\). La réponse est 12. Une division euclidienne rassemble plusieurs soustractions identiques : pour de grands quotients, elle est plus rapide. Cette variante explique le mécanisme, mais n’est pas la méthode de calcul conseillée par défaut.

À toi : Essai guidé : suivre le bon couple

Complète les divisions pour calculer \(\operatorname{PGCD}(198,126)\) :

Indice, à lire seulement si nécessaire. Chaque nouveau couple est le diviseur et le reste de la ligne précédente.

Correction expliquée : Essai guidé

On trouve \(198=126+72\), \(126=72+54\), \(72=54+18\), puis \(54=3\times18+0\). Les restes sont bien strictement plus petits que les diviseurs. Donc \(\operatorname{PGCD}(198,126)=18\). Contrôle : \(198=18\times11\) et \(126=18\times7\).

Le lemme transforme \((a,b)\) en \((b,r)\). Garder toujours le premier dividende ne suivrait plus cette transformation et pourrait perdre le lien démontré entre les couples. Ici la chaîne est \((198,126)\), \((126,72)\), \((72,54)\), \((54,18)\), \((18,0)\).

À toi : Tentative avant consultation

Calcule \(\operatorname{PGCD}(391,221)\), puis détermine tous leurs diviseurs positifs communs. Rédige les divisions, et pas uniquement la valeur annoncée par une calculatrice.

Indice, à lire seulement si nécessaire. Le troisième reste se calcule en divisant 170 par 51.

Ce que ta réponse doit montrer. Chaque ligne doit être une division euclidienne valide ; le bon reste final est repéré ; la liste est reliée au corollaire.

Correction expliquée : Calcul et interprétation

À toi : Justifier les deux sens

Un élève a seulement prouvé : « Si \(c\mid a\) et \(c\mid b\), alors \(c\mid b\) et \(c\mid a-b\). » Pourquoi cela ne suffit-il pas à affirmer l’égalité des deux ensembles de diviseurs communs ? Complète le raisonnement.

Ce que ta réponse doit montrer. Nommer le sens manquant et utiliser \(a=(a-b)+b\), avec des coefficients entiers.

Correction expliquée : Une inclusion ne fait pas une égalité

La phrase prouvée dit seulement que les anciens diviseurs communs sont conservés. Elle n’exclut pas que le second couple en ait de nouveaux. Pour le sens inverse, supposons \(c\mid b\) et \(c\mid(a-b)\). Le diviseur \(c\) divise leur somme \((a-b)+b=a\). Il divise donc \(a\) et \(b\). Les deux ensembles sont désormais identiques, donc leurs plus grands éléments aussi.

À toi : Variation : signe et variante de calcul

1. Calcule \(\operatorname{PGCD}(-253,161)\) sans faire de divisions avec un diviseur négatif.

2. Retrouve \(\operatorname{PGCD}(45,30)\) par soustractions, puis par une division. Compare les résultats et explique l’accord.

Correction expliquée : Les conventions restent visibles

1. On passe à \((253,161)\). Puis \(253=161+92\), \(161=92+69\), \(92=69+23\), \(69=3\times23\). Le PGCD vaut 23. On contrôle \(-253=23\times(-11)\) et \(161=23\times7\).

2. Par soustractions : \((45,30)\to(30,15)\to(15,15)\), réponse 15. Par divisions : \(45=1\times30+15\), \(30=2\times15+0\), réponse 15. Les deux méthodes appliquent le même lemme, avec \(q=1\) à chaque soustraction ou avec le quotient euclidien pour regrouper les soustractions.

Pour réparer une erreur : Si tu annonces le dernier reste, égal à zéro

Erreur. À la ligne finale \(34=2\times17+0\), conclure « PGCD = 0 » oublie « non nul ». Zéro ne divise même pas 425.

Rappel et exemple simple. Pour 28 et 20 : \(28=20+8\), \(20=2\times8+4\), \(8=2\times4+0\). Le couple final est \((4,0)\) ; le PGCD vaut donc 4.

Nouvel essai. Fais les divisions pour 35 et 21, puis entoure le diviseur de la dernière division.

Correction. \(35=21+14\), \(21=14+7\), \(14=2\times7+0\). Le diviseur final est 7, et \(\operatorname{PGCD}(35,21)=7\).

Retour. Dans le calcul initial, le diviseur de la dernière division est 17. Le zéro signale l’arrêt ; il n’est pas la réponse.

À toi : À reprendre plus tard

Calcule \(\operatorname{PGCD}(437,299)\), puis justifie pourquoi 23 est un diviseur commun maximal et pas seulement un diviseur commun trouvé au hasard.

Indice, à lire seulement si nécessaire. Après les deux premières divisions, il reste à diviser 138 par 23.

Correction expliquée : Reprise différée

\(437=1\times299+138\), \(299=2\times138+23\), \(138=6\times23+0\). Donc \(\operatorname{PGCD}(437,299)=23\). Les contrôles \(437=23\times19\) et \(299=23\times13\) montrent qu’il convient. Sa maximalité vient de la conservation de tous les diviseurs communs jusqu’à \((23,0)\) : aucun diviseur positif de 23 ne le dépasse. Pour reprendre, distingue toujours « le candidat divise les deux nombres » et « le candidat est le plus grand ».

À retenir : L’essentiel

Euclide conserve tous les diviseurs communs et fait décroître les restes positifs. À l’arrêt, le diviseur de la dernière division est le PGCD : dernier reste non nul calculé, ou diviseur initial en cas de première division exacte. Les diviseurs communs de deux entiers sont exactement les diviseurs de leur PGCD.

Avant de commencer : Une expression à ne pas lire trop vite

Les nombres 8 et 15 sont-ils premiers entre eux ? Doivent-ils être des nombres premiers pour cela ?

Correction. Les diviseurs positifs de 8 sont \(1,2,4,8\), ceux de 15 sont \(1,3,5,15\). Leur seul diviseur commun positif est 1 : ils sont premiers entre eux. Pourtant \(8=2\times4\) et \(15=3\times5\) ne sont pas premiers. La définition qui suit concerne une relation entre deux nombres, pas une propriété de chaque nombre pris isolément.

Définition : Premiers entre eux

Deux entiers \(a,b\), non simultanément nuls, sont premiers entre eux lorsque \(\operatorname{PGCD}(a,b)=1\). On dit aussi qu’ils sont copremiers. Leur seul diviseur positif commun est alors 1 ; leurs seuls diviseurs relatifs communs sont 1 et \(-1\).

Vocabulaire : Un nombre premier, ce n’est pas la même chose

Un entier naturel \(p\) est premier lorsqu’il a exactement deux diviseurs positifs distincts : 1 et \(p\). Ainsi \(p\ge2\). Les nombres 0 et 1 ne sont pas premiers. Cette notion antérieure sert ici seulement à comparer les deux expressions « premier » et « premiers entre eux ».

Propriété : Quelques cas à connaître

• 1 et \(-1\) sont premiers avec tout entier.

• 0 est premier avec un entier \(a\) si et seulement si \(|a|=1\).

• Deux nombres premiers distincts sont premiers entre eux.

• Si \(p\) est premier, alors \(p\) et \(a\) sont premiers entre eux si et seulement si \(p\nmid a\).

Démonstration : Dénombrer les possibilités

Les seuls diviseurs positifs de 1 et \(-1\) sont 1. Pour \(a\ne0\), on a \(\operatorname{PGCD}(a,0)=|a|\), d’où le deuxième point ; le couple \((0,0)\) reste exclu.

Si \(p\) est premier, un diviseur positif commun à \(p\) et \(a\) vaut nécessairement 1 ou \(p\). Si \(p\mid a\), le PGCD vaut \(p\ne1\). Si \(p\nmid a\), seul 1 convient, donc le PGCD vaut 1. Cela prouve les deux sens du dernier point. Pour deux nombres premiers distincts \(p,q\), \(p\) ne divise pas \(q\), car les seuls diviseurs positifs de \(q\) sont 1 et \(q\). On obtient le troisième point.

Contre-exemple : Le mot « distincts » est indispensable

13 est premier, mais \(\operatorname{PGCD}(13,13)=13\), pas 1. La phrase « deux nombres premiers sont toujours premiers entre eux » est donc fausse sans la précision qu’ils sont distincts.

Méthode : Trois voies, selon les données

Petits nombres. Lister les diviseurs positifs et vérifier que l’intersection est \(\{1\}\).

Nombres numériques plus grands. Appliquer Euclide : une division \(A=Bq+r\), avec \(0\le r<B\), remplace le couple par \((B,r)\). Si le dernier reste non nul est 1, le PGCD est 1.

Expressions avec une lettre. Prendre un diviseur commun positif et chercher une combinaison égale à 1 ou \(-1\). Ce diviseur doit alors valoir 1. On n’utilise ici que la règle des combinaisons ; le théorème de Bézout expliquera plus loin pourquoi on peut toujours trouver une telle combinaison pour un couple copremier.

Exemple expliqué : Deux entiers consécutifs

Soit \(n\in\mathbb{Z}\). Si \(c>0\) divise \(n\) et \(n+1\), il divise leur différence \((n+1)-n=1\). Donc \(c=1\), et 1 divise bien les deux. On a ainsi

Exemple expliqué : Deux entiers séparés par 2

Pour \(n\in\mathbb{Z}\), un diviseur positif commun à \(n\) et \(n+2\) divise \((n+2)-n=2\). Il vaut donc 1 ou 2.

Si \(n\) est pair, il s’écrit \(n=2k\), donc \(n+2=2(k+1)\) : 2 divise les deux, et le PGCD vaut 2. Si \(n\) est impair, \(n=2k+1\) et 2 ne divise pas \(n\). Seul 1 reste possible, et le PGCD vaut 1. Ainsi,

Avant de commencer : Des quotients entiers sont-ils forcément copremiers ?

On divise 12 et 18 par leur diviseur commun 3. Quels quotients obtient-on ? Sont-ils premiers entre eux ?

Correction. Les quotients sont \(12/3=4\) et \(18/3=6\). Ils sont entiers, mais 2 les divise tous deux : ils ne sont pas copremiers. En retirant plutôt le PGCD 6, on obtient 2 et 3, de PGCD 1. Si tu avais conclu à partir du seul mot « entier », la propriété suivante précise ce qu’il faut imposer au diviseur choisi.

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

Soient \((a,b)\ne(0,0)\) et \(d=\operatorname{PGCD}(a,b)\). Il existe des entiers \(a',b'\) tels que

Démonstration : S’il restait un facteur commun

Puisque \(d>0\) divise \(a\) et \(b\), les quotients \(a'=a/d\) et \(b'=b/d\) sont entiers ; ils ne sont pas simultanément nuls. Prenons un diviseur positif commun \(e\) de \(a',b'\). Écrivons \(a'=eu\) et \(b'=ev\), avec \(u,v\in\mathbb{Z}\). Alors

Exemple expliqué : Voir ce que la réduction retire

\(\operatorname{PGCD}(-84,126)=42\) : en effet, \(126=84+42\), puis \(84=2\times42\). On écrit

Question d’élève : Être premiers entre eux dépend-il du signe ?

Non : \(\operatorname{PGCD}(a,b)=\operatorname{PGCD}(|a|,|b|)\). Les couples \((8,15)\), \((-8,15)\) et \((-8,-15)\) sont donc tous copremiers. En revanche, changer une valeur de 1 peut changer la situation : \(5,8\) sont copremiers, mais \(6,9\) ont un PGCD égal à 3.

À toi : Essai guidé : calculer puis réduire

1. Calcule \(\operatorname{PGCD}(91,130)\) par Euclide, en commençant par \(130=91+39\).

2. Écris 91 et 130 comme produits du PGCD par deux entiers.

3. Vérifie directement que les deux entiers restants sont premiers entre eux.

Indice, à lire seulement si nécessaire. Après la division de 91 par 39, le reste est 13.

Correction expliquée : Essai guidé

\(130=1\times91+39\), \(91=2\times39+13\), \(39=3\times13+0\). Donc le PGCD est 13. On obtient \(91=13\times7\) et \(130=13\times10\). Enfin \(10=1\times7+3\), \(7=2\times3+1\), \(3=3\times1+0\), donc \(\operatorname{PGCD}(7,10)=1\). Ce second calcul confirme concrètement la propriété du couple réduit.

À toi : Tentative avant consultation

Montre que \(n\) et \(2n+1\) sont premiers entre eux pour tout entier \(n\), y compris \(n=0\) et les entiers négatifs.

Indice, à lire seulement si nécessaire. Considère un diviseur commun positif et soustrais deux fois la première expression à la seconde.

Ce que ta réponse doit montrer. Le raisonnement doit porter sur un entier quelconque, utiliser un multiplicateur entier et traiter la possibilité de zéro sans division par \(n\).

Correction expliquée : Aucune division par une lettre

Les deux nombres ne sont jamais nuls ensemble : si \(n=0\), \(2n+1=1\). Soit \(c>0\) un diviseur commun. Il divise \((2n+1)-2n=1\), donc \(c=1\). Ainsi \(\operatorname{PGCD}(n,2n+1)=1\). On n’a jamais divisé par \(n\), et aucune étape n’exige \(n>0\). Le raisonnement couvre donc les valeurs nulles et négatives annoncées.

À toi : Retirer tous les facteurs communs

Détermine le couple premier entre eux obtenu en divisant 150 et \(-210\) par leur PGCD. Vérifie les signes et les deux produits qui redonnent les nombres de départ. Un autre élève a divisé par 10 et obtenu \((15,-21)\) : explique pourquoi sa division est correcte mais sa réduction inachevée.

Indice, à lire seulement si nécessaire. Prends les valeurs absolues pour Euclide ; la première division est \(210=150+60\). Ne change pas le signe du second nombre au moment de former les quotients.

Correction expliquée : Une division exacte ne retire pas toujours tout

Les divisions sont

Pour vérifier la coprimalité sans supposer que deux nombres différents suffisent, on calcule

Ce que ta réponse doit montrer. Ta réponse doit identifier le PGCD positif, conserver les signes dans les quotients, vérifier les deux produits de reconstruction et justifier qu’aucun facteur commun supérieur à 1 ne reste.

À toi : Justifier une réduction

Un élève affirme : « Si \(c\) divise \(a\) et \(b\), alors \(a/c\) et \(b/c\) sont premiers entre eux. » Donne un contre-exemple avec \(c>0\), puis précise la bonne hypothèse. Explique pourquoi elle empêche qu’il reste un facteur commun.

Ce que ta réponse doit montrer. Fournir un vrai diviseur commun qui ne retire pas tout, puis utiliser la maximalité du PGCD et non seulement son nom.

Correction expliquée : Un diviseur quelconque ne suffit pas

Prenons \(a=18,b=30,c=3\). On a bien \(3\mid18\) et \(3\mid30\), mais les quotients 6 et 10 ont encore le facteur commun 2. La bonne hypothèse est \(c=\operatorname{PGCD}(a,b)\). Si un facteur commun entier \(e>1\) subsistait dans les quotients, \(ce>c\) diviserait les deux nombres de départ, ce qui contredirait le caractère maximal de \(c\).

À toi : Variation : quand une conclusion change

1. Est-il vrai que deux entiers impairs sont toujours premiers entre eux ?

2. Pour quels entiers \(n\) les nombres \(n\) et \(n+2\) sont-ils premiers entre eux ?

3. Pourquoi les deux réponses ne se contredisent-elles pas ?

Correction expliquée : Le lien entre les deux nombres compte

1. Non : 9 et 15 sont impairs mais ont le diviseur commun 3.

2. L’étude de la différence 2 donne un PGCD égal à 1 exactement quand \(n\) est impair.

3. Dans la deuxième question, les deux nombres impairs sont séparés par 2, ce qui force un éventuel diviseur commun à diviser 2. Dans la première, aucune différence n’est imposée. Une condition de parité seule n’a donc pas le même effet qu’une relation entre les nombres.

Pour réparer une erreur : Si tu confonds « premier » et « premiers entre eux »

Erreur. Dire « 8 et 15 ne sont pas premiers, donc ils ne sont pas premiers entre eux » utilise une propriété individuelle à la place d’une propriété du couple.

Exemple plus simple. 4 et 9 sont composés, mais leurs diviseurs positifs \(\{1,2,4\}\) et \(\{1,3,9\}\) n’ont que 1 en commun.

Nouvel essai. Décide si 9 et 20 sont premiers entre eux, sans tenter de les appeler premiers.

Correction. \(20=2\times9+2\), \(9=4\times2+1\), \(2=2\times1\) : leur PGCD vaut 1. Ils sont premiers entre eux, même s’ils sont tous les deux composés.

Retour. Pour 8 et 15, reprends les deux listes de diviseurs du repérage et cherche leur intersection.

Pour réparer une erreur : Si tu t’arrêtes à un diviseur commun quelconque

Première erreur. Après \(24=4\times6\) et \(40=4\times10\), une copie annonce que \((6,10)\) est réduit. Or 2 divise encore 6 et 10. Le nombre 4 est un diviseur commun, pas le PGCD de 24 et 40.

Rappel. Si les quotients ont encore un facteur commun \(e>1\), le facteur retiré n’était pas complet : \(4\times e\) divise les deux nombres de départ. Ici \(4\times2=8\) convient.

Exemple plus simple corrigé. Pour 6 et 10, on retire leur PGCD 2 : \(6=2\times3\), \(10=2\times5\). Il reste \((3,5)\), premier entre eux puisque \(5=3+2\), \(3=2+1\), puis \(2=2\times1\).

Nouvel essai. Réduis le couple \((0,-18)\) par son PGCD. Pourquoi le couple \((0,-3)\), obtenu en divisant seulement par 6, n’est-il pas réduit ?

Correction. Le PGCD de 0 et \(-18\) vaut 18. On obtient \(0/18=0\) et \((-18)/18=-1\), donc \((0,-1)\). Son PGCD vaut 1 : un diviseur positif de \(-1\) vaut nécessairement 1, et 1 divise aussi 0. Les contrôles sont \(18\times0=0\) et \(18\times(-1)=-18\). En revanche, \(\operatorname{PGCD}(0,-3)=3\) : le facteur 3 restait présent après la division par 6.

Retour. Pour 24 et 40, retire 8, et non seulement 4 : \(24=8\times3\), \(40=8\times5\). Les quotients sont bien \((3,5)\), dont la coprimalité vient d’être vérifiée. Un quotient nul est permis ; c’est le diviseur utilisé qui doit être non nul.

À toi : À reprendre plus tard

Montre que \(7n+3\) et \(2n+1\) sont premiers entre eux pour tout \(n\in\mathbb{Z}\). Puis explique en une phrase pourquoi tu n’as pas besoin de savoir si chacun de ces nombres est premier.

Indice, à lire seulement si nécessaire. Calcule \(7(2n+1)-2(7n+3)\).

Correction expliquée : Reprise différée

Tout diviseur positif commun divise

À toi : À reprendre plus tard : reconstruire une réduction

Sans relire les exemples, écris 84 et \(-132\) comme le produit de leur PGCD positif par deux entiers premiers entre eux. Vérifie le couple réduit et les deux reconstructions.

Indice, à lire seulement si nécessaire. La première division sur les valeurs absolues est \(132=84+48\). Un changement de signe ne modifie pas un ensemble de diviseurs positifs.

Correction expliquée : Réduction différée, avec contrôle indépendant

Les divisions donnent

Ce que ta réponse doit montrer. Retrouver le facteur commun maximal, les deux quotients signés, leur coprimalité et les deux produits de contrôle ; la seule écriture de quotients entiers ne suffit pas.

À retenir : L’essentiel

« Premiers entre eux » signifie PGCD égal à 1. Ce n’est pas « chacun est premier ». Euclide, les listes ou une combinaison égale à 1 permettent de le prouver. Diviser les deux nombres par leur PGCD donne un couple copremier.

Définition : Combinaison linéaire entière

Une combinaison linéaire entière de deux entiers \(a,b\) est une expression \(au+bv\), avec \(u,v\in\mathbb{Z}\). Les coefficients peuvent être négatifs : une soustraction est donc permise. Pour une valeur obtenue, ils ne sont pas obligatoirement uniques.

Avant de commencer : Lire des coefficients sans les confondre avec les nombres

Calcule \(24\times2+15\times(-3)\). Quels sont les deux nombres combinés ? Quels sont leurs coefficients ?

Correction. Les nombres combinés sont \(24\) et \(15\) ; leurs coefficients sont \(2\) et \(-3\). Le calcul est

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

Soient \(a,b\in\mathbb{Z}\), non simultanément nuls, et \(d=\operatorname{PGCD}(a,b)\). Il existe deux entiers \(u,v\) tels que

Démonstration : Pourquoi la remontée produit toujours des entiers

Supposons d’abord \(a>0\) et \(b>0\). Les deux premiers nombres sont déjà des combinaisons de \(a\) et \(b\) :

Si les nombres sont non nuls mais de signes quelconques, on applique ce raisonnement à \(A=|a|\) et \(B=|b|\). Leur PGCD est encore \(d\). On obtient \(d=AU+BV\), avec \(U,V\in\mathbb{Z}\). Remplacer \(|a|\) par \(a\) lorsque \(a>0\), et par \(-a\) lorsque \(a<0\), modifie seulement le signe du coefficient de \(a\) ; on fait de même pour \(b\). Les coefficients restent entiers.

Enfin, si \(b=0\) et \(a\ne0\), alors \(d=|a|\) : on prend \((u,v)=(1,0)\) si \(a>0\), et \((-1,0)\) si \(a<0\). Si \(a=0\) et \(b\ne0\), les couples \((0,1)\) ou \((0,-1)\) conviennent selon le signe de \(b\). Le couple \((0,0)\) de nombres de départ est exclu : son PGCD n’est pas défini dans les conventions de ce cours.

Exemple expliqué : Une identité avec un PGCD différent de \(1\)

Cherchons des entiers \(u,v\) tels que \(187u+119v=\operatorname{PGCD}(187,119)\).

Premier geste : calculer le PGCD en conservant les divisions.

Deuxième geste : partir de la ligne qui a produit \(17\), et non de celle qui a produit \(0\). La troisième division donne \(17=68-51\). La deuxième donne \(51=119-68\). On remplace donc le bloc \(51\) par toute l’expression \(119-68\) :

Troisième geste : remplacer le dernier reste encore présent. La première division donne \(68=187-119\). Ainsi

Contrôle effectif :

Méthode : Fabriquer un couple de Bézout

Quand l’énoncé demande une identité \(au+bv=d\) et qu’aucun couple n’est visible, l’algorithme d’Euclide est une voie systématique.

1. Calcule le PGCD et conserve toutes les égalités de division.

2. Si la première division est exacte, le diviseur initial est le PGCD et fournit une identité immédiate. Sinon, isole le dernier reste non nul dans la division qui le produit.

3. Remplace, en remontant, chaque reste par son expression dans la ligne précédente. Mets les expressions remplacées entre parenthèses.

4. Distribue les coefficients, puis regroupe les multiples d’un même nombre avant la substitution suivante.

5. Arrête-toi lorsque seuls \(a\) et \(b\) figurent dans l’expression ; lis les deux coefficients dans le bon ordre.

6. Remplace \(u,v\) par les valeurs trouvées dans \(au+bv\) et calcule réellement le résultat.

Par exemple, \(24=6\times4\) donne directement \(\operatorname{PGCD}(24,6)=6\) et \(24\times0+6\times1=6\) : il n’y a pas de remontée à inventer. Si un nombre de départ est négatif, on peut effectuer Euclide sur les valeurs absolues, mais il faut ensuite rétablir le signe dans l’identité. Si l’un des nombres vaut zéro, le cas direct de la démonstration suffit.

Question d’élève : Pourquoi accepter des coefficients négatifs ? Sont-ils uniques ?

Pour écrire \(17\) avec \(187\) et \(119\), des coefficients tous deux positifs ou nuls ne conviendraient pas : si l’un d’eux est non nul, la somme est au moins \(119\) ; s’ils sont nuls, elle vaut \(0\). Une différence permet d’obtenir un nombre plus petit.

Les coefficients ne sont pas uniques. En plus de \((2,-3)\), le couple \((9,-14)\) convient, car

À toi : Essai guidé : organiser les substitutions

Les divisions suivantes donnent \(\operatorname{PGCD}(138,84)=6\) :

Indice, à lire seulement si nécessaire. Après le premier remplacement, \(30-(54-30)\) contient deux fois \(30\), pas zéro fois.

Correction expliquée : Essai guidé

On isole d’abord chaque reste utile : \(24=54-30\), \(30=84-54\), puis \(54=138-84\). Les substitutions donnent

À toi : À tenter avant de consulter la correction

Détermine \(\operatorname{PGCD}(119,70)\), puis un couple \((u,v)\in\mathbb{Z}^2\) vérifiant \(119u+70v=\operatorname{PGCD}(119,70)\). Conserve les divisions et vérifie le couple.

Indice, à lire seulement si nécessaire. Les trois premiers restes non nuls sont \(49\), \(21\) et \(7\).

Correction expliquée : Un couple pour \(119\) et \(70\)

Les divisions sont

À toi : Justifier une décision et changer le signe d’une donnée

1. Pourquoi ne commence-t-on pas la remontée de l’exemple de référence par \(0=51-3\times17\) ? Explique ce que cette égalité permettrait d’obtenir.

2. Sans refaire Euclide, transforme l’identité \(119\times3+70\times(-5)=7\) en une identité de Bézout pour \(-119\) et \(70\).

3. Donne une identité de Bézout pour \(0\) et \(-26\).

Indice, à lire seulement si nécessaire. Dans la deuxième question, le produit par le premier nombre doit rester égal à \(357\).

Correction expliquée : L’objectif, l’ordre et les signes

1. Partir de l’égalité produisant zéro et ne faire que des substitutions correctes conserverait zéro au membre de gauche : on construirait une combinaison égale à \(0\), pas au PGCD \(17\). La remontée part donc de la ligne qui a produit le dernier reste non nul.

2. Comme \(119\times3=(-119)\times(-3)\), on obtient

3. Le PGCD de \(0\) et \(-26\) vaut \(26\). L’identité

Ce que ta réponse doit montrer. Nomme l’objectif de la remontée ; indique quel coefficient multiplie quel nombre ; conserve une égalité exacte lorsque le signe d’une donnée change. Ces justifications comptent autant que le couple final.

Pour réparer une erreur : Si un moins devant une parenthèse te fait perdre le fil

L’erreur « \(68-(119-68)=68-119-68\) » apparaît au moment où la parenthèse est supprimée. Le signe moins doit multiplier les deux termes : \((-1)\times119=-119\) et \((-1)\times(-68)=+68\).

Rappel avec un calcul plus simple. Pour \(9-(7-4)\), calculer l’intérieur donne \(9-3=6\). Distribuer le signe moins donne aussi \(9-7+4=2+4=6\). L’écriture \(9-7-4=-2\) ne conserve pas la valeur.

Nouvel essai. Développe \(11-(8-5)\) sans calculer d’abord la parenthèse ; contrôle ensuite par un calcul direct.

Correction. On obtient \(11-8+5=3+5=8\). Directement, \(8-5=3\), puis \(11-3=8\). Les deux chemins concordent.

Retour à la remontée. Il faut écrire \(68-119+68=2\times68-119=136-119=17\). C’est ce regroupement qui produit le coefficient \(2\) de l’étape suivante ; le signe n’est pas un détail de présentation.

À toi : À reprendre lors d’une prochaine séance, avant relecture

Trouve le PGCD de \(161\) et \(98\), puis des entiers \(u,v\) tels que \(161u+98v\) soit égal à ce PGCD. Explique pourquoi tes coefficients sont entiers et contrôle ton égalité.

Indice, à lire seulement si nécessaire. Les restes successifs non nuls sont \(63\), \(35\), \(28\), puis \(7\).

Correction expliquée : Reprise différée

Les divisions donnent

À retenir : L’essentiel

Euclide fournit le PGCD ; la remontée construit une identité entière qui le représente avec les nombres de départ. Garde les parenthèses pendant les substitutions, distribue les signes, puis regroupe. Un couple correct se vérifie par substitution ; il n’est généralement pas unique.

Avant de commencer : Que prouve une combinaison égale à \(1\) ?

Vérifie \(2\times35-3\times23=1\). Si \(c\) est un diviseur positif commun à \(35\) et \(23\), que peux-tu en déduire ?

Correction. Le calcul donne \(70-69=1\). Le nombre \(c\) divise les deux termes de la combinaison, donc il divise \(1\). Le seul diviseur positif de \(1\) est \(1\) lui-même : il n’existe aucun diviseur commun positif supérieur à \(1\). Ainsi \(35\) et \(23\) sont premiers entre eux. Si cette conclusion te bloque, reprends l’écriture \(au+bv=c(Au+Bv)\) donnée juste avant : elle explique la divisibilité employée.

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

Pour deux entiers \(a,b\) non simultanément nuls,

Démonstration : Deux implications, deux rôles différents

Si \(\operatorname{PGCD}(a,b)=1\), l’identité de Bézout appliquée au PGCD fournit des entiers \(u,v\) tels que \(au+bv=\operatorname{PGCD}(a,b)=1\). Ce sens établit l’existence des coefficients.

Si \(au+bv=1\) avec \(u,v\in\mathbb{Z}\), notons \(g=\operatorname{PGCD}(a,b)\). Comme \(g\mid a\) et \(g\mid b\), il existe des entiers \(A,B\) tels que \(a=gA\) et \(b=gB\). Alors

Piège à éviter : Des coefficients rationnels ne suffisent pas

L’égalité \(6\times\frac16+10\times0=1\) est exacte, mais elle ne prouve pas que \(6\) et \(10\) sont premiers entre eux : le coefficient \(\frac16\) n’est pas entier. Leur PGCD vaut \(2\). Dans la preuve, le facteur \(Au+Bv\) doit être entier pour conclure à une divisibilité ; c’est précisément ce qui échouerait avec des coefficients quelconques.

Caractérisation : Certifier un PGCD qui n’est pas forcément \(1\)

Soient \(a,b\in\mathbb{Z}\) non simultanément nuls, et \(d\in\mathbb{N}^*\). Alors \(d=\operatorname{PGCD}(a,b)\) si et seulement si les deux conditions suivantes sont réunies :

1. \(d\) divise \(a\) et \(b\) ;

2. il existe \(u,v\in\mathbb{Z}\) tels que \(d=au+bv\).

Une combinaison égale à \(d\) ne suffit donc pas à elle seule lorsque \(d\ne1\).

Démonstration : Pourquoi les deux conditions sont nécessaires

Si \(d\) est le PGCD, il divise les deux nombres par définition, et l’identité de Bézout fournit la combinaison entière : les deux conditions sont nécessaires.

Réciproquement, supposons les deux conditions satisfaites et notons \(g=\operatorname{PGCD}(a,b)\). Puisque \(d\) est un diviseur positif commun, la définition du plus grand donne \(d\leq g\). Comme \(g\) divise \(a\) et \(b\), il divise aussi \(au+bv=d\). Ainsi \(d=gt\) pour un entier \(t\). Les nombres \(d,g\) étant positifs, \(t\geq1\), donc \(g\leq d\). Les deux inégalités donnent \(g=d\). On a bien prouvé le sens réciproque, et non seulement vérifié un exemple.

Exemple expliqué : Un certificat complet, puis un faux raccourci

Pour \(84\) et \(132\), on a \(84=12\times7\) et \(132=12\times11\) : \(12\) divise les deux nombres. De plus,

En revanche, l’égalité \(30\times2-42\times1=60-42=18\) ne démontre pas que \(18\) est le PGCD de \(30\) et \(42\). Le nombre \(18\) ne divise même pas \(30\) : \(30=18\times1+12\). Une combinaison donne un multiple du PGCD, pas nécessairement le PGCD lui-même.

Propriété : Homogénéité du PGCD

Pour \(a,b\in\mathbb{Z}\) non simultanément nuls et \(k\in\mathbb{Z}\setminus\{0\}\),

Démonstration : Certifier le résultat au lieu de le deviner

Supposons d’abord \(k>0\) et posons \(d=\operatorname{PGCD}(a,b)\). Comme \(a=dA\) et \(b=dB\) pour des entiers \(A,B\), on a \(ka=(kd)A\) et \(kb=(kd)B\) : \(kd\) divise les deux nombres.

De plus, il existe des entiers \(u,v\) tels que \(au+bv=d\). Multiplions les deux membres par \(k\) :

Si \(k<0\), posons \(m=-k=|k|>0\). Les nombres \(ka,kb\) sont les opposés de \(ma,mb\). Or un entier divise un nombre si et seulement s’il divise son opposé : de \(x=ct\) on déduit \(-x=c(-t)\), et réciproquement. Changer ces signes ne change donc pas le PGCD. On obtient

Corollaire : Reconnaître un couple déjà réduit

Si \(d\in\mathbb{N}^*\) divise les deux entiers \(a,b\), non simultanément nuls, alors

Démonstration : Le passage logique depuis l’homogénéité

Posons \(A=a/d\) et \(B=b/d\). Ce sont des entiers, car \(d\) divise les deux nombres, et ils ne sont pas simultanément nuls. L’homogénéité donne \(\operatorname{PGCD}(a,b)=\operatorname{PGCD}(dA,dB)=d\,\operatorname{PGCD}(A,B)\). Ainsi \(\operatorname{PGCD}(a,b)=d\) équivaut à \(d\,\operatorname{PGCD}(A,B)=d\). Diviser les deux membres par le coefficient non nul \(d\) donne \(\operatorname{PGCD}(A,B)=1\). Aucune division par \(A\) ou \(B\) n’est effectuée : l’un d’eux peut être nul.

Exemple expliqué : Réutiliser un certificat déjà obtenu

On a établi \(\operatorname{PGCD}(84,132)=12\). Puisque \(252=3\times84\) et \(396=3\times132\),

Méthode : Chercher une combinaison qui ne dépend plus du paramètre

Quand deux nombres sont de la forme \(an+b\) et \(cn+d\), avec \(a,b,c,d\) entiers connus et \(n\in\mathbb{Z}\), les tester pour quelques valeurs de \(n\) ne prouve rien pour tous les entiers. Le premier geste utile est souvent d’éliminer les termes en \(n\) : multiplier la première expression par \(c\), la seconde par \(a\), puis soustraire.

Si la combinaison obtenue vaut \(1\) ou \(-1\), les deux nombres sont premiers entre eux. Si elle vaut un autre entier \(K\ne0\), le PGCD est un diviseur positif de \(|K|\) ; il faut encore décider lequel. Si la combinaison vaut \(0\), elle ne borne pas le PGCD : tout entier non nul divise \(0\).

Exemple expliqué : Un certificat valable pour tout entier \(n\)

Montrons que \(4n+3\) et \(3n+2\) sont premiers entre eux pour tout \(n\in\mathbb{Z}\). Les coefficients de \(n\) sont \(4\) et \(3\) ; on choisit donc la combinaison \(3(4n+3)-4(3n+2)\) :

Pour contrôler un calcul, on peut prendre \(n=2\) : les deux nombres valent \(11\) et \(8\), et \(3\times11-4\times8=33-32=1\). Ce test ne remplace pas la preuve générale, donnée par le développement précédent.

À toi : Essai guidé : certificat, facteur commun et paramètre

1. Montre que \(\operatorname{PGCD}(75,130)=5\) en utilisant \(7\times75-4\times130=5\). Quelles vérifications faut-il ajouter à cette égalité ? Explique ensuite pourquoi, pour une combinaison égale à \(1\), aucune recherche de diviseurs supplémentaires n’est nécessaire.

2. Déduis de \(\operatorname{PGCD}(84,132)=12\) la valeur de \(\operatorname{PGCD}(-5\times84,5\times132)\). Explique pourquoi la réponse ne peut pas être négative.

3. Pour \(n\in\mathbb{Z}\), pose \(A=5n+2\) et \(B=7n+3\). Calcule \(7A-5B\) et prouve que \(A,B\) sont premiers entre eux.

Indice, à lire seulement si nécessaire. Le candidat \(5\) de la première question doit aussi diviser chacun des deux nombres. Dans la troisième, une combinaison égale à \(-1\) devient un certificat égal à \(1\) en changeant les deux coefficients de signe.

Correction expliquée : Essai guidé et justification personnelle

1. On vérifie d’abord \(75=5\times15\) et \(130=5\times26\) : \(5\) est un diviseur positif commun. L’identité annoncée est exacte, car

Pour une combinaison égale à \(1\), la première condition est automatique : \(1\) divise tout entier, puisque \(a=1\times a\). Le critère de Bézout est ainsi le cas particulier du certificat pour \(d=1\).

2. Changer le signe du premier nombre ne change pas le PGCD. Le facteur commun \(5\) est positif, donc

3. La combinaison choisie élimine les termes en \(n\) :

Ce que ta réponse doit montrer. Ta réponse distingue « diviseur commun » et « combinaison entière », explique la positivité du PGCD et fournit une identité valable pour tout \(n\), pas seulement des tests numériques.

À toi : À tenter avant de consulter la correction

1. Un élève écrit : « \(2\times168-312=24\), donc \(\operatorname{PGCD}(168,312)=24\). » Sa conclusion est correcte ; sa justification est-elle complète ? Répare-la si nécessaire.

2. Pour \(n\in\mathbb{Z}\), détermine

   \[\operatorname{PGCD}\bigl(8(7n+5),\,8(4n+3)\bigr).\]
   Justifie la valeur pour tous les entiers \(n\), sans te limiter à quelques essais.

Indice, à lire seulement si nécessaire. Dans la deuxième question, commence par chercher une combinaison de \(7n+5\) et \(4n+3\) qui vaut \(1\).

Correction expliquée : Un facteur commun ne suffit pas : il faut contrôler le couple réduit

1. L’égalité est exacte : \(2\times168-312=336-312=24\). Mais il manque la vérification que \(24\) est un diviseur commun. Elle est vraie, puisque \(168=24\times7\) et \(312=24\times13\). Le nombre \(24\) est positif et les coefficients \(2,-1\) sont entiers : le certificat est maintenant complet, donc le PGCD vaut \(24\).

2. Posons \(A=7n+5\) et \(B=4n+3\). On calcule

À toi : Variation : quand la combinaison ne vaut pas \(1\)

Pour \(n\in\mathbb{Z}\), posons \(A=3n+1\) et \(B=5n+1\).

1. Calcule \(5A-3B\) et déduis les deux seules valeurs possibles de \(\operatorname{PGCD}(A,B)\).

2. Détermine laquelle convient selon que \(n\) est pair ou impair.

3. Réfute l’affirmation : « La combinaison vaut \(2\), donc le PGCD vaut toujours \(2\). »

Indice, à lire seulement si nécessaire. Un entier pair s’écrit \(2k\) ; un entier impair s’écrit \(2k+1\), avec \(k\in\mathbb{Z}\).

Correction expliquée : Une borne de divisibilité, puis une distinction de cas

On développe tous les produits :

Si \(n=2k\) est pair, alors \(A=6k+1=2(3k)+1\) et \(B=10k+1=2(5k)+1\) sont impairs. Le nombre \(2\) ne divise pas \(A\) ; ce n’est pas le PGCD. Ainsi \(g=1\).

Si \(n=2k+1\) est impair, alors

L’affirmation proposée est donc fausse. Par exemple, \(n=2\) donne \(A=7\), \(B=11\), dont le PGCD vaut \(1\) ; la combinaison reste bien \(5\times7-3\times11=35-33=2\). Elle fournit seulement un multiple du PGCD.

Pour réparer une erreur : Si tu confonds combinaison et certificat complet

La première erreur est de passer de « \(d=au+bv\) » à « \(d\) est le PGCD » sans vérifier que \(d\) divise les deux nombres.

Rappel sur un exemple plus simple. On peut écrire \(8=8\times1+12\times0\), mais \(8\) ne divise pas \(12\), puisque \(12=8+4\). Le PGCD de \(8\) et \(12\) est \(4\) : les diviseurs communs positifs sont \(1,2,4\).

Nouvel essai. L’identité \(-14+21=7\) permet-elle de prouver que le PGCD de \(14\) et \(21\) vaut \(7\) ? Écris les vérifications manquantes.

Correction. Oui, car \(14=7\times2\) et \(21=7\times3\), puis \(14\times(-1)+21\times1=7\). La divisibilité et la combinaison sont toutes deux établies.

Retour au faux raccourci. Dans \(30\times2-42=18\), la combinaison est exacte, mais \(18\) ne divise pas \(30\) ; on ne possède donc pas de certificat. En revanche, \(6\) divise \(30\) et \(42\), et \(30\times3-42\times2=90-84=6\) : le certificat complet donne le bon PGCD, \(6\).

Pour réparer une erreur : Si le signe ou le paramètre fait échouer ton raisonnement

Premier obstacle : sortir un facteur négatif. L’erreur \(\operatorname{PGCD}(-5a,5b)=-5\operatorname{PGCD}(a,b)\) donne un PGCD négatif. Rappelle-toi que changer le signe d’une donnée ne change pas ses diviseurs. Plus simplement, \(\operatorname{PGCD}(-6,10)=\operatorname{PGCD}(6,10)=2\) ; le signe moins ne sort pas comme un facteur négatif.

Nouvel essai corrigé. Quel est \(\operatorname{PGCD}(-14,21)\) ? On écrit \(-14=7(-2)\) et \(21=7\times3\). Comme \(-2+3=1\), les deux termes du couple réduit sont premiers entre eux : le PGCD vaut \(7\). De retour à \(\operatorname{PGCD}(-420,660)\), le même geste donne \(60\operatorname{PGCD}(-7,11)=60\), car \(3(-7)+2\times11=1\).

Second obstacle : perdre un signe dans l’élimination. Dans \(7(5n+2)-5(7n+3)\), écrire \(14+15\) pour les constantes est la première erreur : \(-5\) multiplie aussi le terme \(3\).

Rappel plus simple. On distribue avant de regrouper :

Correction. Les quatre produits sont \(3\times2n+3\times1-2\times3n-2\times2\), soit \(6n+3-6n-4=-1\).

Retour. Pour la combinaison de l’essai guidé, les constantes donnent bien \(7\times2-5\times3=14-15=-1\). On change les deux coefficients de signe pour obtenir un certificat égal à \(1\) ; une valeur \(-1\) n’est pas un échec.

À toi : À reprendre plus tard, avant de relire

Pour \(n\in\mathbb{Z}\), détermine \(\operatorname{PGCD}\bigl(-9(8n+3),\,9(5n+2)\bigr)\). Donne un certificat direct ou utilise un couple réduit ; une méthode correctement justifiée suffit.

Indice, à lire seulement si nécessaire. La combinaison \(8(5n+2)-5(8n+3)\) est constante.

Correction expliquée : Reprise différée : ne pas perdre le signe

Posons \(A=8n+3\) et \(B=5n+2\). Alors

À retenir : L’essentiel

Une combinaison entière égale à \(1\) prouve la coprimalité. Pour certifier un PGCD \(d>1\), vérifie aussi que \(d\) divise les deux nombres. Un facteur commun \(k\ne0\) sort du PGCD sous la forme \(|k|\). Avec un paramètre, une combinaison constante donne d’abord les diviseurs possibles ; seule une vérification complémentaire décide du PGCD exact.

Avant de commencer : Coprimalité et réduction d’une fraction

1. Calcule \(2\times8-15\). Que prouve ce calcul sur \(8\) et \(15\) ?

2. Divise le numérateur et le dénominateur de \(18/30\) par \(6\). Pourquoi la fraction obtenue a-t-elle la même valeur ?

Correction. On a \(16-15=1\) ; le critère de Bézout donne \(\operatorname{PGCD}(8,15)=1\). Puis

Théorème : Théorème de Gauss

Soient \(a\in\mathbb{Z}\setminus\{0\}\) et \(b,c\in\mathbb{Z}\). Si

Démonstration : Multiplier une identité de Bézout par le bon nombre

L’hypothèse \(\operatorname{PGCD}(a,b)=1\) donne des entiers \(u,v\) vérifiant \(au+bv=1\). Le facteur que l’on souhaite isoler est \(c\) : on multiplie les deux membres par \(c\),

Contre-exemple : Sans la coprimalité, on ne peut pas enlever le facteur

On a \(6\mid4\times3\), puisque \(4\times3=12=6\times2\). Pourtant \(6\) ne divise pas \(3\) : le quotient \(3/6=1/2\) n’est pas entier. La condition qui manque est \(\operatorname{PGCD}(6,4)=1\) ; en réalité ce PGCD vaut \(2\).

Il ne suffit donc pas que \(a\) et \(b\) soient différents ou que \(b\) soit plus petit que \(a\). C’est leur coprimalité qui autorise la conclusion.

Remarque : Le sens inverse, et les cas avec zéro

Si \(a\mid c\), alors \(c=ak\) pour un entier \(k\), donc \(bc=a(bk)\) et \(a\mid bc\). Ce sens est toujours vrai. Sous l’hypothèse \(\operatorname{PGCD}(a,b)=1\), on a ainsi une équivalence : \(a\mid bc\) si et seulement si \(a\mid c\).

Le nombre \(c\) peut être nul : tout entier non nul divise \(0\). Si \(b=0\), la condition \(\operatorname{PGCD}(a,0)=1\) impose \(|a|=1\) ; \(a\) divise alors tout entier. Le théorème ne nécessite donc pas une hypothèse inutile \(b\ne0\) ou \(c\ne0\).

Méthode : Appliquer Gauss sans permuter les rôles

1. Repère le diviseur \(a\), le produit \(bc\) et le facteur \(c\) que tu veux conserver.

2. Vérifie \(a\mid bc\) et \(\operatorname{PGCD}(a,b)=1\) ; un petit certificat de Bézout peut éviter un long calcul de PGCD.

3. Écris la conclusion \(a\mid c\). Si l’énoncé demande une forme pour \(c\), traduis-la par \(c=ak\), avec \(k\in\mathbb{Z}\).

4. S’il s’agit de résoudre une condition, vérifie aussi que toutes les valeurs proposées conviennent.

Gauss ne divise pas les trois nombres d’une relation de divisibilité. Il transforme une divisibilité grâce à une hypothèse précise.

Exemple expliqué : Trouver tous les entiers répondant à une condition

Cherchons les entiers \(m\) tels que \(21\mid8m\). Les rôles sont \(a=21\), \(b=8\) et \(c=m\). L’identité

Réciproquement, pour tout \(k\in\mathbb{Z}\), si \(m=21k\), alors \(8m=8\times21k=21(8k)\) ; le quotient \(8k\) est entier, donc \(21\mid8m\). Les solutions sont exactement les multiples de \(21\), y compris \(0\) et les multiples négatifs.

Corollaire : Deux diviseurs premiers entre eux

Soient \(a,b\in\mathbb{Z}\setminus\{0\}\) premiers entre eux, et \(N\in\mathbb{Z}\). Alors

Démonstration : Où intervient Gauss ?

Supposons \(a\mid N\) et \(b\mid N\). La première condition s’écrit \(N=ak\), avec \(k\in\mathbb{Z}\). La seconde devient donc \(b\mid ak\). Comme \(\operatorname{PGCD}(b,a)=1\), Gauss donne \(b\mid k\). Il existe alors un entier \(\ell\) tel que \(k=b\ell\), d’où \(N=a(b\ell)=(ab)\ell\) : le produit \(ab\) divise \(N\).

Réciproquement, si \(N=(ab)\ell\) avec \(\ell\in\mathbb{Z}\), on peut écrire \(N=a(b\ell)=b(a\ell)\). Les quotients \(b\ell\) et \(a\ell\) sont entiers ; chacun des deux nombres divise \(N\). Ce sens n’a pas besoin de la coprimalité.

Exemple expliqué : Combiner deux informations de divisibilité

Si \(12\mid N\) et \(25\mid N\), alors \(300\mid N\) : les nombres \(12\) et \(25\) sont premiers entre eux, puisque \(25-2\times12=25-24=1\), et leur produit vaut \(300\).

Il serait faux de multiplier deux diviseurs sans vérifier cette condition. Les nombres \(4\) et \(6\) divisent tous deux \(12\), mais leur produit \(24\) ne divise pas \(12\). Leur PGCD vaut \(2\), et non \(1\).

Lemme : Préparer le passage aux puissances

Soient \(a,b,c\in\mathbb{Z}\). Si \(a\) est premier avec \(b\) et premier avec \(c\), alors \(a\) est premier avec \(bc\).

Démonstration : Multiplier deux certificats

On dispose d’entiers \(u,v,s,t\) tels que \(au+bv=1\) et \(as+ct=1\). Le produit de ces deux égalités donne

Corollaire : Coprimalité et puissances

Pour deux entiers \(a,b\) non simultanément nuls et deux entiers \(r,s\geq1\),

Démonstration : Répéter le lemme, puis prouver la réciproque

Si \(\operatorname{PGCD}(a,b)=1\), on a d’abord \(\operatorname{PGCD}(a,b^1)=1\). Supposons, pour un entier \(j\geq1\), que \(a\) est premier avec \(b^j\). Il est aussi premier avec \(b\) par l’hypothèse initiale. Le lemme appliqué au produit \(b^j\times b\) montre qu’il est premier avec \(b^{j+1}\). L’initialisation et cette hérédité prouvent par récurrence que \(\operatorname{PGCD}(a,b^s)=1\) pour tout \(s\geq1\).

Fixons maintenant un tel \(s\). Par symétrie, \(b^s\) est premier avec \(a\). Le même raisonnement, en multipliant cette fois des facteurs égaux à \(a\), donne \(\operatorname{PGCD}(b^s,a^r)=1\) pour tout \(r\geq1\). C’est le sens direct.

Pour la réciproque, supposons \(\operatorname{PGCD}(a^r,b^s)=1\). Soit \(d\) un diviseur positif commun de \(a,b\). Écrivons \(a=dA\) et \(b=dB\), avec \(A,B\in\mathbb{Z}\). Si \(r=1\), \(d\) divise déjà \(a^r=a\). Si \(r\geq2\), on a \(a^r=d(Aa^{r-1})\) et le quotient \(Aa^{r-1}\) est entier ; donc \(d\) divise encore \(a^r\). Le même raisonnement, selon que \(s=1\) ou \(s\geq2\), montre que \(d\) divise \(b^s\). Or le plus grand diviseur positif commun de ces puissances vaut \(1\) : on a donc \(d\leq1\), puis \(d=1\). Ainsi \(a,b\) sont premiers entre eux. Cette distinction évite toute expression \(0^0\) lorsque l’une des bases vaut zéro.

Exemple expliqué : Éviter de calculer d’énormes puissances

L’identité \(2\times8-15=1\) prouve que \(8\) et \(15\) sont premiers entre eux. On en déduit \(\operatorname{PGCD}(8^5,15^7)=1\) sans calculer ces puissances.

La condition sur les exposants compte dans la réciproque. On a \(\operatorname{PGCD}(6^0,9)=\operatorname{PGCD}(1,9)=1\), alors que \(\operatorname{PGCD}(6,9)=3\). Un exposant nul efface l’information portée par la base ; il n’est donc pas inclus dans l’équivalence précédente.

Définition : Une fraction qu’on ne peut plus simplifier

Pour \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^*\), la fraction \(a/b\) est irréductible si aucun entier supérieur ou égal à \(2\) ne divise à la fois \(a\) et \(b\). Cela équivaut à \(\operatorname{PGCD}(a,b)=1\).

On choisit ici un dénominateur positif. Si une fraction a un dénominateur négatif, on multiplie d’abord son numérateur et son dénominateur par \(-1\) ; cela ne change pas sa valeur.

Propriété : Réduire une fraction par le PGCD

Soient \(a\in\mathbb{Z}\), \(b\in\mathbb{N}^*\) et \(d=\operatorname{PGCD}(a,b)\). Alors

Démonstration : Égalité de valeur et absence de facteur commun

Posons \(A=a/d\) et \(B=b/d\). Les nombres \(A,B\) sont entiers ; \(B>0\) et \(d>0\). Comme \(a=dA\) et \(b=dB\), on a \(a/b=(dA)/(dB)=A/B\) par simplification du facteur non nul \(d\).

Si un entier \(h\geq2\) divisait \(A\) et \(B\), on pourrait écrire \(A=hA'\) et \(B=hB'\) avec \(A',B'\in\mathbb{Z}\). Alors \(a=(dh)A'\) et \(b=(dh)B'\). Le nombre \(dh\) serait un diviseur positif commun de \(a,b\), strictement supérieur à \(d\), ce qui contredirait la définition du PGCD. La fraction \(A/B\) est donc irréductible.

Proposition : Unicité de la forme irréductible à dénominateur positif

Si \(a/b\) et \(c/e\) sont deux fractions irréductibles, avec \(a,c\in\mathbb{Z}\) et \(b,e\in\mathbb{N}^*\), et si \(a/b=c/e\), alors \(a=c\) et \(b=e\).

Démonstration : Une application de Gauss dans les deux sens

Multiplions l’égalité \(a/b=c/e\) par le même nombre non nul \(be\) :

Les deux dénominateurs sont positifs. La divisibilité \(b\mid e\) donne \(b\leq e\), et \(e\mid b\) donne \(e\leq b\) ; ainsi \(b=e\). L’égalité \(ae=bc\) devient \(ab=bc\). Divisons les deux membres par \(b\ne0\) :

Exemple expliqué : Réduire une fraction négative et vérifier la conclusion

Pour réduire \(-126/198\), on calcule le PGCD des valeurs absolues :

Pour un numérateur nul, \(\operatorname{PGCD}(0,b)=b\) avec \(b>0\), donc \(0/b=0/1\). La fraction \(0/1\) est irréductible ; \(0/7\) ne l’est pas, car \(7\) divise à la fois \(0\) et \(7\).

Bon réflexe : Prouver l’irréductibilité sans chercher tous les diviseurs

Si le numérateur et le dénominateur sont des expressions, cherche une combinaison entière égale à \(1\). C’est souvent plus court qu’une liste de diviseurs. Par exemple, pour \(n\in\mathbb{N}\), le dénominateur \(3n+2\) est strictement positif, et

À toi : Essai guidé : quatre usages à distinguer

1. Si \(28\mid9m\), utilise \(28-3\times9=1\) pour déduire une forme de \(m\).

2. Si \(9\mid N\) et \(14\mid N\), utilise \(2\times14-3\times9=1\) pour montrer que \(126\mid N\).

3. Réduis \(-84/126\) sachant que leur PGCD vaut \(42\) ; vérifie que la fraction obtenue est irréductible.

4. Déduis de \(2\times8-15=1\) la coprimalité de \(8^2\) et \(15^4\). Cite la condition sur les exposants ; n’effectue pas les puissances.

Indice, à lire seulement si nécessaire. Dans les deux premières questions, indique d’abord les deux nombres qui doivent être premiers entre eux.

Correction expliquée : Ne pas employer un même mot pour quatre raisonnements différents

1. \(28-3\times9=28-27=1\) donne \(\operatorname{PGCD}(28,9)=1\). Avec \(28\mid9m\), Gauss donne \(28\mid m\), soit \(m=28k\) avec \(k\in\mathbb{Z}\). Toutes ces valeurs conviennent, car \(9m=9(28k)=28(9k)\).

2. \(2\times14-3\times9=28-27=1\) montre \(\operatorname{PGCD}(9,14)=1\). Le corollaire du produit donne \(9\times14=126\mid N\). Plus explicitement, \(N=9k\) et \(14\mid9k\) ; Gauss donne \(14\mid k\), donc \(k=14\ell\) et \(N=126\ell\) avec \(\ell\in\mathbb{Z}\).

3. On a \(-84=42\times(-2)\) et \(126=42\times3\), donc

4. On calcule d’abord \(2\times8-15=16-15=1\). C’est un certificat entier, donc \(\operatorname{PGCD}(8,15)=1\). Les exposants \(2\) et \(4\) sont des entiers strictement positifs : le corollaire des puissances s’applique et donne \(\operatorname{PGCD}(8^2,15^4)=1\). La condition porte sur les bases avant de passer aux puissances ; le seul fait que les exposants soient différents ne prouve rien.

À toi : À tenter avant de consulter la correction

1. Décris tous les entiers \(t\) tels que \(35\mid12t\).

2. Sans développer les puissances, justifie que \(12^3/35^2\) est irréductible.

3. Si \(15\mid N\) et \(28\mid N\), peut-on conclure \(420\mid N\) ? Justifie, sans supposer que deux nombres différents sont automatiquement premiers entre eux.

Indice, à lire seulement si nécessaire. Pour les deux premières questions, \(3\times12-35=1\). Pour la dernière, tu peux vérifier \(15\times15-28\times8=1\).

Correction expliquée : Applications avec moins de guidage

1. \(3\times12-35=36-35=1\) prouve \(\operatorname{PGCD}(35,12)=1\). Gauss donne \(35\mid t\), donc \(t=35k\) avec \(k\in\mathbb{Z}\). Réciproquement, \(12(35k)=35(12k)\) ; ces valeurs satisfont toutes la condition.

2. On vient de prouver que \(12,35\) sont premiers entre eux. Les exposants \(3\) et \(2\) sont strictement positifs ; le corollaire sur les puissances donne \(\operatorname{PGCD}(12^3,35^2)=1\). Le dénominateur \(35^2\) étant positif, la fraction est irréductible. Il n’est pas nécessaire de calculer les puissances pour prouver ce résultat.

3. Le calcul \(15\times15-28\times8=225-224=1\) fournit un certificat de coprimalité. Le corollaire du produit s’applique donc à \(15\) et \(28\). Leur produit est \(15\times28=420\) ; on conclut \(420\mid N\).

À toi : Justifier et réfuter : quelles conditions sont indispensables ?

1. Réfute : « Si \(6\mid4t\), alors \(6\mid t\). » Propose ensuite une conclusion correcte de la forme \(d\mid t\).

2. Pourquoi la preuve de Gauss multiplie-t-elle l’identité de Bézout par \(c\) et non par un nombre choisi au hasard ?

3. Les fractions \(1/2\) et \((-1)/(-2)\) ont la même valeur. Pourquoi ne contredisent-elles pas l’unicité démontrée ?

4. Que manque-t-il dans : « \(4\) et \(6\) divisent \(12\), donc \(24\) divise \(12\) » ? Pourquoi \(\operatorname{PGCD}(6^0,9)=1\) ne prouve-t-il pas que \(6\) et \(9\) sont premiers entre eux ?

Indice, à lire seulement si nécessaire. Pour la première question, essaie \(t=3\). Puis écris \(4t=6k\) et divise les deux membres par \(2\).

Correction expliquée : Changer une hypothèse change la conclusion

1. Avec \(t=3\), on a \(4t=12=6\times2\), mais \(6\) ne divise pas \(3\). La coprimalité nécessaire manque : \(\operatorname{PGCD}(6,4)=2\).

Une conclusion correcte est \(3\mid t\). En effet, \(6\mid4t\) signifie \(4t=6k\) pour un entier \(k\). Divisons les deux membres par le coefficient non nul \(2\) :

2. Multiplier \(au+bv=1\) par \(c\) fait apparaître le produit \(bc\), sur lequel porte l’hypothèse de divisibilité, et le nombre \(c\) que l’on veut atteindre : \(acu+bcv=c\). Ce choix relie exactement les deux hypothèses à l’objectif.

3. La proposition d’unicité impose des dénominateurs positifs. Le dénominateur \(-2\) n’en respecte pas l’hypothèse. Après changement des deux signes, \((-1)/(-2)\) devient \(1/2\), la même forme normalisée.

4. Le produit des deux diviseurs ne peut être utilisé ici : \(\operatorname{PGCD}(4,6)=2\), et non \(1\). De fait, \(12/24=1/2\) n’est pas un entier. Quant à \(6^0=1\), l’exposant zéro est exclu de la réciproque du corollaire des puissances. Le PGCD de \(1\) et \(9\) vaut bien \(1\), mais celui de \(6\) et \(9\) vaut \(3\). Dans les deux cas, la conclusion échoue parce qu’une hypothèse précise a disparu.

Ce que ta réponse doit montrer. Ta réponse fournit un contre-exemple calculé, nomme l’hypothèse absente et justifie une réparation correcte. Dans la preuve, elle explique l’utilité de la multiplication ; pour l’unicité, elle identifie la condition de signe.

Pour réparer une erreur : Si tu as appliqué Gauss trop vite

La première ligne à contrôler est « \(a\mid bc\), donc \(a\mid c\) ». Demande immédiatement : a-t-on prouvé que \(a\) et \(b\) sont premiers entre eux ?

Exemple plus simple. Si \(2\mid3t\), on peut conclure \(2\mid t\), car \(3-2=1\) prouve \(\operatorname{PGCD}(2,3)=1\).

Nouvel essai. Si \(3\mid2t\), peut-on conclure \(3\mid t\) ?

Correction. Oui : \(3-2=1\) prouve \(\operatorname{PGCD}(3,2)=1\). Les deux hypothèses de Gauss sont satisfaites, donc \(3\mid t\).

Retour. Pour \(6\mid4t\), le PGCD de \(6\) et \(4\) n’est pas \(1\). Le nouvel essai s’applique seulement après la réduction expliquée dans la correction précédente, qui donne \(3\mid2t\). La conclusion correcte est \(3\mid t\), pas \(6\mid t\).

Pour réparer une erreur : Si tu as soustrait au lieu de diviser dans une fraction

Le passage erroné \(14/21=(14-7)/(21-7)=7/14\) ne conserve pas la valeur d’une fraction. Une réduction simplifie un facteur commun, pas une quantité retranchée.

Rappel corrigé. \(6/9=(3\times2)/(3\times3)=2/3\) : le même facteur non nul \(3\) est simplifié.

Nouvel essai. Réduis \(10/15\) et contrôle l’égalité obtenue.

Correction. \(10/15=(5\times2)/(5\times3)=2/3\). On vérifie les produits croisés : \(10\times3=30\) et \(15\times2=30\). Comme \(3-2=1\), la fraction \(2/3\) est irréductible.

Retour. La bonne réduction est \(14/21=(7\times2)/(7\times3)=2/3\). La valeur \(7/14=1/2\) était différente : \(2\times2=4\), tandis que \(3\times1=3\).

Pour réparer une erreur : Si tu as oublié une condition d’un corollaire

Produit de diviseurs. La première erreur serait de déduire \(ab\mid N\) de deux divisibilités sans vérifier \(\operatorname{PGCD}(a,b)=1\). Pour reprendre simplement, \(3\) et \(5\) divisent \(30\), et \(2\times3-5=1\) prouve leur coprimalité : \(15\) divise bien \(30\).

Nouvel essai corrigé. Si \(4\mid N\) et \(9\mid N\), peut-on multiplier les deux diviseurs ? Oui : \(9-2\times4=1\) prouve \(\operatorname{PGCD}(4,9)=1\), donc \(36\mid N\). De retour au couple \(4,6\), ce contrôle échoue puisque leur PGCD vaut \(2\) ; on ne peut pas conclure \(24\mid N\) de ces seules données.

Puissances. L’erreur serait de remonter de \(\operatorname{PGCD}(6^0,9)=1\) à la coprimalité de \(6,9\). Le rappel est précis : la réciproque utilise des exposants au moins égaux à \(1\), afin que tout diviseur d’une base divise encore sa puissance sans que la base disparaisse.

Nouvel essai corrigé. Si \(\operatorname{PGCD}(a^2,b^3)=1\), que peut-on conclure ? Les exposants \(2,3\) sont positifs : tout diviseur positif commun de \(a,b\) divise \(a^2,b^3\), donc il vaut \(1\) ; ainsi \(\operatorname{PGCD}(a,b)=1\). De retour à l’exposant zéro, \(6^0=1\) a effacé tous les diviseurs de \(6\) ; le même raisonnement ne s’applique plus.

À toi : À reprendre plus tard, avant relecture

1. Un entier \(z\) vérifie \(18\mid25z\) et \(5\mid z\). Montre que \(90\mid z\).

2. La fraction \(18^2/25^3\) est-elle irréductible ? Justifie sans développer les puissances.

3. Réduis \(-195/286\) et explique pourquoi la forme obtenue est irréductible.

Indice, à lire seulement si nécessaire. Tu peux vérifier \(7\times18-5\times25=1\) et \(2\times18-7\times5=1\). Pour la fraction numérique, Euclide commence par \(286=195+91\).

Correction expliquée : Reprise différée

1. Le calcul \(7\times18-5\times25=126-125=1\) prouve \(\operatorname{PGCD}(18,25)=1\). Avec \(18\mid25z\), Gauss donne \(18\mid z\). On sait aussi \(5\mid z\), et \(2\times18-7\times5=36-35=1\) prouve \(\operatorname{PGCD}(18,5)=1\). Le corollaire du produit donne donc \(18\times5=90\mid z\).

2. L’identité précédente montre \(\operatorname{PGCD}(18,25)=1\). Les exposants \(2,3\) sont strictement positifs : \(\operatorname{PGCD}(18^2,25^3)=1\). Le dénominateur est positif, donc la fraction est irréductible.

3. Les divisions donnent

À retenir : L’essentiel

Gauss permet d’enlever un facteur d’un produit divisible seulement après vérification de la coprimalité avec le diviseur. Deux diviseurs premiers entre eux peuvent être multipliés. La coprimalité est conservée par des puissances d’exposants positifs. Une fraction se réduit par son PGCD ; sa forme irréductible à dénominateur positif est unique.

Définition : Les inconnues doivent être entières

Dans cette unité, une équation diophantienne linéaire à deux inconnues est une équation

Remarque : Les outils antérieurs utilisés ici

Pour deux entiers \(a,b\) non simultanément nuls, \(d=\operatorname{PGCD}(a,b)\) est positif et divise \(a\) et \(b\). Tout diviseur commun divise aussi \(d\). Si un argument est nul, le PGCD est directement la valeur absolue de l’autre. Sinon, on applique Euclide aux valeurs absolues : le PGCD est le diviseur de la dernière division, celle dont le reste est nul. On le décrit aussi comme le dernier reste non nul, en comptant le diviseur initial lorsque la première division est déjà exacte. L’identité de Bézout, déjà démontrée, fournit \(u,v\in\mathbb{Z}\) tels que \(au+bv=d\).

Le couple réduit \(A=a/d\), \(B=b/d\) est formé d’entiers premiers entre eux : \(\operatorname{PGCD}(A,B)=1\). Le théorème de Gauss, déjà démontré, affirme : si \(m\mid pq\) et \(\operatorname{PGCD}(m,p)=1\), alors \(m\mid q\). Enfin, \(m\mid q\) signifie qu’il existe un entier \(k\) tel que \(q=mk\). Les coefficients de Bézout et les paramètres peuvent être négatifs.

Avant de commencer : Une obstruction que l’on peut voir avant de calculer

Les équations \(35x+21y=5\) et \(35x+21y=14\) peuvent-elles avoir des solutions entières ? Cherche d’abord un diviseur commun aux deux coefficients.

Correction expliquée : L’intégralité change la question

Pour des entiers \(x,y\), \(35x+21y=7(5x+3y)\) est divisible par \(7\). Il ne peut donc pas être égal à \(5\) : la première équation n’a aucune solution entière. La seconde en possède : \((1,-1)\) convient car \(35\times1+21\times(-1)=35-21=14\). Si tu avais choisi une valeur fractionnaire pour \(x\), reviens à la définition : ici les deux coordonnées doivent être entières.

Théorème : Critère d’existence

Soient \(a,b,c\in\mathbb{Z}\), avec \((a,b)\ne(0,0)\), et \(d=\operatorname{PGCD}(a,b)\). Alors

Démonstration : Deux sens, deux rôles

Nécessité. Puisque \(d\mid a\) et \(d\mid b\), on peut écrire \(a=dA\) et \(b=dB\) avec \(A,B\in\mathbb{Z}\). Si \((x,y)\) est une solution entière,

Suffisance. Supposons \(d\mid c\), donc \(c=dh\) pour un entier \(h\). Bézout donne \(au+bv=d\) avec \(u,v\) entiers. En multipliant les deux membres par \(h\),

Exemple expliqué : Une solution particulière construite par Bézout

Cherchons d’abord une solution de \(28x+44y=12\). Euclide donne

Méthode : Décider et construire avant de chercher toutes les solutions

Calcule \(d=\operatorname{PGCD}(a,b)\), en utilisant les valeurs absolues si les coefficients sont négatifs. Si \(d\) ne divise pas \(c\), conclus immédiatement à l’absence de solution entière. Sinon, remonte Euclide pour obtenir une combinaison égale à \(d\), puis multiplie les deux coefficients par l’entier \(c/d\). Si un coefficient de l’équation est négatif, reporte correctement son signe dans la coordonnée correspondante. Contrôle enfin le couple par substitution dans l’équation initiale. Une solution évidente déjà vérifiée peut remplacer la remontée, mais pas le contrôle.

À toi : Essai guidé : existence et construction

Pour \(24x+42y=18\) :

1. termine Euclide à partir de \(42=24+18\) ;

2. exprime le PGCD en fonction de \(24\) et \(42\) ;

3. construis et vérifie une solution ;

4. explique pourquoi remplacer \(18\) par \(20\) changerait la conclusion.

Indice, à lire seulement si nécessaire. Le facteur qui transforme le PGCD en \(18\) multiplie les deux coefficients de Bézout.

Correction expliquée : Les deux coefficients sont multipliés

On a \(24=18+6\) et \(18=3\times6+0\), donc le PGCD est \(6\). Puis

Ce que ta réponse doit montrer. Ta justification d’impossibilité doit mentionner le diviseur commun et le fait que toute combinaison entière des coefficients est divisible par ce nombre.

À toi : Essaie avant de lire

Décide si \(36x-60y=24\) possède des solutions entières et donne un couple solution. Que devient la réponse avec second membre \(25\) ?

Indice, à lire seulement si nécessaire. Calcule le PGCD de \(36\) et \(60\). Dans \(36x-60y\), le coefficient de \(y\) est \(-60\).

Correction expliquée : Le signe appartient au coefficient

Euclide : \(60=36+24\), \(36=24+12\), \(24=2\times12\) ; le PGCD vaut \(12\). Le nombre \(24\) est divisible par \(12\), et

Pour réparer une erreur : Une solution réelle n’est pas une solution entière

Une réponse propose \((1/14,0)\) pour \(14x+21y=1\). L’égalité est vraie, mais la première erreur est de ne plus imposer \(x\in\mathbb{Z}\).

Rappel : si les coefficients sont divisibles par \(d\), chaque combinaison à coefficients entiers est divisible par \(d\). Exemple plus simple : \(6x+10y=3\) est impossible dans \(\mathbb{Z}^2\), car \(6x+10y=2(3x+5y)\) est pair.

Nouvel essai : \(10x+15y=5\) est-il possible dans \(\mathbb{Z}^2\) ? Donne un couple et explique pourquoi l’obstruction précédente ne suffit plus.

Correction expliquée : Réparer puis revenir au départ

Le PGCD de \(10\) et \(15\) vaut \(5\), et \(5\) divise le second membre : une solution existe. Le couple \((-1,1)\) donne \(-10+15=5\). Les coefficients ne sont pas tous deux pairs ; l’argument de parité du cas \(6x+10y=3\) ne s’applique donc pas. Au problème initial, \(14\) et \(21\) sont divisibles par \(7\), mais pas \(1\) : aucune solution entière, même si des solutions réelles existent.

À toi : À reprendre plus tard, sans relire l’exemple

Retrouve si \(22x+34y=14\) est soluble dans \(\mathbb{Z}^2\), puis construis une solution à partir d’Euclide.

Indice, à lire seulement si nécessaire. Le dernier reste non nul est \(2\) ; le second membre vaut \(7\) fois ce reste.

Correction expliquée : Une identité puis le bon facteur

Les divisions sont \(34=22+12\), \(22=12+10\), \(12=10+2\) et \(10=5\times2\). Le PGCD est \(2\) et divise \(14\). La remontée donne

Avant de commencer : Un seul paramètre ou deux paramètres indépendants ?

Le couple \((2,-1)\) vérifie \(3x+5y=1\). Les couples

Correction expliquée : Les variations doivent se compenser

En développant,

Théorème : Toutes les solutions à partir d’une solution particulière

Soient \(a,b\) deux entiers non nuls, \(c\in\mathbb{Z}\), \(d=\operatorname{PGCD}(a,b)\), \(A=a/d\) et \(B=b/d\). Si \((x_0,y_0)\in\mathbb{Z}^2\) vérifie \(ax_0+by_0=c\), alors toutes les solutions entières, et seulement elles, sont

Démonstration : Pourquoi aucune solution n’est oubliée

Soit \((x,y)\) une solution entière. Soustrayons l’égalité de la solution particulière :

Réciproquement, pour tout \(k\in\mathbb{Z}\), \(x_0+Bk\) et \(y_0-Ak\) sont entiers, et

Exemple expliqué : Pourquoi le paramètre décrit toutes les solutions

Résolvons \(28x+44y=12\) dans \(\mathbb{Z}^2\). Le couple \((2,-1)\) convient, car

Réciproquement, pour tout entier \(k\), les deux coordonnées sont entières et

Méthode : Une rédaction qui établit vraiment « toutes »

Après le critère d’existence et une solution particulière :

1. soustrais l’équation de la solution particulière à celle d’une solution quelconque ;

2. réduis par le PGCD avant d’utiliser Gauss ;

3. justifie la divisibilité et introduis un paramètre entier ;

4. retrouve l’autre coordonnée avec ce même paramètre ;

5. vérifie réciproquement la famille dans l’équation de départ.

Le théorème permet ensuite de raccourcir une rédaction en citant ses hypothèses, mais savoir reconstruire ces étapes évite les erreurs de signe et les familles incomplètes.

À toi : Essai guidé : reprendre la solution déjà construite

On a trouvé \((6,-3)\) pour \(24x+42y=18\). Décris toutes les solutions. Écris d’abord l’équation satisfaite par \(x-6\) et \(y+3\), puis réduis par le PGCD.

Indice, à lire seulement si nécessaire. Après division par \(6\), les coefficients sont \(4\) et \(7\), premiers entre eux.

Correction expliquée : Les pas ne sont ni 42 ni 24

Soustraire \(24\times6+42(-3)=18\) donne \(24(x-6)+42(y+3)=0\). La division par \(6\ne0\) conduit à \(4(x-6)=-7(y+3)\). Alors \(7\mid4(x-6)\) et \(\operatorname{PGCD}(7,4)=1\), donc \(x-6=7k\) pour un entier \(k\). En remplaçant, \(4\times7k=-7(y+3)\) ; la division par \(7\ne0\) donne \(4k=-(y+3)\), puis \(y=-3-4k\). Réciproquement,

À toi : Tentative avec un coefficient et un second membre négatifs

Résous entièrement \(18x-30y=-6\) dans \(\mathbb{Z}^2\). Tu peux chercher une petite solution après réduction. Justifie la totalité de ta famille, puis vérifie-la.

Indice, à lire seulement si nécessaire. La réduction donne \(3x-5y=-1\) ; \((3,2)\) convient.

Correction expliquée : Les deux coordonnées peuvent augmenter ensemble

Le PGCD de \(18\) et \(-30\) est celui de \(18\) et \(30\), soit \(6\) : \(30=18+12\), \(18=12+6\), \(12=2\times6\). Il divise \(-6\). Diviser les deux membres de l’équation par \(6\) donne \(3x-5y=-1\). Le couple \((3,2)\) convient car \(3\times3-5\times2=9-10=-1\).

Pour toute solution,

Ce que ta réponse doit montrer. Une preuve complète doit justifier l’existence, le coefficient réduit, l’application de Gauss, le paramètre commun et la réciproque. Le contrôle de deux valeurs de \(k\) ne remplace pas cette dernière.

Question d’élève : Deux réponses différentes peuvent-elles être correctes ?

Oui. Pour \(28x+44y=12\), les familles

Corollaire : Second membre nul

Si \(a,b\) sont non nuls et \(d=\operatorname{PGCD}(a,b)\), les solutions de \(ax+by=0\) sont

Démonstration : Une particulière immédiate

Le couple \((0,0)\) convient ; le théorème précédent s’applique avec \(x_0=y_0=0\). Par exemple, \(12x-20y=0\) a pour solutions \((5k,3k)\), \(k\in\mathbb{Z}\) : après division par \(4\), \(3x=5y\) ; Gauss impose \(x=5k\), puis \(y=3k\). La vérification donne \(12(5k)-20(3k)=12\times5k-20\times3k=60k-60k=0\).

Propriété : Quand un coefficient est nul

Les formules précédentes ont supposé \(a\) et \(b\) non nuls. Les cas restants se lisent directement :

• si \(a=0\) et \(b\ne0\), l’équation est \(by=c\) : elle n’a pas de solution si \(b\nmid c\) ; sinon \(y=c/b\) et \(x\) est un entier quelconque ;

• si \(a\ne0\) et \(b=0\), il faut \(a\mid c\) ; alors \(x=c/a\) et \(y\) est un entier quelconque ;

• si \(a=b=0\), tous les couples entiers conviennent lorsque \(c=0\), et aucun lorsque \(c\ne0\).

Démonstration : Pourquoi il n’y a pas de division par zéro

Pour \(a=0\), on résout \(by=c\) en divisant par \(b\ne0\) : \(y=c/b\). Cette valeur est entière exactement lorsque \(b\mid c\) ; \(x\) ne figure plus dans l’égalité. Le deuxième cas échange les rôles. Dans le troisième, le membre de gauche est toujours \(0\) : l’égalité devient \(0=c\). On ne calcule pas \(\operatorname{PGCD}(0,0)\), qui n’est pas défini dans ce cours.

Exemple expliqué : Lire les cas nuls sans utiliser une formule hors de ses conditions

\(0x-7y=21\) donne \(y=21/(-7)=-3\) : les solutions sont \((k,-3)\), \(k\in\mathbb{Z}\). \(0x+0y=5\) n’a aucune solution. Pour \(0x+0y=0\), toute paire d’entiers convient ; il faut deux paramètres indépendants, \((k,\ell)\) avec \(k,\ell\in\mathbb{Z}\), car aucune relation ne lie les coordonnées.

Pour réparer une erreur : Une famille vraie mais incomplète

Pour \(6x+9y=3\), une copie annonce seulement \(x=-1+9k\), \(y=1-6k\). Les couples proposés conviennent, mais la première erreur est d’avoir utilisé les coefficients \(9\) et \(6\) au lieu des coefficients réduits \(3\) et \(2\).

Rappel : diviser les deux membres par \(3\ne0\) donne \(2x+3y=1\). Le couple \((-1,1)\) convient. Soustraire son égalité donne \(2(x+1)=-3(y-1)\) ; Gauss, avec \(\operatorname{PGCD}(2,3)=1\), impose \(x=-1+3t\), puis \(y=1-2t\). Le couple \((2,-1)\), obtenu pour \(t=1\), est perdu par la famille erronée, car \(-1+9k=2\) imposerait \(k=1/3\notin\mathbb{Z}\).

Nouvel essai : décris toutes les solutions de \(12x+18y=6\), puis vérifie que \((2,-1)\) en fait partie.

Correction expliquée : Le PGCD règle la taille du pas

La division par \(6\ne0\) redonne \(2x+3y=1\). En partant de \((-1,1)\), la différence donne \(2(x+1)=-3(y-1)\). Puisque \(3\) et \(2\) sont premiers entre eux, \(x=-1+3t\) pour \(t\in\mathbb{Z}\) ; la substitution puis la division par \(3\ne0\) donnent \(y=1-2t\). Réciproquement,

À toi : À reprendre plus tard : reconstruis toute la preuve

Résous \(15x+21y=6\) dans \(\mathbb{Z}^2\). Justifie pourquoi tes deux coordonnées utilisent un seul paramètre et contrôle la famille.

Indice, à lire seulement si nécessaire. Réduis par \(3\) ; une petite particulière est \((-1,1)\).

Correction expliquée : Soustraction, Gauss, réciproque

Le PGCD vaut \(3\), car \(21=15+6\), \(15=2\times6+3\), \(6=2\times3\). La réduction donne \(5x+7y=2\), et \(5(-1)+7\times1=2\). Une solution quelconque vérifie donc \(5(x+1)=-7(y-1)\). De \(7\mid5(x+1)\) et \(\operatorname{PGCD}(7,5)=1\), on déduit \(x+1=7k\), \(k\in\mathbb{Z}\). Substituer puis diviser par \(7\) donne \(5k=-(y-1)\), donc \(y=1-5k\). Réciproquement,

Avant de commencer : Entier, positif, strictement positif

Pour \(k\in\mathbb{Z}\), résous \(-3k\ge-8\), puis \(2+5k>0\). Attention : \(\mathbb{N}\) contient \(0\), tandis qu’une quantité strictement positive doit être au moins égale à \(1\) lorsqu’elle est entière.

Correction expliquée : Le sens de l’inégalité et l’arrondi entier

Diviser \(-3k\ge-8\) par \(-3<0\) renverse le sens : \(k\le8/3\). Comme \(2<8/3<3\) et \(k\) est entier, cela équivaut à \(k\le2\). Pour \(2+5k>0\), soustraire \(2\) donne \(5k>-2\), puis diviser par \(5>0\) donne \(k>-2/5\). Les entiers qui conviennent sont donc \(k\ge0\). On ne remplace pas une borne réelle par son arrondi habituel : on cherche le premier ou le dernier entier autorisé.

Méthode : Des contraintes sur les coordonnées aux contraintes sur le paramètre

Commence par la famille entière complète. Remplace \(x\) et \(y\) par leurs expressions en \(k\) dans toutes les conditions. Résous chaque inégalité, en renversant son sens si tu divises par un nombre négatif. Garde ensuite les valeurs entières communes aux intervalles obtenus. Calcule les couples correspondants et vérifie l’équation initiale ainsi que les contraintes. Des coefficients positifs et un total positif donnent souvent un nombre fini de possibilités ; des coefficients de signes opposés peuvent laisser une infinité de couples naturels.

Exemple expliqué : Deux formats de boîtes et un total imposé

Un atelier range \(330\) marqueurs dans des boîtes de \(14\) ou de \(22\) marqueurs, entièrement remplies. On note \(x\) le nombre de boîtes de \(14\) et \(y\) le nombre de boîtes de \(22\). On cherche

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

Lecture du schéma. La droite représente les solutions réelles de l’équation. Les trois points marqués sont les seules solutions à coordonnées entières et non négatives, comme l’a établi le paramètre \(k\). La figure aide à voir le pas \((+11,-7)\) ; elle ne remplace pas la preuve d’exhaustivité.

À toi : Essai guidé : transformer toutes les bornes

Cherche les couples \((x,y)\in\mathbb{N}^2\) vérifiant \(8x+14y=100\). Pars de \((2,6)\), puis traite aussi la condition supplémentaire \(x\le5\).

Indice, à lire seulement si nécessaire. Le PGCD vaut \(2\) ; les pas réduits sont \(+7\) et \(-4\).

Correction expliquée : Croiser les deux conditions

Le PGCD vaut \(2\) : \(14=8+6\), \(8=6+2\), \(6=3\times2\). La particulière est vérifiée par \(8\times2+14\times6=16+84=100\). Les solutions entières sont donc \(x=2+7k\), \(y=6-4k\), \(k\in\mathbb{Z}\). La substitution donne

Pour \(x\ge0\), on obtient \(7k\ge-2\), puis \(k\ge-2/7\), soit \(k\ge0\) pour un entier. Pour \(y\ge0\), on obtient \(-4k\ge-6\), puis \(k\le6/4=3/2\), soit \(k\le1\). Ainsi \(k=0\) ou \(1\) : les couples naturels sont \((2,6)\) et \((9,2)\). Leurs totaux sont \(16+84=100\) et \(72+28=100\). La condition supplémentaire \(x\le5\) ne garde que \((2,6)\).

À toi : Une condition supplémentaire change la sélection

Décris les solutions naturelles de \(12x+20y=160\), puis celles dont les deux coordonnées sont strictement positives. Parmi ces couples, lesquels satisfont aussi \(x+y=10\) ? Justifie chaque sélection en écrivant les bornes correspondantes sur le paramètre ; explique en particulier pourquoi un couple disparaît quand on exige des coordonnées strictement positives.

Indice, à lire seulement si nécessaire. Après réduction, une particulière est \((0,8)\).

Correction expliquée : Équation, positivité, puis contrainte supplémentaire

Le PGCD est \(4\) : \(20=12+8\), \(12=8+4\), \(8=2\times4\). La réduction donne \(3x+5y=40\). Le couple \((0,8)\) convient et les coefficients \(3,5\) sont premiers entre eux. Toutes les solutions sont \(x=5k\), \(y=8-3k\), \(k\in\mathbb{Z}\) ; le contrôle initial donne

Pour \(x,y\ge1\), la première condition impose \(k\ge1\) et la seconde \(8-3k\ge1\), donc \(k\le7/3\), soit \(k\le2\). Il reste \((5,5)\) et \((10,2)\). Enfin, \(x+y=5k+8-3k=8+2k\). Imposer \(8+2k=10\), soustraire \(8\) puis diviser par \(2\ne0\) donne \(k=1\) : seul \((5,5)\) convient.

Ce que ta réponse doit montrer. Explique séparément le domaine de départ, les bornes sur le paramètre et chaque restriction nouvelle ; ne supprime pas le couple à coordonnée nulle avant d’avoir demandé une positivité stricte.

Remarque : Avec des signes opposés, la liste peut être infinie

Pour \(18x-30y=-6\), on a établi \(x=3+5k\), \(y=2+3k\). Les conditions \(x,y\ge0\) donnent

Pour réparer une erreur : Une inégalité renversée dans le mauvais sens

Dans \(15-7k\ge0\), une copie écrit \(-7k\ge-15\), puis \(k\ge15/7\). La première erreur est cette dernière ligne : diviser par \(-7\) renverse le sens.

Rappel plus simple : \(5-2k\ge0\) donne \(-2k\ge-5\), puis \(k\le5/2\) ; pour \(k\in\mathbb{Z}\), cela signifie \(k\le2\). Vérification : \(k=2\) donne \(1\ge0\) ; \(k=3\) donne \(-1\not\ge0\).

Nouvel essai : résous \(9-4k>0\) pour \(k\in\mathbb{Z}\), sans confondre borne stricte et arrondi.

Correction expliquée : Contrôler un entier juste avant et juste après la borne

On soustrait \(9\) : \(-4k>-9\). On divise par \(-4<0\) : \(k<9/4\). Comme \(2<9/4<3\), les entiers autorisés sont \(k\le2\). En effet \(9-4\times2=1>0\), tandis que \(9-4\times3=-3\) ne convient pas. Au problème des boîtes, \(15-7k\ge0\) donne donc \(k\le15/7\), puis \(k\le2\), et non \(k\ge3\).

À toi : Reprise différée : une liste finie avec positivité stricte

Sans relire l’exemple, trouve tous les couples d’entiers strictement positifs tels que \(9x+15y=180\). Justifie qu’aucun couple n’a été oublié.

Indice, à lire seulement si nécessaire. Le couple \((0,12)\) est utile pour résoudre dans \(\mathbb{Z}^2\), même s’il ne respecte pas ensuite la positivité stricte.

Correction expliquée : La particulière n’a pas besoin de satisfaire les contraintes finales

Le PGCD est \(3\) ; \(15=9+6\), \(9=6+3\), \(6=2\times3\). La réduction donne \(3x+5y=60\), dont \((0,12)\) est une solution. Le théorème donne toutes les solutions \(x=5k\), \(y=12-3k\), \(k\in\mathbb{Z}\). Le contrôle initial est

Pour \(x\ge1\), \(5k\ge1\) impose \(k\ge1\). Pour \(y\ge1\), \(12-3k\ge1\) équivaut à \(-3k\ge-11\), puis à \(k\le11/3\) ; pour un entier, \(k\le3\). Donc \(k=1,2,3\), d’où \((5,9)\), \((10,6)\) et \((15,3)\). Les contrôles sont \(45+135=180\), \(90+90=180\) et \(135+45=180\). Le théorème décrit toutes les solutions entières, puis les inégalités ont gardé exactement tous les paramètres autorisés : c’est la justification d’exhaustivité.

À retenir : Le fil d’une résolution

Pour \(ax+by=c\), commence par le domaine et les éventuels coefficients nuls. Si \((a,b)\ne(0,0)\), calcule \(d=\operatorname{PGCD}(a,b)\) : une solution entière existe exactement lorsque \(d\mid c\). Construis et contrôle une particulière. Si \(a,b\ne0\), la famille complète est

Remarque : Le sens d’une congruence

Pour un entier \(n\ge2\), \(s\equiv t\;[n]\) signifie \(n\mid s-t\) : il existe \(q\in\mathbb{Z}\) tel que \(s-t=nq\). Les nombres \(s\) et \(t\) ont le même reste dans la division euclidienne par \(n\). La classe de \(r\) modulo \(n\) désigne ici l’ensemble des entiers \(r+kn\), \(k\in\mathbb{Z}\) ; on peut choisir son unique représentant entre \(0\) et \(n-1\).

On peut additionner les mêmes nombres ou multiplier par un même entier les deux membres d’une congruence : un multiple de \(n\) reste un multiple de \(n\). En revanche, diviser demande une condition ou un changement de module ; c’est l’un des points centraux de cette unité.

Nous utiliserons aussi deux résultats déjà démontrés : Bézout donne \(\operatorname{PGCD}(a,n)=1\Longleftrightarrow au+nv=1\) pour certains \(u,v\in\mathbb{Z}\) ; Gauss donne \(n\mid az\) et \(\operatorname{PGCD}(n,a)=1\Longrightarrow n\mid z\). Le PGCD est positif, et le couple \((a/\operatorname{PGCD}(a,n),n/\operatorname{PGCD}(a,n))\) est coprime.

Avant de commencer : Un produit égal à 1 à un multiple près

Pourquoi \(3\) permet-il d’inverser la multiplication par \(7\) modulo \(10\) ? Peut-on trouver un entier \(r\) tel que \(6r\equiv1\;[10]\) ?

Correction expliquée : Un succès et une impossibilité

On a \(7\times3=21=2\times10+1\), donc \(7\times3\equiv1\;[10]\). Multiplier ensuite par \(3\) permet ainsi de retrouver la valeur de départ modulo \(10\) après une multiplication par \(7\). Pour \(6r\equiv1\;[10]\), il faudrait \(6r-1=10q\) avec \(q\in\mathbb{Z}\). Le membre de gauche est impair, celui de droite pair : c’est impossible. Le fait que \(6\) soit non nul ne suffit donc pas à autoriser son inversion modulo \(10\).

Définition : Inverse modulo n

Pour \(a\in\mathbb{Z}\) et \(n\ge2\), un inverse de \(a\) modulo \(n\) est un entier \(u\) tel que

Théorème : Existence et unicité modulo n

Un entier \(a\) possède un inverse modulo \(n\ge2\) si et seulement si \(\operatorname{PGCD}(a,n)=1\). Lorsque c’est le cas, tous ses inverses sont congrus entre eux modulo \(n\) : il existe un unique inverse parmi \(0,1,\ldots,n-1\).

Démonstration : Bézout pour exister, Gauss pour être unique

Si \(au\equiv1\;[n]\), il existe \(q\in\mathbb{Z}\) tel que \(au-1=nq\). En ajoutant \(1-nq\) aux deux membres, on obtient \(au-nq=1\), soit \(au+n(-q)=1\). Les coefficients sont entiers ; le critère de Bézout donne \(\operatorname{PGCD}(a,n)=1\).

Réciproquement, si ce PGCD vaut \(1\), Bézout donne \(au+nv=1\). Alors \(au-1=-nv\), multiple de \(n\), donc \(u\) est un inverse.

Si \(u\) et \(v\) sont deux inverses, \(au\equiv av\;[n]\), donc \(n\mid a(u-v)\). Comme \(\operatorname{PGCD}(n,a)=1\), Gauss donne \(n\mid u-v\), c’est-à-dire \(u\equiv v\;[n]\). Enfin, si \(u\) est un inverse, tout \(u+kn\) l’est aussi :

Exemple expliqué : Construire un inverse sans deviner

Cherchons un inverse de \(17\) modulo \(43\). Euclide donne

Méthode : Trouver et contrôler un inverse

Calcule \(\operatorname{PGCD}(a,n)\). S’il n’est pas égal à \(1\), arrête : aucun inverse n’existe. Sinon, remonte Euclide pour écrire \(au+nv=1\). Lis le coefficient de \(a\), réduis-le si tu veux entre \(0\) et \(n-1\), puis vérifie que le produit avec \(a\) a pour reste \(1\). Une petite table de produits ou un produit évident peut remplacer la remontée lorsque le module est petit ; la condition et le contrôle restent indispensables.

Représentation intuitive : Une table de restes que l’on peut ou non remonter

Voici deux tables, modulo \(8\) :

Dans la ligne de \(3x\), chaque reste apparaît une seule fois ; le reste \(1\) est atteint pour \(x=3\), donc \(3\) est son propre inverse modulo \(8\). Dans la ligne de \(2x\), des entrées différentes ont la même image, et \(1\) n’apparaît jamais : \(2\) n’a pas d’inverse modulo \(8\). Le module \(8\) n’est pas premier, mais certains entiers y sont inversibles : c’est la coprimalité avec le module qui compte. Cette représentation donne du sens à « annuler une multiplication » ; pour un grand module, le théorème et Bézout remplacent la table.

À toi : Essai guidé : lis le bon coefficient

Trouve un inverse de \(13\) modulo \(29\). Commence par \(29=2\times13+3\), puis remonte jusqu’à une identité égale à \(1\).

Indice, à lire seulement si nécessaire. La division suivante est \(13=4\times3+1\).

Correction expliquée : La remontée fournit directement l’inverse

Euclide se termine par \(3=3\times1+0\), donc le PGCD vaut \(1\). Puis

À toi : Tentative avec un entier négatif

Trouve un inverse de \(-9\) modulo \(26\), avec un représentant entre \(0\) et \(25\). Décide aussi si \(8\) a un inverse modulo \(20\). Justifie le coefficient choisi dans l’identité, le changement de représentant et l’impossibilité éventuelle ; une valeur annoncée seule ne suffit pas.

Indice, à lire seulement si nécessaire. Une identité \(3\times9-26=1\) est utile, mais le coefficient de \(-9\) n’est pas \(3\).

Correction expliquée : Conserver le signe puis choisir un représentant

On vérifie \(3\times9-26=27-26=1\). Comme \(9=-(-9)\), cette identité s’écrit \((-3)(-9)-26=1\). Un inverse de \(-9\) est donc \(-3\) ; en ajoutant \(26\), on choisit \(23\). Le contrôle donne

Ce que ta réponse doit montrer. Explique pourquoi l’identité utilise des coefficients entiers, quel coefficient est l’inverse et pourquoi ajouter le module ne change pas son rôle.

Pour réparer une erreur : Choisir le mauvais coefficient de Bézout

À partir de \(1=2\times43-5\times17\), une copie annonce que \(2\) est un inverse de \(17\) modulo \(43\). La première erreur est de lire le coefficient de \(43\), pas celui de \(17\). Le contrôle dénonce l’erreur : \(17\times2=34\) n’a pas pour reste \(1\) modulo \(43\).

Rappel plus simple : \(5\times5-3\times8=1\) donne un inverse de \(5\) modulo \(8\) égal à \(5\), car c’est le coefficient qui multiplie \(5\).

Nouvel essai : à partir de \(1=5\times17-6\times14\), donne un inverse de \(14\) modulo \(17\) entre \(0\) et \(16\), puis contrôle-le.

Correction expliquée : Le nombre multiplié désigne le coefficient à lire

On écrit l’identité sous la forme \(14(-6)+17\times5=1\). Le coefficient de \(14\) est \(-6\) ; son représentant entre \(0\) et \(16\) est \(-6+17=11\). Contrôle : \(14\times11=154=9\times17+1\). Au problème initial, le coefficient de \(17\) est donc \(-5\), et l’inverse positif est \(38\) modulo \(43\).

À toi : Reprise différée : reconstruis sans la table

Détermine un inverse de \(19\) modulo \(50\). Donne un représentant entre \(0\) et \(49\) et vérifie-le.

Indice, à lire seulement si nécessaire. La suite des restes d’Euclide est \(12,7,5,2,1,0\).

Correction expliquée : Une remontée plus longue, avec les mêmes règles

Les divisions sont

Avant de commencer : Une simplification qui perdrait des solutions

On a \(2\times1\equiv2\times4\;[6]\), puisque \(8-2=6\). Peut-on en déduire \(1\equiv4\;[6]\) ? Que devient la conclusion modulo \(3\) ?

Correction expliquée : Le module compte autant que les nombres

Non : \(4-1=3\) n’est pas divisible par \(6\), donc \(1\not\equiv4\;[6]\). En revanche, \(3\mid4-1\), donc \(1\equiv4\;[3]\). La division des deux membres par \(2\) est ici accompagnée d’une division du module par \(2\). Le coefficient \(2\) est non nul, mais il n’est pas premier avec \(6\) : on ne pouvait pas le simplifier en gardant ce module.

Propriété : Simplifier sans changer le module

Si \(\operatorname{PGCD}(k,n)=1\), alors, pour tous \(u,v\in\mathbb{Z}\),

Démonstration : La condition de Gauss est la condition de simplification

La première congruence signifie \(n\mid k(u-v)\). Avec \(\operatorname{PGCD}(n,k)=1\), Gauss donne \(n\mid u-v\), donc \(u\equiv v\;[n]\). Réciproquement, si \(u-v=nq\) avec \(q\) entier, \(ku-kv=knq\) est multiple de \(n\) ; on retrouve la première congruence.

Propriété : Diviser aussi le module

Si \(d\) est un entier strictement positif qui divise \(s\), \(t\) et \(n\), alors

Démonstration : Revenir à une égalité

Dire \(s\equiv t\;[n]\) revient à écrire \(s-t=nq\) pour un entier \(q\). La division des deux membres par \(d\ne0\) donne \(s/d-t/d=(n/d)q\). Inversement, multiplier cette dernière égalité par \(d\) redonne \(s-t=nq\). Les deux écritures sont donc équivalentes.

Corollaire : La règle générale de simplification

Pour \(n\ge2\) et \(k\ne0\), pose \(d=\operatorname{PGCD}(k,n)\). Alors

Démonstration : Réduire puis simplifier un facteur devenu coprime

Écris \(k=dK\) et \(n=dN\). Diviser par \(d\) donne

Exemple expliqué : Même geste apparent, modules différents

Pour \(5x\equiv10\;[12]\), on écrit \(5x\equiv5\times2\;[12]\). Puisque \(\operatorname{PGCD}(5,12)=1\), on simplifie \(5\) sans changer le module : \(x\equiv2\;[12]\).

Pour \(6x\equiv12\;[18]\), on écrit \(6x\equiv6\times2\;[18]\). Cette fois \(\operatorname{PGCD}(6,18)=6\), donc

À toi : Essai guidé : justifie le nouveau module

Simplifie \(8x\equiv24\;[20]\) de deux façons : avec le corollaire général, puis en divisant d’abord par \(4\). Explique pourquoi le résultat n’est pas \(x\equiv3\;[20]\).

Indice, à lire seulement si nécessaire. Écris \(24=8\times3\) ; dans la seconde voie, le module devient \(5\).

Correction expliquée : Deux voies qui conservent le même ensemble

Comme \(\operatorname{PGCD}(8,20)=4\), le corollaire donne directement

À toi : Variations de condition, pas seulement de nombres

Pour des entiers \(u,v\) :

1. justifie si \(5u\equiv5v\;[12]\) équivaut à \(u\equiv v\;[12]\) ;

2. donne la conclusion correcte à partir de \(6u\equiv6v\;[15]\) ;

3. réfute la conclusion trop forte \(u\equiv v\;[15]\) dans le deuxième cas.

Indice, à lire seulement si nécessaire. Pour réfuter une implication, une paire particulière \((u,v)\) suffit.

Correction expliquée : Le PGCD décide de ce que l’on peut conclure

Dans le premier cas, \(\operatorname{PGCD}(5,12)=1\) : Gauss autorise la simplification avec module \(12\), dans les deux sens. Dans le deuxième, \(\operatorname{PGCD}(6,15)=3\) : la conclusion équivalente est \(u\equiv v\;[5]\). Prends \(u=0\), \(v=5\). Alors \(6v-6u=30\) est divisible par \(15\), donc l’hypothèse est vraie. Mais \(v-u=5\) n’est pas divisible par \(15\), donc la conclusion trop forte est fausse.

Ce que ta réponse doit montrer. Ta réponse doit nommer la condition de coprimalité, annoncer le module conservé ou réduit, et distinguer une équivalence valide d’une implication réfutée.

Pour réparer une erreur : « Le coefficient n’est pas nul » ne suffit pas

Une copie passe de \(2x\equiv2\;[6]\) à \(x\equiv1\;[6]\), parce que \(2\ne0\). La première erreur est d’utiliser une règle des égalités sans contrôler la congruence. En réalité, \(2(x-1)=6q\) équivaut, après division par \(2\), à \(x-1=3q\). Ainsi \(x\equiv1\;[3]\) : modulo \(6\), les deux représentants \(1\) et \(4\) conviennent.

Nouvel essai : simplifie \(9x\equiv18\;[12]\) et indique les représentants modulo \(12\).

Correction expliquée : Le facteur et le module ont un PGCD

On a \(18=9\times2\) et \(\operatorname{PGCD}(9,12)=3\). Le corollaire donne \(x\equiv2\;[12/3]\), soit \(x\equiv2\;[4]\). Les représentants modulo \(12\) sont \(2,6,10\) ; leurs différences avec \(2\) sont des multiples de \(4\). Le contrôle de toute la famille est

À toi : À reprendre plus tard

Simplifie \(10x\equiv30\;[24]\). Donne les représentants modulo \(24\) et une explication permettant de retrouver le module réduit.

Indice, à lire seulement si nécessaire. Écris \(30=10\times3\), puis calcule \(\operatorname{PGCD}(10,24)\).

Correction expliquée : Ne pas confondre coefficient et PGCD

Euclide donne \(24=2\times10+4\), \(10=2\times4+2\), \(4=2\times2\), donc le PGCD vaut \(2\). La congruence équivaut à \(x\equiv3\;[24/2]\), soit \(x\equiv3\;[12]\). Les représentants modulo \(24\) sont \(3\) et \(15\). Pour toute la famille \(x=3+12k\),

Avant de commencer : Une congruence peut n’avoir aucune solution

Compare \(18x\equiv30\;[42]\) et \(18x\equiv31\;[42]\). Sans chercher \(x\), montre que la seconde est impossible.

Correction expliquée : Le second membre doit respecter un diviseur commun

Si \(18x\equiv31\;[42]\), il existe \(q\in\mathbb{Z}\) tel que \(18x-31=42q\). Donc \(31=18x-42q=6(3x-7q)\) devrait être divisible par \(6\), ce qui est faux : \(31=5\times6+1\). Le second membre \(30\), lui, est divisible par \(6\) ; le théorème suivant garantit alors l’existence de solutions.

Théorème : Existence, réduction et nombre de classes

Soient \(a,b\in\mathbb{Z}\), \(n\ge2\), et \(d=\operatorname{PGCD}(a,n)\). La congruence \(ax\equiv b\;[n]\) admet une solution entière si et seulement si \(d\mid b\).

Supposons cette condition remplie, et posons

Démonstration : Pourquoi le PGCD mesure aussi la multiplicité

Si \(ax\equiv b\;[n]\), il existe \(q\in\mathbb{Z}\) tel que \(ax-b=nq\), donc \(b=ax-nq\). Le nombre \(d\) divise \(a\) et \(n\) ; il divise donc cette combinaison et ainsi \(b\).

Réciproquement, Bézout donne \(a\alpha+n\beta=d\). Si \(b=dh\), avec \(h\in\mathbb{Z}\), multiplier l’identité par \(h\) donne \(a(h\alpha)+n(h\beta)=b\). Le choix \(x=h\alpha\) vérifie donc la congruence. Cela prouve le critère d’existence.

Pour décrire les solutions, on divise l’égalité \(ax-b=nq\) par \(d>0\) :

Pour classer ces entiers modulo \(n=dN\), divisons \(k\) par \(d\) : \(k=dh+j\), avec \(h\in\mathbb{Z}\) et \(0\le j<d\). Alors

Enfin, si \(N=1\), alors \(d=n\) ; \(n\) divise \(a\) et \(b\). Ainsi \(ax-b\) est multiple de \(n\) pour tout entier \(x\).

Méthode : L’ordre des décisions

1. Calcule \(d=\operatorname{PGCD}(a,n)\).

2. Si \(d\nmid b\), conclus : aucune solution entière.

3. Sinon, divise \(a,b\) et le module \(n\) par \(d\).

4. Si le module réduit vaut \(1\), tous les entiers conviennent. Sinon, inverse le coefficient réduit avec Bézout.

5. Donne la famille entière, puis, si demandé, ses \(d\) classes modulo le module initial.

6. Vérifie par substitution dans la congruence initiale.

Ne cherche pas un inverse de \(a\) modulo \(n\) lorsque leur PGCD dépasse \(1\) : c’est le coefficient réduit qui deviendra inversible.

Exemple expliqué : Réduire le coefficient et le module ensemble

Résolvons \(18x\equiv30\;[42]\). Comme \(\operatorname{PGCD}(18,42)=6\) et \(6\) divise \(30\), la recherche peut aboutir. La congruence signifie qu’il existe \(q\in\mathbb{Z}\) tel que \(18x-30=42q\). On divise les deux membres de cette égalité par \(6\ne0\) :

Comme \(3\times5=15=2\times7+1\), \(5\) est un inverse de \(3\) modulo \(7\). Multiplions les deux membres de la congruence réduite par \(5\) :

Exemple expliqué : Le cas coprime ne donne qu’une classe

Résolvons \(17x\equiv9\;[43]\). Nous disposons de \(17\times38=15\times43+1\), donc \(38\) est un inverse de \(17\) modulo \(43\). En multipliant les deux membres par \(38\),

À toi : Essai guidé : revenir au module de départ

Résous \(20x\equiv14\;[42]\) et donne tous les représentants entre \(0\) et \(41\). Que se passerait-il avec le second membre \(15\) ?

Indice, à lire seulement si nécessaire. Le PGCD vaut \(2\) ; \(10\times19=190=9\times21+1\).

Correction expliquée : Une classe modulo 21, deux modulo 42

Euclide : \(42=2\times20+2\), \(20=10\times2\) ; le PGCD est \(2\). Comme \(2\mid14\), la congruence équivaut à \(10x\equiv7\;[21]\). Le produit fourni montre que \(19\) est un inverse de \(10\) modulo \(21\). On multiplie donc les deux membres par \(19\) :

À toi : Tentative avec un coefficient négatif

Résous \(-12x\equiv18\;[30]\). Donne une description par un paramètre, puis tous les représentants entre \(0\) et \(29\). Justifie le changement de module et explique pourquoi ta liste contient exactement six représentants ; distingue cette liste de l’ensemble infini des solutions entières.

Indice, à lire seulement si nécessaire. Réduis par \(6\) ; un inverse de \(-2\) modulo \(5\) est \(2\).

Correction expliquée : L’inverse peut être positif malgré le coefficient négatif

Le PGCD de \(-12\) et \(30\) est \(6\), car \(30=2\times12+6\) et \(12=2\times6\). Il divise \(18\), et la réduction donne \(-2x\equiv3\;[5]\). Puisque \((-2)\times2=-4=-5+1\), \(2\) est bien un inverse de \(-2\) modulo \(5\). Multiplier par \(2\) donne

Ce que ta réponse doit montrer. Il faut justifier le PGCD, la réduction du module, le produit qui fournit l’inverse, la famille complète et le nombre de représentants, pas seulement afficher une liste.

Méthode : Autre voie : transformer la congruence en équation

La congruence \(ax\equiv b\;[n]\) équivaut à l’existence de \(y\in\mathbb{Z}\) tel que \(ax-ny=b\). On peut donc résoudre cette équation diophantienne : les premières coordonnées des couples solutions donnent exactement les valeurs de \(x\) cherchées.

Rappel utile : si \(AX+BY=C\), avec \(A,B\ne0\), possède une solution \((X_0,Y_0)\) et si \(d=\operatorname{PGCD}(A,B)\), toutes les solutions sont \(X=X_0+(B/d)t\), \(Y=Y_0-(A/d)t\), \(t\in\mathbb{Z}\). Ce résultat se prouve en soustrayant une particulière, puis en appliquant Gauss aux coefficients réduits, et en vérifiant la réciproque.

À toi : Changer de représentation

Résous \(14x\equiv8\;[30]\) en utilisant l’équation \(14x-30y=8\). Compare ensuite avec une réduction de la congruence.

Indice, à lire seulement si nécessaire. Le couple \((7,3)\) vérifie l’équation.

Correction expliquée : Les deux voies décrivent les mêmes entiers

Le PGCD de \(14\) et \(30\) est \(2\) : \(30=2\times14+2\), \(14=7\times2\). Le couple \((7,3)\) convient car \(14\times7-30\times3=98-90=8\). Soustraire son égalité et diviser par \(2\) donne

Par la voie de la congruence, on réduit d’abord en \(7x\equiv4\;[15]\). Comme \(7\times13=91=6\times15+1\), un inverse de \(7\) est \(13\). On obtient \(x\equiv52\equiv7\;[15]\), puisque \(52=3\times15+7\). Les descriptions coïncident ; le quotient entier \(y\) a simplement été rendu explicite dans la première méthode.

Pour réparer une erreur : Chercher des solutions alors que le PGCD les interdit

Une copie tente de résoudre \(18x\equiv31\;[42]\) en cherchant un inverse de \(18\). La première erreur est de sauter le calcul du PGCD et la condition sur le second membre.

Exemple plus simple : \(4x\equiv3\;[6]\) demanderait \(4x-3=6q\). Donc \(3=4x-6q=2(2x-3q)\) serait pair : impossible.

Nouvel essai : décide si \(12x\equiv8\;[18]\) possède une solution entière.

Correction expliquée : L’obstruction doit être levée avant toute inversion

Le PGCD de \(12\) et \(18\) vaut \(6\) : \(18=12+6\), \(12=2\times6\). Mais \(6\) ne divise pas \(8\) ; aucune solution n’existe. En effet, une solution donnerait \(8=12x-18q=6(2x-3q)\), contradiction. Au problème initial, \(\operatorname{PGCD}(18,42)=6\) ne divise pas \(31\), donc il n’y a pas de solution non plus. Il ne suffit pas qu’une congruence contienne une inconnue pour qu’elle soit soluble.

Propriété : Coefficient nul ou module réduit égal à 1

Si \(n\mid a\), alors \(ax\equiv b\;[n]\) est vraie pour tous les entiers \(x\) lorsque \(n\mid b\), et pour aucun sinon. Cela inclut \(a=0\). Si le module initial est \(1\), toute congruence entre entiers est vraie ; on ne parle pas ici d’inverse modulo \(1\).

Démonstration : Lire directement la divisibilité

Si \(a=nq\), alors \(ax-b=nqx-b\). Ce nombre est multiple de \(n\) exactement lorsque \(b\) est multiple de \(n\), indépendamment de \(x\). Pour le module \(1\), la différence de deux entiers est toujours divisible par \(1\).

À toi : Cas limites à reconnaître

Sans chercher d’inverse, résous :

Correction expliquée : Aucun entier ou tous les entiers

La première demanderait \(11\mid-7\), ce qui est faux : aucune solution. La deuxième demande \(11\mid0\), vrai pour tout entier \(x\) : tous les entiers conviennent. Dans la troisième, \(24x-36=12(2x-3)\) est toujours multiple de \(12\) : tous les entiers conviennent. Dans la quatrième, \(24x\) est multiple de \(12\), alors que \(5\) ne l’est pas : aucune solution. Ces cas correspondent au module réduit \(N=1\) lorsque le critère d’existence est satisfait ; il n’y a pas d’inverse à chercher.

À toi : Reprise différée : retrouver toutes les classes

Résous \(27x\equiv18\;[45]\), puis décide ce qui changerait avec second membre \(19\). Donne la famille entière et les représentants entre \(0\) et \(44\).

Indice, à lire seulement si nécessaire. Le PGCD vaut \(9\) ; la congruence réduite porte sur le module \(5\).

Correction expliquée : Une famille courte, neuf représentants

Euclide : \(45=27+18\), \(27=18+9\), \(18=2\times9\), donc le PGCD vaut \(9\). Il divise \(18\) : on réduit en \(3x\equiv2\;[5]\). Comme \(3\times2=6=5+1\), l’inverse de \(3\) modulo \(5\) est \(2\). Ainsi \(x\equiv4\;[5]\), et toutes les solutions sont \(x=4+5k\), \(k\in\mathbb{Z}\). Les neuf représentants modulo \(45\) sont

À retenir : Le PGCD commande l’existence et le bon module

Un inverse de \(a\) modulo \(n\ge2\) est un entier \(u\) tel que \(au\equiv1\;[n]\). Il existe exactement lorsque \(\operatorname{PGCD}(a,n)=1\), et il est unique modulo \(n\), pas comme entier.

Pour \(ax\equiv b\;[n]\), calcule \(d=\operatorname{PGCD}(a,n)\). Si \(d\nmid b\), il n’y a aucune solution. Sinon, réduis les deux membres et le module par \(d\). Pour un module réduit \(N=n/d\ge2\), inverse le coefficient réduit : tu obtiens une classe modulo \(N\), donc exactement \(d\) classes modulo \(n\). Si \(N=1\), tous les entiers conviennent.

On peut simplifier un facteur sans changer le module lorsqu’il est premier avec ce module. Une simple non-nullité ne suffit pas. Vérifie toujours la solution ou la famille dans la congruence initiale.

Remarque : Les objets manipulés dans cette unité

Les entrées \(a,b\) sont des entiers relatifs, non tous les deux nuls. Leur PGCD est le plus grand entier positif qui les divise tous les deux. Il ne dépend pas de leurs signes : \(\operatorname{PGCD}(a,b)=\operatorname{PGCD}(|a|,|b|)\). Pour \(a\ne0\), \(\operatorname{PGCD}(a,0)=|a|\) ; nous ne définissons pas \(\operatorname{PGCD}(0,0)\).

Pour des entiers \(A\geq0\) et \(B>0\), la division euclidienne écrit \(A=qB+R\) avec \(q\in\mathbb{N}\) et \(0\leq R<B\). En Python, A // B donne \(q\) et A % B donne \(R\). Les caractères // ne désignent pas une division décimale. Par exemple, \(29=4\times6+5\) donne 29 // 6 = 4 et 29 % 6 = 5.

Une identité de Bézout est une égalité \(au+bv=d\), où \(d=\operatorname{PGCD}(a,b)\) et \(u,v\) sont des entiers, éventuellement négatifs. On cherche ici à calculer ces coefficients en même temps que le PGCD.

Avant de commencer : Lire une affectation

Avant de lire la réponse, prends \(A=29\), \(B=6\). Calcule le reste, puis lis successivement R = A % B, A = B, B = R. Quelles valeurs contiennent les trois variables à la fin ?

Réponse. \(29-4\times6=5\), donc \(R=5\) ; \(A\) reçoit ensuite l’ancienne valeur de \(B\), soit \(6\) ; enfin \(B\) reçoit \(5\). L’état final est \(A=6\), \(B=5\), \(R=5\). En informatique, le signe = signifie ici « reçoit la valeur calculée à droite », non une égalité mathématique qui doit rester vraie après les lignes suivantes. Si tu as gardé \(A=29\), reprends cette distinction avant le programme.

Propriété : La règle qui autorise la boucle

Si \(A=qB+R\) avec \(B>0\) et \(0\leq R<B\), alors \(\operatorname{PGCD}(A,B)=\operatorname{PGCD}(B,R)\).

Démonstration : Pourquoi les diviseurs communs sont conservés

Si un entier positif \(e\) divise \(A\) et \(B\), il divise \(A-qB=R\) : il divise donc \(B\) et \(R\). Réciproquement, s’il divise \(B\) et \(R\), il divise \(qB+R=A\). Les deux paires ont exactement les mêmes diviseurs positifs communs, donc le même plus grand. Cette preuve rappelle la règle établie avec Euclide ; elle justifie chacune des étapes du programme, pas seulement un exemple.

Exemple expliqué : Une étape, calculée avant toute mise à jour

Les variables contiennent \(A=323\) et \(B=187\). Le quotient entier est \(q=1\), car \(187\times1\leq323<187\times2\). Le reste vaut

Algorithme : Calculer le PGCD, avec une variable temporaire

Entrées : deux entiers \(a,b\) non tous les deux nuls. Sortie : leur PGCD positif. On travaille sur les valeurs absolues pour que toutes les divisions de la boucle aient un dividende positif ou nul et un diviseur strictement positif.

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

Exemple expliqué : Suivre tout le calcul pour \(323\) et \(187\)

Chaque ligne est l’état avant la division indiquée. La dernière ligne est l’état d’arrêt : on n’y effectue plus de division.

Le reste nul fait arrêter le calcul, mais ce n’est pas le PGCD. À cet instant, le dernier reste non nul a été placé dans \(A\). Le contrôle donne \(323=17\times19\) et \(187=17\times11\). Cela confirme que \(17\) est un diviseur commun ; c’est la conservation démontrée des diviseurs communs qui garantit qu’il est le plus grand.

Proposition : Le programme s’arrête et donne le bon résultat

Pour toutes les entrées entières autorisées, pgcd_euclide(a,b) termine et renvoie \(\operatorname{PGCD}(a,b)\).

Démonstration : Un invariant et une quantité qui diminue

Un invariant est une propriété vraie au départ et conservée à chaque tour. Ici, c’est

Pour l’arrêt, on suit \(B\). Tant qu’il n’est pas nul, le nouveau \(B\) est le reste \(R\), donc \(0\leq R<B\). Une suite d’entiers naturels ne peut pas décroître strictement indéfiniment : partant de la valeur initiale \(B_0\), elle baisse d’au moins \(1\) à chaque tour, donc au plus \(B_0\) tours sont possibles. À l’arrêt, \(B=0\) et \(A>0\). L’invariant donne alors

Méthode : Lire ou compléter un programme d’Euclide

Si une tâche demande un calcul répétitif de PGCD ou un tableau d’états, commence par nommer les deux valeurs actuelles. Écris \(A=qB+R\) et vérifie \(0\leq R<B\). Calcule le reste avec les anciennes valeurs ; déplace ensuite l’ancien \(B\) dans \(A\) et le reste dans \(B\). Arrête quand \(B=0\), puis lis \(A\). Pour justifier le programme, donne séparément la conservation du PGCD et la diminution du reste. Quelques essais numériques ne remplacent pas ces deux arguments.

Question d’élève : Et si la première division est déjà exacte ?

Avec \(A=42\), \(B=14\), le premier reste calculé est \(0\), car \(42=3\times14\). Il n’y a donc aucun reste calculé non nul. Le programme passe à \((14,0)\) et renvoie \(14\), le diviseur de la dernière division. L’expression courante « dernier reste non nul » inclut alors le diviseur initial dans la chaîne d’Euclide. Si \(B=0\) dès le départ, on ne fait aucune division et on renvoie directement \(|a|\).

À toi : Essai guidé : quatre divisions

Calcule le PGCD de \(221\) et \(143\) en remplissant les nouvelles paires : \((221,143)\), puis \((143,\ldots)\), \((78,\ldots)\), \((65,\ldots)\) et l’état final. Indique la valeur renvoyée et pourquoi elle n’est pas \(0\).

Indice, à lire seulement si nécessaire. Commence par \(221-143\), puis calcule le reste de \(143\) dans la division par \(78\).

Correction expliquée : Essai guidé

Les divisions sont

À toi : À tenter avant de consulter

Écris les états de pgcd_euclide(299,115). Puis explique, avec les noms des variables, pourquoi il ne faut pas renvoyer \(B\) à la fin.

Indice, à lire seulement si nécessaire. La première division utilise le quotient \(2\) ; son reste est \(299-2\times115\).

Correction expliquée : États et justification

\(299-2\times115=299-230=69\) ; puis \(115-69=46\) ; puis \(69-46=23\) ; enfin \(46-2\times23=0\). On obtient

Ce que ta réponse doit montrer. Ta réponse doit distinguer les deux variables, mentionner la condition d’arrêt et utiliser la propriété du PGCD avec zéro. Dire seulement « le dernier nombre » est ambigu.

À toi : Variation : entrées permutées, signes et zéro

Prévois les résultats pour \((187,323)\), \((-323,187)\), \((0,-35)\) et \((0,0)\). Pour le premier couple, décris la première division ; pour les deux derniers, précise si la boucle est exécutée.

Correction expliquée : Aucune hypothèse \(a>b\) n’est cachée

Pour \((187,323)\), \(187=0\times323+187\) : le premier tour donne \((323,187)\), puis le tableau de référence conduit à \(17\). Pour \((-323,187)\), la valeur absolue donne immédiatement \((323,187)\), donc \(17\).

Pour \((0,-35)\), l’initialisation donne \((0,35)\). Le reste de \(0\) par \(35\) vaut \(0\), d’où \((35,0)\) après un tour et la sortie \(35\). Avec \((0,0)\), l’exception est déclenchée avant l’initialisation de la boucle : aucune valeur n’est renvoyée comme PGCD. Le rejet est conforme à notre convention, et non un manque du programme.

Pour réparer une erreur : Si les anciennes valeurs ont disparu

Erreur proposée : avec \((A,B)=(21,15)\), écrire d’abord A = B, puis B = A % B. La première ligne remplace \(21\) par \(15\) ; la seconde calcule \(15\%15=0\). Le programme s’arrête avec \(15\), alors que \(21=15+6\) et \(15=2\times6+3\) donnent un PGCD de \(3\).

Rappel ciblé. Calcule ce qui dépend des anciennes valeurs avant de les remplacer. Exemple plus simple : \((14,8)\) donne \(R=14-8=6\), puis \((A,B)=(8,6)\).

Nouvel essai. Applique le bon ordre au couple \((18,12)\), jusqu’à l’arrêt. Correction. D’abord \(R=18-12=6\), puis \((12,6)\) ; ensuite \(R=12-2\times6=0\), puis \((6,0)\) ; le PGCD est \(6\). Reviens maintenant à la première étape du tableau \(323,187\) : le calcul \(R=136\) doit précéder tout remplacement de \(A\) ou de \(B\).

Avant de commencer : Retrouver les deux coefficients

Dans \(R=3a-5b\), quels sont les coefficients de \(a\) et de \(b\) ? Que devient \(A-2B\) si \(A=a-b\) et \(B=-a+2b\) ?

Réponse. Les coefficients de \(R\) sont \(3\) et \(-5\). Pour la seconde question,

Représentation intuitive : Une étiquette attachée à chaque reste

On peut imaginer que chaque valeur transporte une étiquette \((u,v)\) indiquant comment elle a été fabriquée à partir des deux données de départ : \(ua+vb\). Quand on soustrait \(q\) fois une valeur, on soustrait aussi \(q\) fois son étiquette. Cette image aide à suivre la provenance ; les coefficients peuvent être négatifs, donc il ne s’agit pas de quantités d’objets physiques. Les égalités suivantes, et non l’image, justifient le calcul.

Propriété : La mise à jour des coefficients

Si \(A=ua+vb\) et \(B=sa+tb\), alors le reste \(R=A-qB\) s’écrit

Démonstration : Même opération sur les valeurs et leurs coefficients

On remplace les deux valeurs par leurs expressions, puis on distribue le facteur \(-q\) :

Algorithme : Obtenir le PGCD et un couple de Bézout

Les variables \(u,v\) décrivent \(A\), tandis que \(s,t\) décrivent \(B\). Les majuscules \(R,U,V\) reçoivent les nouveaux calculs avant les affectations. La sortie est le triplet \((d,u,v)\) satisfaisant \(au+bv=d\).

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

Exemple expliqué : Le tableau étendu pour \(323\) et \(187\)

Chaque ligne vérifie simultanément \(A=323u+187v\) et \(B=323s+187t\).

Voyons la transition de l’étape \(2\) à l’étape \(3\). Le quotient est \(q=2\) et

À l’arrêt, la sortie est \((17,-4,7)\) et l’identité annoncée est

Proposition : Ce que garantit Euclide étendu

Pour deux entiers \(a,b\) non tous deux nuls, bezout_euclide(a,b) termine et renvoie \((d,u,v)\) avec \(d=\operatorname{PGCD}(a,b)>0\) et \(au+bv=d\).

Démonstration : Trois propriétés conservées

À l’initialisation, \(A=|a|=ua+vb\) : si \(a\geq0\), on a \(u=1,v=0\) ; sinon \(u=-1,v=0\). Dans les deux cas l’égalité est vraie. De même, \(B=|b|=sa+tb\), grâce à \(s=0\) et au choix du signe de \(t\).

Supposons les deux identités vraies au début d’un tour. La propriété de mise à jour établit \(R=Ua+Vb\). Le déplacement des coefficients assure ensuite que le nouveau \(A\), qui est l’ancien \(B\), a bien les coefficients de cet ancien \(B\), et que le nouveau \(B=R\) a bien \(U,V\). Les deux identités restent vraies.

Le PGCD de \(A,B\) est lui aussi conservé, puisque les restes suivent exactement Euclide. La même diminution stricte de \(B\) prouve l’arrêt. Alors \(A=d\), \(B=0\) et l’identité conservée \(A=ua+vb\) donne \(d=ua+vb\). Les autres variables ne sont plus utiles à la sortie.

Méthode : Choisir les variables à renvoyer

Si tu veux seulement un PGCD, le premier programme suffit. Si tu veux en plus une identité ou préparer un inverse modulo un entier, conserve les coefficients pendant les divisions. Commence par écrire au-dessus du tableau les deux identités \(A=ua+vb\) et \(B=sa+tb\) : elles indiquent à quoi sert chaque colonne. À l’arrêt, lis les coefficients du \(A\) final, qui est le diviseur de la dernière division lorsqu’une division a eu lieu, et vérifie l’identité avec les entrées signées d’origine. Si la boucle n’a pas été exécutée, l’initialisation fournit déjà l’identité. Un couple différent de celui d’un corrigé peut être correct ; le contrôle porte sur l’égalité, pas sur l’apparence des coefficients.

À toi : Essai guidé : compléter deux étiquettes

Pour \(a=119\), \(b=85\), commence avec \(A=119\), \(B=85\), \((u,v)=(1,0)\) et \((s,t)=(0,1)\). Les divisions sont \(119=85+34\), \(85=2\times34+17\), \(34=2\times17\). Trouve les coefficients de \(34\), puis de \(17\), et vérifie l’identité finale.

Indice, à lire seulement si nécessaire. La première étiquette est \((1-1\times0,0-1\times1)\). La seconde doit utiliser les coefficients de \(85\) et de \(34\).

Correction expliquée : Deux soustractions sur les coefficients

\(34=119-85\) a pour étiquette \((1,-1)\). Comme \(17=85-2\times34\), ses coefficients sont

À toi : À tenter avant de consulter : une entrée négative

Prévois le résultat du programme étendu pour \(a=-161\), \(b=115\). Écris l’initialisation des coefficients, puis une identité de Bézout pour ces deux entrées. Explique pourquoi changer le signe de \(a\) change aussi son coefficient.

Indice, à lire seulement si nécessaire. La boucle commence avec \(A=161\), \(B=115\), mais \(A=-1\times a+0\times b\).

Correction expliquée : Conserver l’identité avec les données d’origine

L’initialisation est \((u,v)=(-1,0)\) et \((s,t)=(0,1)\). Les divisions sont \(161=115+46\), \(115=2\times46+23\), \(46=2\times23\). Le reste \(46=A-B\) a les coefficients \((-1,-1)\) : \((-1)\times(-161)-115=46\). Le reste \(23=115-2\times46\) a les coefficients

Ce que ta réponse doit montrer. Il faut montrer l’initialisation signée, au moins une mise à jour et la substitution finale avec \(-161\) entre parenthèses. L’égalité finale seule ne montre pas que le programme a été compris.

À toi : Variation : quel certificat contrôle réellement le PGCD ?

Un programme renvoie \(d,u,v\) et l’on vérifie seulement \(au+bv=d\). Est-ce suffisant pour conclure \(d=\operatorname{PGCD}(a,b)\) ? Examine \(a=6\), \(b=10\), \(u=v=1\), puis indique ce qu’il faut vérifier en plus si l’on ne dispose pas de la preuve du programme.

Correction expliquée : Une identité seule ne suffit pas

Ici \(6\times1+10\times1=16\), mais \(\operatorname{PGCD}(6,10)=2\). L’identité seule n’impose pas que \(d\) divise \(a\) et \(b\). Un certificat complet est : \(d>0\), \(d\mid a\), \(d\mid b\) et \(au+bv=d\). En effet, tout diviseur commun de \(a,b\) divise alors \(d\) ; comme \(d\) est lui-même un diviseur commun positif, c’est le plus grand. Pour nos programmes, la preuve d’invariance établit déjà le PGCD ; ce certificat fournit un contrôle supplémentaire d’une sortie particulière.

Pour réparer une erreur : Si une mise à jour de coefficient utilise la nouvelle valeur

Erreur proposée : écrire u = s puis s = u - q * s. Avec les valeurs initiales \(u=1,s=0,q=1\), la première instruction donne \(u=0\), puis la seconde donne \(s=0-1\times0=0\). Pourtant le coefficient correct du premier reste de \(323,187\) est \(1-1\times0=1\). La première ligne fautive est le remplacement prématuré de \(u\).

Rappel ciblé. Calcule \(U=u-qs\) avant les affectations. Exemple simple avec \(22=2\times8+6\) : \(U=1-2\times0=1\), \(V=0-2\times1=-2\), donc \(6=22-2\times8\). Ensuite seulement, déplace les étiquettes.

Nouvel essai. Quelle étiquette reçoit \(6\) dans \(18=1\times12+6\) ? Correction. Les étiquettes initiales sont \((1,0)\) et \((0,1)\) ; la soustraction donne \((1-1\times0,0-1\times1)=(1,-1)\), et \(18-12=6\). Reviens au cas \(323,187\) : le coefficient temporaire \(U=1\) doit être conservé avant que \(u\) reçoive \(0\).

Contrôle : Des entrées choisies pour des raisons différentes

Ces tests vérifient des cas ordinaires, des signes, une permutation et zéro. Ils peuvent révéler une erreur de transcription ; leur réussite ne démontre pas le résultat pour tous les entiers, ce qui est le rôle des preuves précédentes.

assert pgcd_euclide(323, 187) == 17
assert pgcd_euclide(187, 323) == 17
assert pgcd_euclide(0, -35) == 35
assert bezout_euclide(323, 187) == (17, -4, 7)
assert bezout_euclide(-323, 187) == (17, 4, 7)
assert bezout_euclide(0, -35) == (35, 0, -1)

for a, b in [(119, 85), (-161, 115), (-35, 0)]:
    d, u, v = bezout_euclide(a, b)
    assert d > 0
    assert a % d == 0 and b % d == 0
    assert a * u + b * v == d

try:
    bezout_euclide(0, 0)
except ValueError:
    pass
else:
    raise AssertionError("Le couple (0, 0) doit etre refuse")

À toi : À reprendre une autre séance, avant de relire

1. Retrouve les états d’Euclide pour \(391\) et \(253\) et donne le PGCD.

2. Pour \(187\) et \(119\), trouve avec les étiquettes un couple de Bézout. Donne une phrase sur la terminaison et une phrase sur la conservation des identités.

Indice, à lire seulement si nécessaire. Pour 1, le premier reste vaut \(138\). Pour 2, les restes sont \(68,51,17,0\) ; conserve le coefficient de chaque donnée d’origine.

Correction expliquée : Reprise différée

1. \(391=253+138\), \(253=138+115\), \(138=115+23\), \(115=5\times23\). Les états sont \((391,253)\), \((253,138)\), \((138,115)\), \((115,23)\), \((23,0)\) ; le PGCD est \(23\).

2. On suit \(68=187-119\), puis

Ce que ta réponse doit montrer. Écris les états dans le bon ordre, le reste non nul final, des coefficients attachés aux données d’origine et un contrôle numérique. Sépare la preuve d’arrêt de celle de la valeur calculée.

À retenir : L’essentiel

Pour programmer Euclide, on conserve le PGCD et on fait diminuer le second nombre. Pour programmer Bézout, on conserve aussi les deux identités linéaires. Les nouvelles valeurs se calculent avec les anciennes, avant leur remplacement. Un test contrôle un cas ; un invariant et un argument d’arrêt justifient le programme sur tout son domaine.

Propriété : La boîte à outils locale

• Pour \((a,b)\ne(0,0)\), le PGCD \(d>0\) est le plus grand diviseur commun. Euclide le calcule par divisions successives ; tout diviseur commun divise \(d\).

• Pour \(d>0\), \(\operatorname{PGCD}(a,b)=d\) équivaut à \(a=du,b=dv\), avec \(u,v\in\mathbb{Z}\) premiers entre eux. Cette réduction retire tous les facteurs communs.

• Bézout donne des coefficients entiers \(r,s\) tels que \(ar+bs=\operatorname{PGCD}(a,b)\). En particulier, une combinaison entière égale à 1 caractérise la coprimalité.

• Gauss : si \(m\mid ax\) et \(\operatorname{PGCD}(m,a)=1\), alors \(m\mid x\).

• Pour \(n\ge2\), \(x\equiv y\;[n]\) signifie \(n\mid(x-y)\). Si \(ua\equiv1\;[n]\), on peut multiplier \(ax\equiv b\;[n]\) par \(u\) et obtenir \(x\equiv ub\;[n]\). Un tel inverse \(u\) existe exactement lorsque \(\operatorname{PGCD}(a,n)=1\).

Ces résultats ont été démontrés dans le parcours principal. Leurs conditions sont reprises ici pour que les problèmes restent exploitables séparément.

Avant de commencer : Quelle inconnue ?

Pour chaque demande, précise d’abord ce que désigne l’inconnue :

1. Faire le plus grand nombre de lots identiques à partir de deux effectifs.

2. Trouver deux entiers dont on connaît le produit et le PGCD.

3. Retrouver le rang d’une lettre à partir d’une congruence.

Correction. 1 : le nombre de lots doit diviser chacun des effectifs ; on cherche un diviseur commun maximal. 2 : on cherche un couple, à réduire par le PGCD avant d’utiliser le produit. 3 : le rang est un entier dans \(\{0,\ldots,25\}\) ; on résout une congruence, puis on choisit son représentant dans cet intervalle. Si les réponses se confondaient, commence la méthode suivante en écrivant une phrase par inconnue.

Méthode : Du texte à la vérification finale

Premier geste. Nommer chaque inconnue et son domaine : entier relatif, entier naturel, entier positif, ou entier dans un intervalle.

Traduire chaque information par une égalité, une divisibilité ou une congruence. Choisir l’outil qui agit sur cette forme. Résoudre d’abord les contraintes arithmétiques, puis conserver seulement les valeurs admissibles dans le contexte. Enfin, revenir aux quantités initiales et vérifier toutes les conditions, pas seulement la dernière équation utilisée.

Exemple expliqué : Un produit et un PGCD

On cherche les entiers positifs \(a<b\) tels que

Les seules paires copremières sont \((1,72)\) et \((8,9)\). On revient aux nombres initiaux en multipliant chaque coordonnée par 12 :

À toi : Essai guidé : ne pas perdre le retour d’échelle

Trouve les entiers positifs \(a<b\) tels que \(\operatorname{PGCD}(a,b)=5\) et \(ab=150\). Pose \(a=5u,b=5v\), complète l’équation en \(u,v\), puis n’oublie pas de donner \(a,b\).

Indice, à lire seulement si nécessaire. Après division par \(5^2=25\), le produit réduit vaut 6.

Correction expliquée : Du couple réduit au couple demandé

On a \((5u)(5v)=150\), donc \(25uv=150\). Diviser les deux membres par 25 donne \(uv=6\). Les paires positives ordonnées sont \((1,6)\) et \((2,3)\), toutes deux copremières. Elles donnent \((a,b)=(5,30)\) et \((10,15)\). Vérification : les deux produits valent 150, et les deux PGCD valent 5. Répondre seulement \((1,6)\) et \((2,3)\) donnerait les variables intermédiaires, pas les inconnues de l’énoncé.

À toi : Tentative : une autre relation entre les inconnues

Trouve tous les couples d’entiers positifs \((a,b)\) tels que \(a<b\), \(a+b=210\) et \(\operatorname{PGCD}(a,b)=30\). Choisis ton point de départ avant de lire l’indice.

Indice, à lire seulement si nécessaire. Réduis le couple par 30 ; cette fois, on obtient une somme et non un produit.

Ce que ta réponse doit montrer. Le couple réduit doit être copremier ; l’ordre borne la recherche ; la réponse doit être réécrite avec les nombres initiaux.

Correction expliquée : Somme, ordre et coprimalité

Posons \(a=30u,b=30v\), avec \(u,v>0\) entiers copremiers. L’égalité \(30u+30v=210\) devient \(30(u+v)=210\), puis \(u+v=7\) après division des deux membres par 30. Comme \(u<v\), on a \(2u<7\), donc \(u\in\{1,2,3\}\).

Les paires sont \((1,6),(2,5),(3,4)\), chacune copremière. Elles donnent \((30,180),(60,150),(90,120)\). Les sommes valent 210 et l’homogénéité du PGCD donne 30 dans chaque cas. La borne \(u<3{,}5\) justifie que la liste est complète, pas simplement une liste d’exemples.

À toi : Justification et changement de condition

1. Pourquoi faut-il vérifier \(\operatorname{PGCD}(u,v)=1\) dans la méthode précédente ?

2. Peut-il exister \(a,b\in\mathbb{N}^*\) tels que \(\operatorname{PGCD}(a,b)=10\) et \(ab=750\) ?

Ce que ta réponse doit montrer. Utiliser le carré du PGCD dans le produit, et distinguer une condition nécessaire d’une construction de solutions.

Correction expliquée : Une contrainte oubliée change le problème

1. Si \(a=du,b=dv\), alors \(\operatorname{PGCD}(a,b)=d\,\operatorname{PGCD}(u,v)\). Un facteur commun restant dans \(u,v\) rendrait le PGCD initial plus grand que \(d\).

2. La condition imposerait \(a=10u,b=10v\), donc \(ab=100uv\), multiple de 100. Or \(750/100=7{,}5\notin\mathbb{Z}\). Aucun couple ne convient. On n’a pas besoin d’une recherche de facteurs : l’intégralité de \(uv\) suffit à exclure la situation.

Pour réparer une erreur : Si tu oublies de revenir aux inconnues

Erreur. Annoncer \((u,v)=(1,6)\) comme réponse à un problème dont le PGCD demandé est 5. Le couple annoncé a un PGCD égal à 1.

Exemple plus simple. Si \(a=2u,b=2v\) et \((u,v)=(1,3)\), alors \((a,b)=(2,6)\), pas \((1,3)\).

Nouvel essai. Avec \(a=4u,b=4v\) et \((u,v)=(3,5)\), retrouve \(a,b\) et leur PGCD.

Correction. \(a=12,b=20\), et \(\operatorname{PGCD}(12,20)=4\).

Retour. Dans l’essai guidé, multiplie chaque coordonnée réduite par 5, puis contrôle le PGCD demandé.

À toi : À reprendre plus tard : un couple

Détermine les entiers positifs \(a<b\) tels que \(\operatorname{PGCD}(a,b)=7\) et \(ab=980\).

Indice, à lire seulement si nécessaire. Le produit réduit est \(980/49=20\).

Correction expliquée : Reprise différée sur la réduction

Écrivons \(a=7u,b=7v\), avec \(u<v\) copremiers. Alors \(49uv=980\), donc \(uv=20\). Les paires sont \((1,20),(2,10),(4,5)\) ; celle du milieu a un PGCD égal à 2 et doit être écartée. On obtient \((a,b)=(7,140)\) ou \((28,35)\). Le produit vaut bien 980 et les PGCD valent 7. Si tu avais conservé \((14,70)\), son PGCD 14 révélerait la condition de coprimalité oubliée.

Exemple expliqué : Ne pas oublier que le reste est plus petit

On cherche les entiers \(m>0\) tels que la division de 259 par \(m\) ait pour reste 7 et celle de 391 par \(m\) ait pour reste 13. Une division euclidienne exige une égalité et un encadrement du reste. Les conditions deviennent donc

À toi : Essai guidé puis variation

On divise 171 et 289 par le même entier \(m>0\), avec pour restes respectifs 3 et 9. Écris les deux divisibilités et la borne sur \(m\), puis trouve toutes les valeurs possibles. Explique pourquoi le candidat 7 doit être rejeté, même s’il divise les deux différences.

Indice, à lire seulement si nécessaire. Calcule \(\operatorname{PGCD}(168,280)\).

Correction expliquée : Divisibilité et borne sont cumulatives

Les conditions sont \(m\mid168\), \(m\mid280\) et \(m>9\). Comme \(280=168+112\), \(168=112+56\) et \(112=2\times56\), le PGCD vaut 56. Ses diviseurs positifs sont \(1,2,4,7,8,14,28,56\). Les valeurs admissibles sont donc \(14,28,56\), et elles conviennent toutes par les mêmes égalités et bornes.

Le nombre 7 divise bien 168 et 280, mais 9 n’est pas un reste possible dans une division par 7. L’égalité \(289=40\times7+9\) est vraie ; la division euclidienne est pourtant \(289=41\times7+2\). Voilà la première condition perdue si l’on retient seulement les diviseurs communs.

À toi : À tenter seul, puis à reprendre plus tard

Détermine tous les diviseurs positifs \(m\) pour lesquels les divisions de 103 et de 157 ont pour restes respectifs 7 et 13. Justifie que chaque candidat final convient.

Indice, à lire seulement si nécessaire. Les différences avec les restes sont 96 et 144.

Ce que ta réponse doit montrer. Faire apparaître les deux différences, leur PGCD, la condition stricte sur \(m\), puis une réciproque.

Correction expliquée : Un nouvel essai pour réparer l’oubli de la borne

Il faut et il suffit que \(m\) divise 96 et 144 et que \(m>13\). Puisque \(144=96+48\) et \(96=2\times48\), le PGCD vaut 48. Ses diviseurs positifs supérieurs à 13 sont \(16,24,48\). Pour chacun, les écritures \(103=m(96/m)+7\) et \(157=m(144/m)+13\) sont des divisions euclidiennes car les quotients sont entiers et les deux restes sont strictement inférieurs à \(m\).

Si tu avais gardé 12, reviens au cas simple \(31=4\times6+7\) : cette égalité n’est pas la division euclidienne par 6, puisque le reste doit être inférieur à 6 ; on écrit en réalité \(31=5\times6+1\). Reprends ensuite la tâche en rayant tous les candidats inférieurs ou égaux à 13. Le même exercice peut être retenté plus tard, sans relire ces lignes.

Définition : Un chiffrement affine sur 26 lettres

On associe aux lettres A à Z les rangs 0 à 25. Pour deux entiers fixés \(a,b\), on transforme un rang \(x\) en l’unique rang \(y\in\{0,\ldots,25\}\) vérifiant

Théorème : La condition pour décoder sans ambiguïté

Le chiffrement affine permet de retrouver chaque lettre de départ de façon unique si et seulement si \(\operatorname{PGCD}(a,26)=1\). Dans ce cas, si \(u\) est un inverse de \(a\) modulo 26, le décodage est

Démonstration : Existence du décodage, puis nécessité de la condition

Supposons d’abord \(\operatorname{PGCD}(a,26)=1\). Il existe \(u\) tel que \(ua\equiv1\;[26]\). De \(y\equiv ax+b\), on obtient \(y-b\equiv ax\), puis \(u(y-b)\equiv uax\equiv x\). Cette congruence donne un unique représentant dans \(0,\ldots,25\).

Réciproquement, pour un rang chiffré \(y\), prenons le reste \(x\) de \(u(y-b)\). Alors

Supposons maintenant \(d=\operatorname{PGCD}(a,26)>1\). Écrivons \(a=da'\), \(26=dm\), avec \(m=26/d\in\{1,\ldots,13\}\). Les deux rangs distincts 0 et \(m\) donnent des expressions dont la différence est

Méthode : Calculer une clé de décodage

Premier geste. Calculer \(\operatorname{PGCD}(a,26)\). S’il est différent de 1, chercher une collision plutôt qu’inventer une division. Sinon, trouver \(u\) tel que \(au\equiv1\;[26]\), par Bézout ou par une petite table de produits.

Soustraire \(b\), multiplier par \(u\), puis prendre le reste entre 0 et 25. Pour un nombre négatif, ajuster le quotient : le reste doit rester positif ou nul. Contrôler en réappliquant le chiffrement à la lettre retrouvée.

Exemple expliqué : La clé \((7,4)\)

Comme \(7\times15=105=4\times26+1\), l’entier 15 est inverse de 7 modulo 26. On chiffre avec \(y\equiv7x+4\), puis on déchiffre avec

Chiffrons le mot MATH :

Par exemple \(137=5\times26+7\) et \(53=2\times26+1\). Le message est donc KEHB.

Déchiffrons chaque rang avec \(15(y-4)\) :

À toi : Essai guidé : une nouvelle clé

On utilise \(y\equiv5x+8\;[26]\). Vérifie que 21 est inverse de 5, écris une formule de décodage, puis chiffre AXE et contrôle en déchiffrant.

Indice, à lire seulement si nécessaire. Les rangs d’AXE sont 0, 23 et 4. La formule de décodage peut garder les parenthèses.

Correction expliquée : Essai guidé de chiffrement

\(5\times21=105=4\times26+1\), donc \(x\equiv21(y-8)\;[26]\). Les trois valeurs \(5x+8\) sont 8, 123 et 28. Comme \(123=4\times26+19\) et \(28=26+2\), les rangs chiffrés sont 8, 19 et 2 : le message est ITC.

Pour contrôler : \(21(8-8)=0\) donne A ; \(21(19-8)=21\times11=231=8\times26+23\) donne X ; \(21(2-8)=21\times(-6)=-126=(-5)\times26+4\) donne E. La même formule traite donc les valeurs positives et négatives, si le reste est correctement choisi.

À toi : Tentative avant consultation : retrouver le message

Le message YP a été chiffré avec \(y\equiv9x+2\;[26]\). Retrouve le message initial et vérifie ton résultat en le chiffrant à nouveau.

Indice, à lire seulement si nécessaire. \(9\times3=27\). Les rangs de Y et P sont 24 et 15.

Ce que ta réponse doit montrer. Justifier l’inverse, soustraire le décalage avant de multiplier, ramener les résultats à \(0,\ldots,25\), puis contrôler.

Correction expliquée : Une congruence par lettre

\(9\times3=27=26+1\), donc 3 est inverse de 9. Pour Y, \(x\equiv3(24-2)=66\equiv14\;[26]\), car \(66=2\times26+14\) : c’est O. Pour P, \(x\equiv3(15-2)=39\equiv13\;[26]\) : c’est N. Le message initial est ON.

Contrôle : \(9\times14+2=128=4\times26+24\) donne Y ; \(9\times13+2=119=4\times26+15\) donne P. Les deux vérifications utilisent les lettres retrouvées, pas une simple relecture de la formule.

À toi : Justification et variation : une clé qui échoue

On propose \(y\equiv8x+4\;[26]\). Explique pourquoi il n’existe pas de décodage unique. Donne deux lettres différentes donnant la même lettre chiffrée. Peut-on obtenir une lettre de rang impair ?

Ce que ta réponse doit montrer. Relier le PGCD à une collision explicite et justifier la propriété de parité des restes.

Correction expliquée : La collision n’est pas une erreur de calcul

\(\operatorname{PGCD}(8,26)=2\ne1\). Les rangs 0 et 13 donnent respectivement \(8\times0+4=4\) et \(8\times13+4=108=4\times26+4\). A et N sont donc tous deux chiffrés en E : recevoir E ne permet pas de savoir lequel était le message.

Toute valeur \(8x+4\) est paire. En soustrayant un multiple de 26, également pair, son reste reste pair. Les rangs impairs ne sont jamais obtenus. La transformation ne réarrange donc pas les 26 lettres : elle en confond certaines et en omet d’autres.

Pour réparer une erreur : Si tu divises comme dans les réels

Erreur. De \(2x\equiv1\;[5]\), déduire \(x=1/2\). On cherche ici un entier et une congruence, pas une égalité réelle.

Exemple plus simple. \(2\times3=6\equiv1\;[5]\), donc \(x\equiv3\;[5]\). Le rang 3 convient parce que \(2\times3-1=5\).

Nouvel essai. Résous \(3x\equiv4\;[7]\), sachant que \(3\times5=15\equiv1\;[7]\).

Correction. Multiplions par 5 : \(x\equiv5\times4=20\equiv6\;[7]\). Contrôle : \(3\times6-4=14\), divisible par 7.

Retour. Pour la clé \((7,4)\), le multiplicateur de décodage est 15, un inverse modulo 26, pas la fraction réelle \(1/7\).

À toi : À reprendre plus tard : un décodage

Une lettre est chiffrée avec \(y\equiv11x+3\;[26]\). On reçoit P. Retrouve la lettre initiale en utilisant \(11\times19=209\), puis vérifie.

Indice, à lire seulement si nécessaire. \(209=8\times26+1\), et P a le rang 15.

Correction expliquée : Reprise différée sur l’inverse

19 est inverse de 11 modulo 26. Donc \(x\equiv19(15-3)=19\times12=228\;[26]\). Comme \(228=8\times26+20\), le rang est 20 : la lettre est U. Contrôle : \(11\times20+3=223=8\times26+15\), qui redonne P. Les deux gestes à retrouver sont la soustraction de 3 et la multiplication par l’inverse, dans cet ordre.

À retenir : L’essentiel

Le domaine des inconnues fait partie du problème. Après une réduction par le PGCD, revenir aux variables initiales. Pour décoder \(ax+b\) modulo 26, vérifier \(\operatorname{PGCD}(a,26)=1\), soustraire \(b\), multiplier par un inverse de \(a\), puis choisir le bon reste.

Complément facultatif : Un parcours à choisir après le noyau

Le lemme chinois et la recherche de racines rationnelles prolongent les outils du chapitre. Ils ne sont pas nécessaires pour apprendre à calculer un PGCD, obtenir une identité de Bézout ou résoudre une équation diophantienne simple.

Remarque : La boîte à outils locale

Pour un entier \(m\geq2\), \(x\equiv r\;[m]\) signifie \(m\mid(x-r)\), ou encore \(x=r+mk\) pour un entier \(k\). Deux entiers sont premiers entre eux lorsque leur PGCD vaut \(1\).

Le théorème de Bézout donne : si \(\operatorname{PGCD}(m,n)=1\), il existe des entiers \(u,v\) tels que \(mu+nv=1\). Le théorème de Gauss donne : si \(m\mid nz\) et \(\operatorname{PGCD}(m,n)=1\), alors \(m\mid z\). Ces résultats sont établis dans le noyau du chapitre ; ils sont rappelés ici avec leurs conditions pour que cette unité puisse être lue seule.

On utilisera également leur conséquence : si \(m\mid D\), \(n\mid D\) et \(\operatorname{PGCD}(m,n)=1\), alors \(mn\mid D\). En effet, \(D=mk\) ; comme \(n\mid mk\) et \(\operatorname{PGCD}(n,m)=1\), Gauss donne \(n\mid k\). On écrit \(k=nt\), puis \(D=mnt\).

Avant de commencer : Lire les deux conditions

Le nombre \(23\) laisse-t-il le reste \(2\) dans la division par \(7\) et le reste \(5\) dans la division par \(9\) ? Donne deux égalités, pas seulement « oui ».

Réponse. \(23=3\times7+2\) avec \(0\leq2<7\) et \(23=2\times9+5\) avec \(0\leq5<9\). Les deux conditions sont vérifiées. Une seule division ne suffirait pas. Si tu as testé \(23-2\) pour les deux modules, reprends le sens de chaque congruence : on soustrait son propre reste.

Lemme : Lemme chinois pour deux modules premiers entre eux

Soient \(m,n\geq2\) deux entiers premiers entre eux et \(r,s\in\mathbb{Z}\). Choisissons \(u,v\in\mathbb{Z}\) tels que \(mu+nv=1\), puis posons

Démonstration : Construction, puis totalité des solutions

De \(mu+nv=1\), on tire \(nv\equiv1\;[m]\) et \(mu\equiv1\;[n]\). D’autre part, \(mu\) est multiple de \(m\) et \(nv\) multiple de \(n\). Les deux poids agissent donc ainsi :

Par conséquent, \(x_0=rnv+smu\) est congru à \(r\times1+s\times0=r\) modulo \(m\), et à \(r\times0+s\times1=s\) modulo \(n\). Il est bien solution.

Si \(x\) est une autre solution, \(x-x_0\) est multiple de \(m\) et de \(n\). Ces modules étant premiers entre eux, leur produit divise \(x-x_0\) : il existe \(k\in\mathbb{Z}\) tel que \(x-x_0=mnk\), donc \(x=x_0+mnk\).

Réciproquement, ajouter \(mnk\) à \(x_0\) ajoute un multiple de chacun des deux modules : les deux congruences restent vraies. Cela prouve que tous les nombres annoncés, et seulement eux, sont solutions.

Enfin, la division euclidienne de \(x_0\) par \(mn\) donne un reste \(R\) entre \(0\) et \(mn-1\) qui est encore solution. Si deux représentants de cet intervalle différaient, leur différence serait un multiple non nul de \(mn\), donc aurait une valeur absolue au moins \(mn\). Or deux nombres de l’intervalle ont une différence de valeur absolue strictement inférieure à \(mn\) : impossible. Le représentant est unique.

Exemple expliqué : Construire puis vérifier un entier

On cherche \(x\equiv2\;[7]\) et \(x\equiv5\;[9]\). L’identité \(4\times7-3\times9=28-27=1\) permet de construire

Méthode : Construire avec Bézout ou substituer

Méthode de référence, avec Bézout. Vérifie d’abord que les modules sont premiers entre eux. Écris une identité \(mu+nv=1\), associe le reste \(r\) au poids \(nv\) et le reste \(s\) au poids \(mu\), calcule \(x_0\), puis réduis-le modulo \(mn\). Contrôle les deux restes. Termine par la famille entière, et par les contraintes du contexte s’il y en a.

Autre voie utile, par substitution. Écris d’abord \(x=r+mk\), puis impose la seconde condition. Sur le même exemple, \(x=2+7k\) donne \(2+7k\equiv5\;[9]\), donc \(7k\equiv3\;[9]\). Comme \(4\times7=28\equiv1\;[9]\), on multiplie par \(4\) et on obtient \(k\equiv12\equiv3\;[9]\). Cette transformation est réversible : multiplier \(k\equiv3\) par \(7\) donne \(7k\equiv21\equiv3\). Ainsi \(k=3+9t\) avec \(t\in\mathbb{Z}\), puis

À toi : Essai guidé : réduire une solution négative

Résous \(x\equiv1\;[5]\) et \(x\equiv6\;[8]\). Utilise \((-3)\times5+2\times8=1\). Construis d’abord \(x_0\), puis donne un représentant entre \(0\) et \(39\) et toutes les solutions entières.

Indice, à lire seulement si nécessaire. Le poids à associer au reste \(1\) est \(2\times8\), pas \((-3)\times5\).

Correction expliquée : Une solution négative se normalise

Les modules \(5,8\) sont premiers entre eux, puisque l’identité donnée vaut \(-15+16=1\). On calcule

À toi : À tenter avant de consulter : deux dispositifs périodiques

Un premier dispositif émet aux instants entiers \(t\geq0\) congrus à \(5\) modulo \(8\) ; un second émet aux instants congrus à \(4\) modulo \(11\). Les temps sont exprimés en minutes. Détermine tous les instants communs, puis le premier. Choisis la construction par Bézout ou la substitution et justifie la totalité des solutions.

Indice, à lire seulement si nécessaire. \(7\times8-5\times11=1\). Vérifie les deux restes de ton représentant final.

Correction expliquée : Une famille entière, puis la contrainte du temps

Les modules sont premiers entre eux grâce à \(56-55=1\). La construction donne

Pour le contexte, \(37+88k\geq0\) équivaut à \(88k\geq-37\), puis à \(k\geq-37/88\) en divisant par \(88>0\). Comme \(-1<-37/88<0\) et \(k\) est entier, cela impose \(k\geq0\). Les instants communs sont donc \(37+88k\) minutes avec \(k\in\mathbb{N}\) ; le premier est \(37\) minutes.

Ce que ta réponse doit montrer. Ta réponse doit vérifier la coprimalité, construire ou résoudre, vérifier les deux restes, expliquer le pas \(88\) et traiter la condition \(t\geq0\). Une seule valeur correcte ne décrit pas tous les instants.

À toi : Pourquoi les deux modules doivent-ils être premiers entre eux ?

Compare les deux systèmes suivants :

Système A : \(x\equiv1\;[4]\) et \(x\equiv2\;[6]\).

Système B : \(x\equiv1\;[4]\) et \(x\equiv3\;[6]\).

Le premier a-t-il une solution ? Pour le second, vérifie \(9\) et \(21\). Pourquoi la conclusion « une unique solution modulo \(24\) » serait-elle fausse ?

Correction expliquée : L’absence de coprimalité change la situation

Dans A, \(x=1+4k\) est impair, alors que \(x=2+6\ell\) est pair. Aucun entier ne peut satisfaire les deux conditions.

Dans B, \(9=2\times4+1=1\times6+3\), et \(21=5\times4+1=3\times6+3\) : les deux sont solutions. Pourtant \(21-9=12\) n’est pas multiple de \(24\) ; ce sont donc deux représentants distincts modulo \(24\). Comme \(\operatorname{PGCD}(4,6)=2\), le lemme n’est pas applicable. Sans sa condition, il peut y avoir absence de solution ou plusieurs classes modulo le produit.

Ce que ta réponse doit montrer. Il faut exhiber la contradiction de parité pour A et les deux vérifications pour B. « Le lemme ne s’applique pas » ne prouve pas, à lui seul, qu’un système est impossible.

Pour réparer une erreur : Si les deux restes ont été intervertis

Dans l’exemple \([7],[9]\), l’expression erronée \(2\times4\times7+5\times(-3)\times9=-79\) associe chaque reste au mauvais poids. Elle donne \(-79\equiv5\;[7]\) et \(-79\equiv2\;[9]\) : les restes sont échangés.

Rappel ciblé. Le poids du premier reste doit valoir \(1\) dans son module et \(0\) dans l’autre. Exemple plus simple : \(2\times3-1\times5=1\). Pour obtenir \(x\equiv1\;[3]\) et \(x\equiv2\;[5]\), on construit \(1\times(-5)+2\times6=-5+12=7\), et \(7=2\times3+1=1\times5+2\).

Nouvel essai. Avec \((-1)\times3+1\times4=1\), construis \(x\equiv2\;[3]\), \(x\equiv1\;[4]\). Correction. Les poids sont \(4\) et \(-3\), donc \(x_0=2\times4+1\times(-3)=5\) ; \(5=1\times3+2=1\times4+1\). Reviens à l’exemple initial : le poids de \(2\) est \(-27\), celui de \(5\) est \(28\), d’où \(86\), puis \(23\) modulo \(63\).

À toi : À reprendre plus tard : deux restes proches

Avant de relire, détermine tous les entiers \(x\) tels que \(x\equiv4\;[9]\) et \(x\equiv7\;[10]\). Justifie le module final et vérifie un représentant.

Indice, à lire seulement si nécessaire. Utilise \((-1)\times9+1\times10=1\), ou écris \(x=4+9k\).

Correction expliquée : Reprise différée des restes simultanés

L’identité assure la coprimalité de \(9\) et \(10\). On construit \(x_0=4\times10+7\times(-9)=40-63=-23\). Ajouter \(90\) donne \(67\). Les vérifications sont \(67=7\times9+4\) et \(67=6\times10+7\). Si \(x\) est une autre solution, \(x-67\) est multiple de \(9\) et de \(10\) ; Gauss donne qu’il est multiple de \(90\). Réciproquement, ajouter \(90k\) conserve les deux restes. Les solutions sont donc \(67+90k\), \(k\in\mathbb{Z}\).

Avant de commencer : Une fraction doit d’abord être irréductible

Écris \(-6/9\) sous forme irréductible avec un dénominateur positif. Puis vérifie si \(2/3\) est une racine de \(3x-2\).

Réponse. Diviser numérateur et dénominateur par leur PGCD \(3\) donne \(-6/9=-2/3\) ; \(\operatorname{PGCD}(2,3)=1\) et le dénominateur est positif. Ensuite \(3\times(2/3)-2=6/3-2=2-2=0\). Si la simplification te bloque, le point essentiel est que les deux nombres \(p,q\) de la fraction utilisée dans le théorème doivent être premiers entre eux.

Théorème : Théorème des racines rationnelles

Soit \(P(x)=a_dx^d+\cdots+a_1x+a_0\), où \(d\geq1\), les \(a_i\) sont entiers et \(a_d\ne0\). Si une racine rationnelle non nulle s’écrit \(p/q\) avec \(p\in\mathbb{Z}\), \(q\in\mathbb{N}^*\) et \(\operatorname{PGCD}(p,q)=1\), alors

Démonstration : Deux applications répétées de Gauss

De \(P(p/q)=0\), on obtient, en multipliant chaque terme par \(q^d\ne0\),

Dans la même égalité, tous les termes sauf le premier sont multiples de \(q\). Donc \(q\mid a_dp^d\). Comme \(\operatorname{PGCD}(q,p)=1\), Gauss permet de retirer les \(d\) facteurs \(p\), un par un : \(q\mid a_dp^{d-1}\), puis finalement \(q\mid a_d\).

Enfin, \(P(0)=a_0\) prouve directement l’affirmation sur la racine nulle. L’hypothèse de fraction irréductible a été utilisée exactement dans les applications de Gauss.

Corollaire : Lorsque le coefficient dominant vaut \(1\) ou \(-1\)

Si \(a_d=1\) ou \(a_d=-1\), toute racine rationnelle de \(P\) est entière.

Démonstration : Le dénominateur est imposé

Pour une racine non nulle \(p/q\) irréductible, le théorème impose \(q\mid1\) et \(q>0\), donc \(q=1\). La racine est \(p\), un entier. Si la racine est \(0\), elle est aussi entière.

Méthode : Chercher toutes les racines rationnelles

Vérifie que les coefficients sont entiers, puis relève le coefficient dominant et le terme constant. Si le terme constant est non nul, dresse les diviseurs relatifs \(p\) de \(a_0\) et les diviseurs positifs \(q\) de \(a_d\). Ne garde que les fractions \(p/q\) irréductibles, sans doublons. Ce sont les candidats. Substitue chacun dans \(P\) pour sélectionner ceux qui donnent zéro.

Une factorisation vérifiée peut raccourcir la sélection, mais le fait d’être candidat ne suffit jamais. Si \(a_0=0\), commence plutôt par mettre \(x\) en facteur : la liste des diviseurs de zéro n’est pas finie et ne fournit pas le même raccourci.

Exemple expliqué : Supprimer les dénominateurs sans perdre de facteur

Si \(p/q\), avec \(p\in\mathbb{Z}\) et \(q\in\mathbb{N}^*\), est une racine de \(6x^2-x-2\), alors

Exemple expliqué : Chercher et sélectionner, sans confondre les deux

Cherchons les racines rationnelles de \(P(x)=6x^2-x-2\). Le terme constant \(-2\) n’est pas nul : \(0\) n’est pas racine. Le théorème impose \(p\in\{-2,-1,1,2\}\) et \(q\in\{1,2,3,6\}\), avec \(\operatorname{PGCD}(p,q)=1\). La liste sans doublons est

Les signes du tableau viennent bien de \(-pq\) : pour \(p=-1,q=2\), on a \(-pq=-(-1)\times2=+2\). Les deux seules racines rationnelles sont donc \(-1/2\) et \(2/3\).

On peut contrôler par une factorisation exacte :

À toi : Essai guidé : quatre candidats

Pour \(P(x)=2x^2+x-1\), indique les diviseurs possibles de \(p\) et de \(q\), puis teste \(1,-1,1/2,-1/2\). Quels nombres sont des racines rationnelles ?

Indice, à lire seulement si nécessaire. Le terme constant vaut \(-1\) ; le coefficient dominant vaut \(2\).

Correction expliquée : Le théorème réduit la recherche, le calcul décide

On doit avoir \(p=1\) ou \(-1\) et \(q=1\) ou \(2\). Les quatre fractions proposées sont irréductibles. Les substitutions donnent

À toi : À tenter avant de consulter

Détermine toutes les racines rationnelles de \(3x^2-2x-1\). Explique pourquoi tu n’as pas à tester toutes les fractions possibles.

Indice, à lire seulement si nécessaire. Commence par la liste des numérateurs divisant \(-1\) et des dénominateurs positifs divisant \(3\).

Correction expliquée : Une liste finie justifiée

Les seuls candidats irréductibles sont \(1,-1,1/3,-1/3\). En posant \(P(x)=3x^2-2x-1\), on calcule

Ce que ta réponse doit montrer. Ta réponse doit préciser le caractère entier des coefficients, l’irréductibilité de la fraction testée, l’exhaustivité de la liste et les substitutions. Une liste de diviseurs n’est pas encore une liste de solutions.

À toi : Deux hypothèses à ne pas oublier

1. Le nombre \(2/4\) est racine de \(2x-1\). Pourquoi serait-il faux d’en déduire que \(4\) doit diviser \(2\) ?

2. Pour \(P(x)=4x^3-9x\), pourquoi le terme constant nul change-t-il le premier geste ? Trouve les racines rationnelles.

Correction expliquée : Fraction réduite et racine nulle

1. \(2/4=1/2\) n’est pas écrit sous forme irréductible dans la première écriture. Le théorème porte sur \(p=1,q=2\) ; \(2\) divise bien le coefficient dominant \(2\). Il ne porte pas sur n’importe quel dénominateur d’une écriture équivalente.

2. Ici \(P(0)=0\). On factorise d’abord : \(4x^3-9x=x(4x^2-9)\). Puis

Pour réparer une erreur : Si tous les candidats sont annoncés comme racines

Erreur proposée : « Pour \(x^2+1\), les candidats sont \(\pm1\), donc les racines sont \(\pm1\). » La première partie est correcte ; le mot donc est fautif. On a \((\pm1)^2+1=1+1=2\ne0\). Il n’y a donc aucune racine rationnelle.

Rappel ciblé. Une condition nécessaire élimine des possibilités sans garantir celles qui restent. Exemple plus simple : pour \(P(x)=x-2\), le théorème autorise \(\pm1,\pm2\) ; les valeurs sont \(-1,-3,0,-4\) respectivement. Seul \(2\) est racine.

Nouvel essai. Étudie les racines rationnelles de \(x^2-3\). Correction. Le coefficient dominant vaut \(1\), donc une racine rationnelle serait entière et diviserait \(-3\) : candidats \(\pm1,\pm3\). Or \(1-3=-2\) et \(9-3=6\). Aucun ne donne zéro ; il n’y a pas de racine rationnelle. Reviens au tableau de \(6x^2-x-2\) : seules les deux lignes dont le numérateur vaut zéro sont à retenir.