Calculer le PGCD de deux nombres exprimés en fonction de $$n$$ - Exercice 1

Notons $$D=\text{PGCD}\left(n+2;3n+1\right)$$
$$D$$ divise $$n+2$$ et $$D$$ divise $$3n+1$$ donc $$D$$ divise toute combinaison linéaire de $$n+2$$ et $$3n+1$$ . Ainsi
$$D$$ divise $$\left(\blue{3}\times \left(n+2\right)+\purple{\left(-1\right)}\times\left(3n+1\right)\right)$$ . Ici, nous avons construit une $$\red{\text{combinaison linéaire indépendante de}}$$ $$\red{n}$$
$$D$$ divise $$\left(3n+6-3n-1\right)$$
$$D$$ divise $$5$$
Il en résulte donc que $$D=1$$ ou $$D=5$$ .
Nous allons dresser la table des restes modulo $$5$$ .
Le seul cas possible afin que $$n+2$$ et $$3n+1$$ soient des multiples de $$5$$ est $$n = 3 + 5k$$ avec $$k \in \mathbb{N}$$
Ainsi :

Si $$n$$ est congru à $$3$$ modulo $$5$$ alors $$n+2$$ et $$3n+1$$ sont donc divisibles par $$5$$ et leur $$\text{PGCD}$$ est égal à $$5$$. Nous pouvons aussi écrire si $$n = 3 + 5k$$ alors $$\text{PGCD}\left(n+2;3n+1\right)=5$$

Sinon $$n+2$$ et $$3n+1$$ ne sont pas divisibles par $$5$$ et leur $$\text{PGCD}$$ est égal à $$1$$. Nous pouvons aussi écrire si $$n \ne 3 + 5k$$ alors $$\text{PGCD}\left(n+2;3n+1\right)=1$$