Cours Stage - PGCD, algorithme d'Euclide

Exercice - Divisibilité et PGCD

L'énoncé

\(a\), \(b\), \(p\) et \(q\) sont des entiers relatifs tels que : \(a = 9 p + 4 q\) et \(b = 2 p + q\).


Question 1

Démontrer que : \(PGCD (a, b) = PGCD (p, q)\)

Soit \(d\) un diviseur commun de \(a\) et de \(b\).
\(d\) divise toute combinaison linéaire à coefficients entiers de \(a\) et de \(b\) donc \(d\) divise \(9p + 4q - 4 ( 2p + q )\), donc \(d\) divise \(p\).
De même \(d\) divise \(q\).

Ainsi tout diviseur de \(a\) et \(b\) est un diviseur de \(p\) et \(q\).
Réciproquement, soit d' un diviseur de \(p\) et \(q\).
Alors \(d'\) divise \(9p + 4q\) et \(2p + q\) donc \(d'\) divise \(a\) et \(b\).
L'ensemble des diviseurs de \(a\) et \(b\) est donc égal à l'ensemble des diviseurs de \(p\) et \(q\),
Ainsi :  (\PGCD (a, b) = PGCD (p, q)\)

On ne peut pas démontrer directement cette égalité. Il faut prouver tout d’abord que : \(D (a, b) = D (p, q )\) où \(D (a, b )\) est l’ensemble des diviseurs communs positifs de \(a\) et \(b\).


Il faut démontrer l’inclusion de ces deux ensembles, dans un sens puis dans l’autre pour obtenir l’égalité.


Connaissez –vous la propriété du cours : « Si \(d\) divise \(a\) et \(b\), alors \(d\) divise toute combinaison linéaire à coefficients entiers de \(a\) et de \(b\). » Sinon vous devez l’apprendre par cœur.


Ecrire \(p\) et \(q\) sous forme de combinaisons linéaires de \(a\) et de \(b\).

Question 2

Déterminer en fonction de l'entier \(p\), le PGCD de \((9p + 4)\) et \((2p + 1)\).

Première méthode :

On utilise la question précédente avec $q=1$. On obtient : \(PGCD (9p + 4, 2p + 1) = PGCD (p, 1)=1\)

 

Deuxième méthode :

Posons la division euclidienne de $9p+4$ par $2p+1$

$9p+4= 4\times (2p+1)+p$

$2p+1= 2\times p+1$

Le dernier reste de cette division est $1$ donc  \(PGCD (9p + 4, 2p + 1) =1\)

Conclusion : \(PGCD (9p + 4, 2p + 1) = PGCD (p, 1) = 1\)

C’est une application directe de la question 1.


Pensez à poser \(q = 1\).

Question 3

Quelles sont les valeurs possibles du PGCD de \(9p + 4\) et \(2p - 1\) ?

Donner les valeurs de \(p\) correspondantes.

Soit \(d\) un diviseur de \(9p + 4\) et \(2p - 1\). \(d\) divise alors \(2(9p + 4) - 9(2p - 1)\) donc \(d\) divise 17.
Les valeurs possibles du PGCD de \(9p + 4\) et \(2p 1\) sont donc 1 et 17.

\(PGCD (9p + 4, 2p - 1) = 17 \Leftrightarrow S \left\{ \begin{array}{left} 9p+4 \equiv 0(17) \\ 2p-1 \equiv 0(17) \end{array}\right. \)

Si \(p\) est solution de \(S\) alors   \(9p+4-4(2p-1) \equiv 0(17)\)   soit   \(p \equiv 9(17)\)

Réciproquement,

Si \(p = 9+17k\)  alors  \(9p+4 = 17(9k+5)\)

Soit : \(9p+4 \equiv 0(17)\)

De même : \(2p-1 = 17(2k+1)\)

Soit \(2p-1 \equiv 0(17)\)  

Donc \(p\) est solution de \(S\).


Ainsi, $17$ est le PGCD de \(9p + 4\) et \(2p -1\) si et seulement si \(p\) sécrit \(17k + 9\), où \(k\) est un entier relatif.
Dans tous les autres cas, le PGCD est 1.

Former une combinaison linéaire des deux nombres qui élimine \(p\). Le PGCD de \(9p + 4\) et \(2p – 1\) divise cette combinaison linéaire.


Vous obtenez deux valeurs possibles, 1 et 17. Etudier d’abord le cas où le PGCD vaut 17. Former ainsi une combinaison linéaire de \(9p + 4\) et \(2p – 1\) qui est égale à \(p\). Trouver ainsi les valeurs de \(p\) correspondant à ce cas.


Si le PGCD vaut 17, alors vous avez trouvé \(p\). N’oubliez pas la réciproque ! Si \(p\) s’écrit comme ça, est-on certain que le PGCD vaut 17 ?


Vous n’avez trouvé que deux valeurs possibles. Le PGCD vaut donc 1 dans tous les autres cas, c’est-à-dire dès que \(p\) est différent des valeurs trouvées précédemment.