Un PGCD qui vaut 1 ou 11
Soit un entier naturel. On pose , et .
- 1.0,5pts
Montrer que .
- 2.1pts
En déduire que ou .
- 3.1pts
Résoudre dans l'équation .
- 4.0,5pts
En déduire que divise si et seulement si .
- 5.1,5pts
Montrer que si , et sinon.
- 6.0,5pts
Contrôler ce résultat pour , en calculant par l'algorithme d'Euclide.

Le PGCD divise et , donc toute combinaison linéaire de et de .
Essaie les onze classes , en réduisant modulo .
Si , calcule modulo . Sinon, peut-il être un diviseur commun ?
.
L'entier divise et . Par combinaison linéaire, divise .
Or est un entier naturel non nul, et est premier : ses seuls diviseurs positifs sont et . Donc ou .
Pour chaque classe , on calcule et on le réduit modulo .
La seule solution est .
On a si et seulement si , c'est-à-dire dans .
D'après la question 3, cela équivaut à , c'est-à-dire à .
Si . D'après la question 4, . Par compatibilité, , et , donc . Ainsi est un diviseur commun, donc ; avec la question 2, .
Sinon. D'après la question 4, : n'est pas un diviseur commun à et , donc . Avec la question 2, .
Pour , on a et . Comme , on divise par : Donc . C'est cohérent : , donc .
