Aller au contenu

Devoir PGCD et Bézout

Les détails des calculs sont attendus.

L'usage de la calculatrice est autorisé.

Durée : 55 minutes

Exercice 1 (6 points)

  1. a. Déterminer le PGCD des nombres 168 et 20.

    Corrigé

    On applique l'algorithme d'Euclide :

    \(168 = 20 \times 8 + 8\)

    \(20 = 8 \times 2 + 4\)

    \(8 = 4 \times 2 + 0\)

    Donc \(PGCD(168; 20) = 4\)

    b. Soit l'équation \(168x + 20y = 6\) dont les inconnues \(x\) et \(y\) sont des entiers relatifs. Cette équation a-t-elle des solutions ?

    Corrigé

    D'après la question précédente, \(PGCD(168; 20) = 4\).

    Or \(4\) ne divise pas \(6\) (car \(6 = 4 \times 1 + 2\)).

    Donc l'équation \(168x + 20y = 6\) n'a pas de solution dans \(\mathbb{Z}^2\).

    c. Soit l'équation \(168x + 20y = 4\) dont les inconnues \(x\) et \(y\) sont des entiers relatifs. Cette équation a-t-elle des solutions ?

    Corrigé

    D'après la question a., \(PGCD(168; 20) = 4\).

    Or \(4\) divise \(4\).

    Donc l'équation \(168x + 20y = 4\) admet des solutions dans \(\mathbb{Z}^2\).

  2. a. Déterminer en détaillant les calculs effectués, deux entiers relatifs \(m\) et \(p\) tels que \(42m + 5p = 1\).

    Corrigé

    On applique l'algorithme d'Euclide étendu :

    \(42 = 5 \times 8 + 2\)

    \(5 = 2 \times 2 + 1\)

    \(2 = 1 \times 2 + 0\)

    Donc \(PGCD(42; 5) = 1\).

    On remonte l'algorithme :

    \(1 = 5 - 2 \times 2\)

    \(\phantom{1} = 5 - 2 \times (42 - 5 \times 8)\)

    \(\phantom{1} = 5 - 2 \times 42 + 16 \times 5\)

    \(\phantom{1} = 17 \times 5 - 2 \times 42\)

    \(\phantom{1} = 42 \times (-2) + 5 \times 17\)

    Donc \(m = -2\) et \(p = 17\) conviennent.

    b. En déduire deux entiers relatifs \(u\) et \(v\) tels que \(42u + 5v = 2\).

    Corrigé

    D'après la question précédente : \(42 \times (-2) + 5 \times 17 = 1\)

    En multipliant par \(2\) : \(42 \times (-4) + 5 \times 34 = 2\)

    Donc \(u = -4\) et \(v = 34\) conviennent.

    c. Démontrer que le couple d'entiers relatifs \((x; y)\) est solution de l'équation \(42x + 5y = 2\) si, et seulement si \(42(x + 4) = 5(34 - y)\).

    Corrigé

    On a \(42x + 5y = 2\) et \(42 \times (-4) + 5 \times 34 = 2\) (d'après b.)

    Par soustraction : \(42x + 5y - [42 \times (-4) + 5 \times 34] = 0\)

    \(\Leftrightarrow 42(x + 4) + 5(y - 34) = 0\)

    \(\Leftrightarrow 42(x + 4) = -5(y - 34)\)

    \(\Leftrightarrow 42(x + 4) = 5(34 - y)\)

    d. Déterminer tous les couples d'entiers \((x; y)\) d'entiers relatifs solutions de l'équation \(42x + 5y = 2\).

    Corrigé

    D'après la question c., on a \(42(x + 4) = 5(34 - y)\).

    Or \(PGCD(42; 5) = 1\), donc d'après le théorème de Gauss, \(5\) divise \((x + 4)\).

    Il existe donc \(k \in \mathbb{Z}\) tel que \(x + 4 = 5k\), soit \(x = 5k - 4\).

    En remplaçant dans \(42(x + 4) = 5(34 - y)\) :

    \(42 \times 5k = 5(34 - y)\)

    \(\Leftrightarrow 42k = 34 - y\)

    \(\Leftrightarrow y = 34 - 42k\)

    Les solutions de l'équation sont les couples \((5k - 4; 34 - 42k)\) avec \(k \in \mathbb{Z}\).

  3. Déduire du 2. les couples \((x; y)\) d'entiers relatifs solutions de l'équation \((42x + 5y - 3)(42x + 5y + 3) = -5\).

    Corrigé

    On pose \(X = 42x + 5y\). L'équation devient :

    \((X - 3)(X + 3) = -5\)

    \(\Leftrightarrow X^2 - 9 = -5\)

    \(\Leftrightarrow X^2 = 4\)

    \(\Leftrightarrow X = 2\) ou \(X = -2\)

    Cas 1 : \(42x + 5y = 2\)

    D'après 2.d., les solutions sont \((5k - 4; 34 - 42k)\) avec \(k \in \mathbb{Z}\).

    Cas 2 : \(42x + 5y = -2\)

    On résout de la même manière. D'après 2.b., \(42 \times (-4) + 5 \times 34 = 2\), donc \(42 \times 4 + 5 \times (-34) = -2\).

    Par un raisonnement analogue à 2.d., les solutions sont \((5k' + 4; -34 - 42k')\) avec \(k' \in \mathbb{Z}\).

    Conclusion : Les couples solutions sont :

    • \((5k - 4; 34 - 42k)\) avec \(k \in \mathbb{Z}\)
    • \((5k' + 4; -34 - 42k')\) avec \(k' \in \mathbb{Z}\)

Exercice 2 (4 points)

Soient \(a\), \(b\) et \(c\) trois entiers naturels non nuls.

  1. Montrer que : \(PGCD(a; b) = PGCD(bc - a; b)\).

    Corrigé

    Posons \(d = PGCD(a; b)\) et \(d' = PGCD(bc - a; b)\).

    Montrons que \(d \mid d'\) :

    • Puisque \(d = PGCD(a; b)\), on a : \(d \mid a\) et \(d \mid b\)
    • Donc \(d \mid b\) implique \(d \mid bc\)
    • Comme \(d \mid bc\) et \(d \mid a\), on a : \(d \mid (bc - a)\)
    • Ainsi \(d\) divise à la fois \((bc - a)\) et \(b\)
    • Donc \(d \mid PGCD(bc - a; b) = d'\)

    Montrons que \(d' \mid d\) :

    • Puisque \(d' = PGCD(bc - a; b)\), on a : \(d' \mid (bc - a)\) et \(d' \mid b\)
    • Donc \(d' \mid b\) implique \(d' \mid bc\)
    • Comme \(d' \mid bc\) et \(d' \mid (bc - a)\), on a : \(d' \mid [bc - (bc - a)] = a\)
    • Ainsi \(d'\) divise à la fois \(a\) et \(b\)
    • Donc \(d' \mid PGCD(a; b) = d\)

    Conclusion : Puisque \(d \mid d'\) et \(d' \mid d\), et que \(d\) et \(d'\) sont positifs, on a \(PGCD(a; b) = PGCD(bc - a; b)\).

  2. En déduire que, pour tout entier naturel \(k\), \(PGCD(a; b) = PGCD(a + kb; b)\).

    Corrigé

    D'après la question 1, en remplaçant \(c\) par \(-k\) :

    \(PGCD(a; b) = PGCD(b(-k) - a; b) = PGCD(-kb - a; b)\)

    Or \(PGCD(-kb - a; b) = PGCD(kb + a; b)\) car le PGCD ne dépend que des valeurs absolues.

    Donc \(PGCD(a; b) = PGCD(a + kb; b)\).

  3. Soit \(n\) un entier naturel. Déterminer le PGCD de \(7n + 3\) et \(21n + 11\).

    Corrigé

    Posons \(d = PGCD(7n + 3; 21n + 11)\).

    On cherche une relation entre \(21n + 11\) et \(7n + 3\) :

    \(21n + 11 = 3(7n + 3) + 2\)

    Donc \(21n + 11 - 3(7n + 3) = 2\)

    D'après la question 2 :

    \(d = PGCD(7n + 3; 21n + 11) = PGCD(7n + 3; 2)\)

    Analyse des cas :

    \(d\) divise \(2\), donc \(d \in \{1; 2\}\).

    • Si \(7n + 3\) est pair : alors \(7n\) est impair, donc \(n\) est impair. Dans ce cas, \(d = 2\).

    • Si \(7n + 3\) est impair : alors \(7n\) est pair, donc \(n\) est pair. Dans ce cas, \(d = 1\).

    Conclusion : \(PGCD(7n + 3; 21n + 11) = \begin{cases} 2 & \text{si } n \text{ est impair} \\ 1 & \text{si } n \text{ est pair} \end{cases}\)

  4. Déterminer tous les entiers naturels \(n\) tels que \(PGCD(7n + 3; 21n + 11) = 1\).

    Corrigé

    D'après la question 3, on a :

    \(PGCD(7n + 3; 21n + 11) = 1 \Leftrightarrow n \text{ est pair}\)

    Conclusion : L'ensemble des solutions est \(\{0, 2, 4, 6, 8, 10, \ldots\} = 2\mathbb{N}\).