Exercice : PGCD, Algorithme d'Euclide et Théorème de Bézout

Étape 1

Soit $n$ un entier naturel. On cherche à déterminer les diviseurs communs possibles des entiers $A(n) = 3n^2 + 11n + 19$ et $B(n) = 2n + 3$.

Étape 2

On cherche une combinaison linéaire entre $A(n)$ et $B(n)$ permettant d'éliminer la variable $n$. En effectuant la division synthétique de $4 A(n)$ par $B(n)$, on obtient :$$4 A(n) = 12n^2 + 44n + 76 = (2n + 3)(6n + 13) + 37$$

Étape 3

On en déduit la relation suivante :$$4 A(n) - (6n + 13) B(n) = 37$$Soit $d$ un diviseur commun à $A(n)$ et $B(n)$. D'après cette relation, $d$ divise $37$. Or, $37$ est un nombre premier. Les seuls diviseurs positifs de $37$ sont donc $1$ et $37$. Par conséquent, $\text{PGCD}(A(n), B(n))$ vaut soit $1$, soit $37$.

Étape 4

Les entiers $A(n)$ et $B(n)$ ne sont pas premiers entre eux si et seulement si leur PGCD vaut $37$, c'est-à-dire si $37$ divise à la fois $A(n)$ et $B(n)$.

Étape 5

Supposons que $37$ divise $B(n)$, c'est-à-dire que $2n + 3 \equiv 0 \pmod{37}$. Comme $4 A(n) = (6n + 13) B(n) + 37$, il vient que $37$ divise $4 A(n)$. Or, $\text{PGCD}(4, 37) = 1$. D'après le théorème de Gauss, $37$ divise $A(n)$.

Étape 6

Ainsi, $A(n)$ et $B(n)$ ne sont pas premiers entre eux si et seulement si $2n + 3 \equiv 0 \pmod{37}$.

Étape 7

Résolvons cette congruence :$$2n + 3 \equiv 0 \pmod{37} \text{ ce qui équivaut à } 2n \equiv -3 \pmod{37}$$Comme $-3 \equiv 34 \pmod{37}$, l'équation devient $2n \equiv 34 \pmod{37}$. Puisque $\text{PGCD}(2, 37) = 1$, on peut diviser par $2$, ce qui donne $n \equiv 17 \pmod{37}$.

Étape 8

Les entiers naturels $n$ vérifiant cette condition sont de la forme $n = 17 + 37k$ avec $k \in \mathbb{N}$. On calcule les premières valeurs : pour $k = 0$, $n = 17$ ; pour $k = 1$, $n = 54$ ; pour $k = 2$, $n = 91$ ; pour $k = 3$, $n = 128$.

Étape 9

Le plus petit entier naturel $n \ge 100$ tel que $A(n)$ et $B(n)$ ne soient pas premiers entre eux est donc $128$.