Déterminer le PGCD

Soit $n$ un entier naturel.

On pose $a=3n+1$ , $b=5n+1$ et $d=PGCD\left(a;b\right)$ .

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$