PGCD, théorèmes de Bezout et Gauss

Calculer le PGCD de deux nombres exprimés en fonction de nn - Exercice 2

5 min
20
Question 1
Soit nn un entier naturel.

Déterminer en fonction de nn le PGCD de 2n+52n+5 et 3n+63n+6 .

Correction
Notons D=PGCD(2n+5;3n+6)D=\text{PGCD}\left(2n+5;3n+6\right)
DD divise 2n+52n+5 et DD divise 3n+63n+6 donc DD divise toute combinaison linéaire de 2n+52n+5 et 3n+63n+6 . Ainsi
DD divise (3×(2n+5)+(2)×(3n+6))\left(\blue{3}\times \left(2n+5\right)+\purple{\left(-2\right)}\times\left(3n+6\right)\right) . Ici, nous avons construit une combinaison lineˊaire indeˊpendante de\red{\text{combinaison linéaire indépendante de}} n\red{n}
DD divise (6n+156n12)\left(6n+15-6n-12\right)
DD divise 33
Il en résulte donc que D=1D=1 ou D=3D=3 .
Nous allons dresser la table des restes modulo 33 .
Le seul cas possible afin que 2n+52n+5 et 3n+63n+6 soient des multiples de 33 est n=2+3kn = 2 + 3k avec kNk \in \mathbb{N}
Ainsi :
  • Si nn est congru à 22 modulo 33 alors 2n+52n+5 et 3n+63n+6 sont donc divisibles par 33 et leur PGCD\text{PGCD} est égal à 33. Nous pouvons aussi écrire si n=2+3kn = 2 + 3k alors PGCD(2n+5;3n+6)=3\text{PGCD}\left(2n+5;3n+6\right)=3
  • Sinon 2n+52n+5 et 3n+63n+6 ne sont pas divisibles par 33 et leur PGCD\text{PGCD} est égal à 11. Nous pouvons aussi écrire si n2+3kn \ne 2 + 3k alors PGCD(2n+5;3n+6)=1\text{PGCD}\left(2n+5;3n+6\right)=1