ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Étude du pgcd de deux entiers        niveau TerS SpéMath / Sup

 ➔  Extrait, baccalauréat La Réunion, 2000.

On considère, pour n entier naturel au moins égal à 5,  les deux entiers naturels :

a = n³ - n² - 12n  et  b = 2n² - 7n - 4

1°/ Soit δ le pgcd de 2n + 1 et n(n + 3). Prouver que pgcd(a,b) = δ(n + 4).

2°/ Prouver que n et 2n +1 sont premiers entre eux.

3°/  On pose α = 2n + 1 et β = n + 3.
     Établir entre α et β une relation indépendante de n. En déduire les diviseurs communs à α et β.

4°/ Montrer que α et β sont multiples de 5 si et seulement si n est congru à 2 modulo 5.

5°/ Prouver maintenant que δ = pgcd(α,β).

6°/ Déduire de l'étude précédente le pgcd de a et b selon les valeurs de n.

7°/ Vérifier les résultats obtenus lorsque a/ n = 11   b/ n = 12.

On considère, pour n entier naturel au moins égal à 5,  les deux entiers naturels :

a = n³ - n² - 12n  et  b = 2n² - 7n - 4

1°/ Soit δ le pgcd de 2n + 1 et n(n + 3). Prouver que pgcd(a,b) = δ(n - 4).

a = n(n² - n - 12) = n(n + 3)(n - 4), b = (2n + 1)(n - 4). Il suit que n - 4 divise a et b et les quotients sont respectivement n(n + 3) et (2n + 1). Si δ est leur pgcd, celui de a et b sera donc multiplié par n - 4.

2°/ Prouver que n et 2n +1 sont premiers entre eux.

2n + 1 - 2n = 1, ce qui peut s'écrire 1 × (2n + 1) - 2 × n = 1. Les entiers n et 2n + 1 vérifient donc l'identité de Bezout relative aux entiers premiers entre eux.

3°/  On pose α = 2n + 1 et β = n + 3. Établir entre α et β une relation indépendante de n.

2β = 2n + 6, donc 2β = α + 5. Si d est un diviseur commun à α et β, alors d divise 5 = 2β - α. Donc d = 1 ou 5.

4°/ Montrer que α et β sont multiples de 5 si et seulement si n est congru à 2 modulo 5.

La condition est suffisante :

Si n est congru à 2 modulo 5, n = 5k + 2, k ≥ 1 puisque n ≥ 5. On a alors α = 2n + 1 = 10k + 4 + 1 = 5(2k + 1), multiple de 5 et β = n + 3 = 5(k + 1), multiple de 5.

La condition est nécessaire :

Supposons α et β multiples de 5. Concernant β, il existe k ≥ 1 tel que β = 5k. On a n = β - 3 = 5k - 3 ≡ - 3 [5]. Or -3 ≡ 2 [5] . Donc n = 5k + 2, congru à 2 modulo 5.

Concernant α, on peut écrire α = 2n + 1 = 2(n - 2) + 5. 5 divise donc 2(n - 2) et ne divisant pas 2, il divise n - 2 : n est congru à 2 modulo 5.

5°/ Prouver maintenant que δ = pgcd(α,β).

δ est le pgcd de α = 2n + 1 et de nβ = n(n + 3). Montrons que les diviseurs communs à  α et β sont les diviseurs communs à α et nβ.

• Si d divise α et β, alors d divise n + 3, donc d divise n(n + 3) = nβ.
• Si d, distinct de 1, divise α et nβ, d ne peut diviser n car n et α = 2n + 1 sont premiers entre eux. donc d divise β (théorème de Gauss).

les paires d'entiers {α,β}et {α,nβ} ayant les mêmes diviseurs, elles ont même pgcd : pgcd(α,β) =  pgcd(α,nβ) = δ.

6°/ Déduire de l'étude précédente le pgcd de a et b selon les valeurs de n.

L'étude précédente montre que pgcd(a,b) = δ(n - 4) = (n - 4) × pgcd(α,β).

Si n ≡ 2 [5], alors α et β sont multiples de 5, donc (d'après 3°), leur pgcd est δ = 5. Donc pgcd(a,b) = 5(n - 4).
Sinon, α et β ne sont pas multiples de 5, donc δ = 1 et pgcd(a,b) = n - 4.

7°/ Vérifier les résultats obtenus lorsque a/ n = 11   b/ n = 12.

a/ n = 11 : a = 1078 = 2 × 7² × 11  et b = 161 = 7 × 23. Donc pgcd(a,b) = 7 = n - 4. Correct !
b/ n = 12 : a = 1440 =2⁵ × 3² × 5 et b = 200 = 2³ × 5². Donc pgcd(a,b) = 2³ × 5 = 5 × 8 = 5(n - 4). Correct !