Arithmétique avancée : PGCD paramétré, Gauss et applications

Exercice 4 — PGCD paramétré, théorème de Gauss et entiers premiers entre eux

Soit n un entier naturel non nul. On pose a = 2n + 3 et b = 3n + 4.

Partie A — Étude du PGCD

1. Montrer que $\text{pgcd}(a,b)=\text{pgcd}(2n+3,1)$ en effectuant une combinaison linéaire appropriée. En déduire que $\text{pgcd}(2n+3,3n+4)=1$ pour tout $n\in {\mathbb{N}}^{\ast }$.
2. En utilisant une autre combinaison, retrouver ce résultat en calculant $\text{pgcd}(a,b)$ via $\text{pgcd}(b,2b-3a)$.

Partie B — Application au théorème de Gauss

3. Soit p un entier naturel tel que $(2n+3)\mid p$ et $(3n+4)\mid p$. Montrer que $(2n+3)(3n+4)\mid p$. Quel théorème utilise-t-on ?
4. Déterminer le plus petit entier naturel non nul p divisible à la fois par $a=2n+3$ et $b=3n+4$, et exprimer $\text{ppcm}(a,b)$ en fonction de n.

Partie C — Équation et congruence

5. Montrer qu'il existe des entiers u et v tels que $(2n+3)u+(3n+4)v=1$. Trouver un couple solution pour $n=3$.
6. Pour $n=3$, résoudre dans $\mathbb{Z}$ l'équation (E) : $9x\equiv 5(\mathrm{mod}13)$ en utilisant les résultats précédents.