Correction détaillée des exercices 15 à 17 — Arithmétique dans Z — Algorithme d’Euclide et PGCD — Manuel Al Moufid

Correction détaillée des exercices 15 à 17 — Arithmétique dans \(\mathbb Z\)

Manuel Al Moufid · 2e Bac Sciences Mathématiques

Les exercices 15 à 17 utilisent l’algorithme d’Euclide pour calculer un PGCD et produire une relation de Bézout. Ils passent de calculs numériques avec de grands entiers à la construction de solutions particulières d’équations linéaires dans ℤ².

Une rédaction bien organisée garde, à chaque division, l’expression du reste en fonction des deux nombres initiaux. Ce suivi réduit les erreurs de signes et évite de refaire tout le calcul à la fin. Pour les équations, la dernière vérification doit toujours utiliser les coefficients de l’énoncé.

Repères de cours — Algorithme d’Euclide et relation de Bézout

L’égalité \(a=bq+r\) donne \(\gcd(a,b)=\gcd(b,r)\). En répétant les divisions, le dernier reste non nul est le PGCD. Pour des entiers négatifs, le PGCD est celui de leurs valeurs absolues.

À chaque étape, écrire le reste sous la forme \(r=ua+vb\) permet d’obtenir, au dernier reste non nul, \(\gcd(a,b)=u_0a+v_0b\). Les coefficients \(u_0,v_0\) sont entiers, peuvent être négatifs et ne sont pas uniques.

Pour \((a,b)\ne(0,0)\), l’équation \(ax+by=c\) admet des solutions entières si et seulement si \(\gcd(a,b)\mid c\). Une relation de Bézout multipliée par \(c/\gcd(a,b)\) donne une solution particulière. La propriété \(\gcd(ka,kb)=|k|\gcd(a,b)\) permet de simplifier les coefficients communs.

15 16 17

Exercice 15

Objectif et méthode — Exercice 15

Effectuer les divisions euclidiennes jusqu’au reste nul, puis prendre le dernier reste non nul comme PGCD. À chaque ligne, exprimer immédiatement le nouveau reste en fonction des deux nombres de départ. Cette organisation prépare la relation de Bézout et permet de contrôler les grands coefficients par substitution.

Énoncé

En utilisant l’algorithme d’Euclide, déterminer \(a\wedge b\) dans chacun des cas suivants :

Question 1 \[ a=604800 \qquad\text{et}\qquad b=176280. \]

Lire la correction + Masquer la correction −

Repère méthodologique. Pour alléger l’écriture, posons \(a=604800\) et \(b=176280\). À chaque étape, on exprime le nouveau reste seulement en fonction de \(a\) et \(b\).

D’après la proposition 2, le PGCD est le dernier reste non nul de l’algorithme d’Euclide.

\[ \begin{aligned} a&=3b+r_1 &&\Longrightarrow\quad r_1=a-3b,\\[2mm] b&=2r_1+r_2 &&\Longrightarrow\quad r_2=b-2r_1=7b-2a,\\[2mm] r_1&=3r_2+r_3 &&\Longrightarrow\quad r_3=r_1-3r_2=7a-24b,\\[2mm] r_2&=8r_3+r_4 &&\Longrightarrow\quad r_4=r_2-8r_3=199b-58a,\\[2mm] r_3&=2r_4+r_5 &&\Longrightarrow\quad r_5=r_3-2r_4=123a-422b,\\[2mm] r_4&=5r_5+r_6 &&\Longrightarrow\quad r_6=r_4-5r_5=2309b-673a=120,\\[2mm] r_5&=2r_6. \end{aligned} \]

Le dernier reste non nul est \(r_6=120\).

Donc \(\boxed{604800\wedge176280=120}\).

Question 2 \[ a=1309770 \qquad\text{et}\qquad b=571725. \]

Lire la correction + Masquer la correction −

Repère méthodologique. Posons \(a=1309770\) et \(b=571725\). On conserve ensuite seulement \(a\) et \(b\) dans les combinaisons linéaires des restes.

D’après la proposition 2, le PGCD est le dernier reste non nul de l’algorithme d’Euclide.

\[ \begin{aligned} a&=2b+r_1 &&\Longrightarrow\quad r_1=a-2b,\\[2mm] b&=3r_1+r_2 &&\Longrightarrow\quad r_2=b-3r_1=7b-3a,\\[2mm] r_1&=2r_2+r_3 &&\Longrightarrow\quad r_3=r_1-2r_2=7a-16b,\\[2mm] r_2&=3r_3+r_4 &&\Longrightarrow\quad r_4=r_2-3r_3=55b-24a=10395,\\[2mm] r_3&=2r_4. \end{aligned} \]

Le dernier reste non nul est \(r_4=10395\).

Donc \(\boxed{1309770\wedge571725=10395}\).

Exercice 16

Objectif et méthode — Exercice 16

Écrire \(b=105k\), puisque le PGCD recherché vaut \(105\), et utiliser \(630=105\times6\). La condition devient \(\gcd(6,k)=1\). Traduire l’encadrement de \(b\) en un encadrement entier de \(k\), puis conserver uniquement les valeurs premières avec \(6\).

Énoncé

Déterminer \(b\) tel que :

\[ 600<b<1100 \qquad\text{et}\qquad 630\wedge b=105. \]

Lire la correction + Masquer la correction −

Propriété utilisée. Si un entier est le PGCD de deux entiers, alors il divise chacun d’eux.

Comme \(630\wedge b=105\), on a en particulier \(105/b\). Il existe donc \(k\in\mathbb N^*\) tel que :

\[ b=105k. \]

D’autre part :

\[ 630=105\times6. \]

D’après les propriétés du PGCD :

\[ 630\wedge b =(105\times6)\wedge(105k) =105(6\wedge k). \]

Comme \(630\wedge b=105\), on obtient :

\[ 6\wedge k=1. \]

Par ailleurs, les inégalités \(600<b<1100\) donnent :

\[ 600<105k<1100. \]

D’où :

\[ k\in\{6;7;8;9;10\}. \]

Parmi ces entiers, seul \(7\) est premier avec \(6\). Ainsi :

\[ k=7 \qquad\text{et}\qquad b=105\times7=735. \]

Par conséquent, l’unique entier cherché est \(\boxed{b=735}\).

Exercice 17

Objectif et méthode — Exercice 17

Chercher une relation de Bézout par l’algorithme d’Euclide, en respectant l’ordre des coefficients dans \(ax+by\). Pour l’équation dont le second membre est \(105\), simplifier d’abord par le PGCD, puis multiplier une relation adaptée si nécessaire. Vérifier chaque couple trouvé dans l’équation d’origine, avec les bons signes.

Énoncé

Les questions 1), 2) et 3) sont indépendantes.

Question 1.a

On pose \(a=257\) et \(b=45\).

En utilisant l’algorithme d’Euclide, calculer \(a\wedge b\).

Lire la correction + Masquer la correction −

Repère méthodologique. Ici, \(a=257\) et \(b=45\). On exprime chaque reste en fonction de \(a\) et \(b\) dès qu’il apparaît.

D’après la proposition 2, le PGCD est le dernier reste non nul de l’algorithme d’Euclide.

\[ \begin{aligned} a&=5b+r_1 &&\Longrightarrow\quad r_1=a-5b,\\[2mm] b&=r_1+r_2 &&\Longrightarrow\quad r_2=b-r_1=6b-a,\\[2mm] r_1&=2r_2+r_3 &&\Longrightarrow\quad r_3=r_1-2r_2=3a-17b,\\[2mm] r_2&=2r_3+r_4 &&\Longrightarrow\quad r_4=r_2-2r_3=40b-7a=1,\\[2mm] r_3&=6r_4. \end{aligned} \]

Le dernier reste non nul est \(r_4=1\).

Donc \(\boxed{257\wedge45=1}\). Ainsi, \(257\) et \(45\) sont premiers entre eux.

Question 1.b

En déduire qu’il existe un couple \((\alpha;\beta)\in\mathbb Z^2\) tel que :

\[ a\alpha+\beta b=a\wedge b, \]

où \(\alpha\) et \(\beta\) sont à déterminer.

Lire la correction + Masquer la correction −

Propriété utilisée. Comme \(257\wedge45=1\), le théorème 3 de Bézout assure l’existence de deux entiers relatifs \(\alpha\) et \(\beta\) tels que \(257\alpha+45\beta=1\).

La question précédente donne déjà le dernier reste sous la forme :

\[ 1=r_4=40b-7a. \]

Donc :

\[ 1=-7a+40b=a\wedge b. \]

On peut donc prendre \(\boxed{(\alpha;\beta)=(-7;40)}\).

Question 2

En utilisant l’algorithme d’Euclide, déterminer deux entiers relatifs \(x\) et \(y\) tels que :

\[ 1050x+735y=1050\wedge735. \]

Lire la correction + Masquer la correction −

Repère méthodologique. Posons \(a=1050\) et \(b=735\). En exprimant chaque reste en fonction de \(a\) et \(b\) au fur et à mesure, les coefficients de Bézout apparaissent directement.

\[ \begin{aligned} a&=b+r_1 &&\Longrightarrow\quad r_1=a-b,\\[2mm] b&=2r_1+r_2 &&\Longrightarrow\quad r_2=b-2r_1=3b-2a=105,\\[2mm] r_1&=3r_2. \end{aligned} \]

Le dernier reste non nul est \(r_2=105\). Ainsi :

\[ a\wedge b=105 \qquad\text{et}\qquad 105=-2a+3b. \]

En revenant aux valeurs de \(a\) et \(b\), on obtient :

\[ 105=-2\times1050+3\times735. \]

Ainsi, on peut prendre \(\boxed{x=-2}\) et \(\boxed{y=3}\).

Question 3

En utilisant l’algorithme d’Euclide, calculer \(137\wedge726\), puis déterminer \((x_0;y_0)\in\mathbb Z^2\) tel que :

\[ 726x_0+137y_0=1. \]

Lire la correction + Masquer la correction −

Repère méthodologique. Pour effectuer l’algorithme dans l’ordre décroissant, posons \(a=726\) et \(b=137\). On exprime chaque reste en fonction de \(a\) et \(b\) dès la division où il apparaît.

\[ \begin{aligned} a&=5b+r_1 &&\Longrightarrow\quad r_1=a-5b,\\[2mm] b&=3r_1+r_2 &&\Longrightarrow\quad r_2=b-3r_1=16b-3a,\\[2mm] r_1&=2r_2+r_3 &&\Longrightarrow\quad r_3=r_1-2r_2=7a-37b,\\[2mm] r_2&=r_3+r_4 &&\Longrightarrow\quad r_4=r_2-r_3=53b-10a=1,\\[2mm] r_3&=13r_4. \end{aligned} \]

Le dernier reste non nul est \(r_4=1\). Donc :

\[ a\wedge b=1. \]

La même ligne donne directement :

\[ 1=-10a+53b =-10\times726+53\times137. \]

Par conséquent, \(\boxed{137\wedge726=1}\) et un couple convenable est \(\boxed{(x_0;y_0)=(-10;53)}\).

↑ Retour au menu principalTous les exercices d’arithmétique — Al Moufid

Note : Ce site est une ressource pédagogique indépendante et n'est pas affilié aux éditeurs du manuel Al Moufid.