Sommaire
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 3n-5 et de n-1.
À l'aide d'une combinaison linéaire, éliminer n dans un des termes
D'après le cours, on a :
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 :
\left(3n-5\right) -3\times\left(n-1\right) = 3n-5-3n+3=-2
Donc :
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 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 :
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 d=1 ou 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 3n-5 et n-1. On détermine alors la table des restes de la division euclidienne de 3n-5 et n-1 par 2 en fonction des valeurs de n :
| n\equiv \left[2\right] | 0 | 1 |
|---|---|---|
| 3n-5\equiv \left[2\right] | 1 | 0 |
| n-1\equiv \left[2\right] | 1 | 0 |
Donc 2 divise 3n-5 et n-1 si et seulement si n\equiv 1\left[2\right].
On en conclut :
- Si n est impair : PGCD \left(3n-5;n-1\right) =2
- Si n est pair : PGCD \left(3n-5;n-1\right) =1