Exercice 40

Notons $D=\mathrm{PGCD}(n^{3}+n,2n+1)$, bien défini car $2n+1\neq 0$.

• $D$ est premier avec $n$. Un diviseur commun de $D$ et $n$ divise $2n+1$ et $n$, donc $(2n+1)-2n=1$.

• $D$ divise $n^{2}+1$. $D$ divise $n^{3}+n=n(n^{2}+1)$ et est premier avec $n$ : d'après le théorème de Gauss, $D\mid n^{2}+1$.

• $D$ divise $5$. $D$ divise $4(n^{2}+1)$ et $(2n-1)(2n+1)=4n^{2}-1$, donc leur différence : $4n^{2}+4-4n^{2}+1=5$. Ainsi $D\in\{1\,;5\}$.

• Quand vaut-il $5$ ? Si $D=5$, alors $5\mid 2n+1$, soit $2n\equiv 4\;[5]$, d'où $n\equiv 2\;[5]$ en multipliant par $3$, inverse de $2$ modulo $5$. Réciproquement, si $n\equiv 2\;[5]$, alors $2n+1\equiv 5\equiv 0$ et $n^{3}+n=n(n^{2}+1)\equiv 2\times 5\equiv 0\;[5]$, donc $5\mid D$.

$$\boxed{\mathrm{PGCD}(n^{3}+n,2n+1)=\left\{\begin{array}{ll} 5 & \text{si } n\equiv 2\;[5] \\ 1 & \text{sinon} \end{array}\right.}$$ Contrôle : $n=2$ donne $\mathrm{PGCD}(10,5)=5$ ; $n=7$ donne $\mathrm{PGCD}(350,15)=5$ ; $n=3$ donne $\mathrm{PGCD}(30,7)=1$. On reconnaît la méthode de l'exercice 11 : écarter le facteur $n$, premier avec $2n+1$, puis éliminer $n$ par une combinaison linéaire.