Afin de calculer le PGCD de deux nombres exprimés en fonction de n, on supprime n dans un des termes, on cherche les diviseurs de l'entier obtenu puis on donne la valeur du PGCD en fonction de n.
Déterminer en fonction de n le PGCD de \(\displaystyle{3n-5}\) et de \(\displaystyle{n-1}\).
À l'aide d'une combinaison linéaire, éliminer n dans un des termes
D'après le cours, on a :
\(\displaystyle{PGCD \left(a;b\right) =PGCD \left(a-kb ; b\right)}\) où k est un entier.
On utilise cette propriété afin d'éliminer les n dans un des deux termes.
Par combinaison linéaire :
\(\displaystyle{\left(3n-5\right) -3\times\left(n-1\right) = 3n-5-3n+3=-2}\)
Donc :
\(\displaystyle{PGCD \left(3n-5;n-1\right) =PGCD \left(3n-5 ; -2\right)=PGCD \left(3n-5 ; 2\right)}\)
Chercher les diviseurs de l'entier obtenu
On pose \(\displaystyle{d = PGCD \left(a;b\right)}\).
On sait que d divise l'entier déterminé à l'étape précédente.
On cherche tous les diviseurs de cet entier.
On pose :
\(\displaystyle{d = PGCD \left(3n-5;n-1\right) =PGCD \left(3n-5 ; 2\right)}\).
On sait ainsi que d divise 2.
On en déduit que \(\displaystyle{d=1 }\) ou \(\displaystyle{d=2}\).
Conclure selon les valeurs de n
Pour chacun des diviseurs de d, on détermine, à l'aide d'un tableau, la valeur du PGCD en fonction de n.
D'après le résultat précédent, les seules valeurs possibles pour d sont 1 et 2.
Or, d doit diviser \(\displaystyle{3n-5}\) et \(\displaystyle{n-1}\). On détermine alors la table des restes de la division euclidienne de \(\displaystyle{3n-5}\) et \(\displaystyle{n-1}\) par 2 en fonction des valeurs de n :
| \(\displaystyle{n\equiv \left[2\right]}\) | 0 | 1 |
|---|---|---|
| \(\displaystyle{3n-5\equiv \left[2\right]}\) | 1 | 0 |
| \(\displaystyle{n-1\equiv \left[2\right]}\) | 1 | 0 |
Donc 2 divise \(\displaystyle{3n-5 }\) et \(\displaystyle{n-1}\) si et seulement si \(\displaystyle{n\equiv 1\left[2\right]}\).
On en conclut :
- Si n est impair : \(\displaystyle{PGCD \left(3n-5;n-1\right) =2}\)
- Si n est pair : \(\displaystyle{PGCD \left(3n-5;n-1\right) =1}\)