Exercices
5 min
Non commencé
Déterminer le PGCD
Soit $ n $ un entier naturel.
On pose $ a=3n+1 $, $ b=5n+1 $ et $ d=PGCD\left(a;b\right) $.
- Montrer que $ d $ est un diviseur de 2.
- Déterminer les valeurs de $ d $ en fonction de $ n $.
Corrigé
$ d $ divise $ a $ et $ b $ donc il divise toute combinaison linéaire de $ a $ et $ b $ ; en particulier il divise :
$ 5a - 3b=5\left(3n+1\right) - 3\left(5n+1\right)=2 $
Remarque :
On a choisi les coefficients $ 5 $ et $ - 3 $ de façon à éliminer les $ n $...Les seuls diviseurs entiers naturels de $ 2 $ sont $ 1 $ et $ 2 $.
Par conséquent :
- Si $ n $ est pair, $ a $ et $ b $ sont impairs donc $ d $ ne peut pas être égal à $ 2 $, d'où $ d=1 $
- Si $ n $ est impair, $ a $ et $ b $ sont pairs donc $ d $ est également pair d'où $ d=2 $