PGCD : exercices page 1 de 2

PGCD : exercices

Les solutions ne sont pas entièrement rédigées. ce ne sont que des indications, qui se- Réponse = n = 1 + 7k (avec k > 0).
raient insuffisantes sur une copie. Assurez-vous que vous comprenez bien toutes les 3n + 2
étapes et que vous savez les détailler et les justifier en utilisant des théorèmes du cours 6. Déterminer l’ensemble des n entiers naturels non nuls tels que la fraction soit
n+2
(voir la deuxième section : théorème utilisés). irréductible.
1. a, b sont des entiers naturel non nuls. 3n + 2 = 3(n + 2) − 4, donc (lemme d’Euclide) :
Démontrer que PGCD(a3 , b3 ) = (PGCD(a, b))3 PGCD(3n + 2, n + 2) = PGCD(n + 2, −4) = PGCD(n + 2, 4).
Indications : utiliser la décomposition en facteurs premiers de a et b, appliquer à On cherche donc les n tels que PGCD(n + 2, 4) = 1, c’est-à-dire différent de 2 et
partir de là la méthode pour calculer le PGCD (facteurs premiers communs, plus de 4 (diviseurs de 4).
petits exposants). Faire de même avec a3 et b3 et comparer les résultats. PGCD(n + 2, 4) = 1 ⇔
2. Démontrer l’équivalence entre les deux propriétés P1 et P2 suivantes, pour a entier ⇔ n + 2 n’est divisible ni par 4 ni par 2
relatif :
⇔ n + 2 est impair
P1 : L’équation ax ≡ 1 [6] n’a aucune solution x dans Z
P2 : a est divisible par 2 ou par 3. ⇔ n est impair.
Indications : 7. Soient a et a deux entiers relatifs premiers entre eux, A = 11a + 2b et B = 18a + 5b.
Par contraposée : Exprimer a et b en fonction de A et B et en déduire que tout diviseur commun à A et
B est un diviseur commun à 19a et 19b.
L’équation ax ≡ 1 [6] a au moins une solution ⇔
Calculer PGCD(A, B).
⇔ a est premier avec 6 (Bézout) à préciser
19a = 5A − 2B et 19b = −18A + 11B.
⇔ a n’est divisible ni par 2 ni par 3 (décomposition en facteurs premiers de 6).
Donc (combinaisons linéaires) PGCD(A, B) divise 19a et 19b.
3. m et n sont des entiers naturels non nuls.
Donc (théorème) il divise PGCD(19a, 19b).
Démontrer que, si m est premier avec n2 , alors m est premier avec n
m n’a aucun facteur premier commun avec n2 , les facteurs premiers de n2 sont les Or PGCD(19a, 19b) = 19PGCD(a, b) (théorème).
mêmes que ceux de n, donc m n’a aucun facteur premier commun avec n Comme PGCD(a, b) = 1, PGCD(19a, 19b) = 19. Donc PGCD(A, B) = 19 ou 1.
Ou bien : am + bn2 = 1 ⇒ am + kn = 1 ⇒ m et n premiers entre eux (Bézout). C’est 19 si et seulement si A et B sont divisibles par 19, sinon c’est 1.
4. a et n sont deux entiers naturels non nuls, et premiers entre eux. 8. On considère l’équation 3x − 5y = 2
Démontrer que l’équation ax ≡ 2 [n] ne peut pas avoir plus d’une solution x dans Démontrer l’équivalence suivante : (a, b) est solution ⇔ (a + 5k, b + 3k) est solution.
[0; n − 1]. Trouver toutes les solutions avec 0 6 y 6 2 et en déduire l’ensemble des solutions.
Par l’absurde : si ax ≡ 2 [n] et ay ≡ 2 [n] avec x et y dans [0; n − 1], alors 3(a + 5k) − 5(b + 3k) = 3a − 5b.
a(x − y) est divisible par n, donc x − y est divisible par n (Gauss). Donc : (a, b) est solution ⇔ (a + 5k, b + 3k) est solution.
Or −(n − 1) 6 x − y 6 n − 1. Donc la seule possibilité est x − y = 0, soit x = y. Puisque y = b + 3k d’après ce qui précède, il suffit d’essayer les valeurs de y dans
5. Déterminer tous les n entiers naturels tels que PGCD(5n + 2, 4n + 3) = 7. {0, 1, 2}. On trouve (x = 4, y = 2).
Lemme d’Euclide : PGCD(5n + 2, 4n + 3) = · · · = PGCD(n − 1, 7) L’ensemble des solution s est {(4 + 5k, 2 + 3k); k ∈ Z}
PGCD(a, b) = b ⇔ b divise a. 9. Déterminer l’ensemble des couples (x, y) d’entiers relatifs tels que 37x + 22y = 2
PGCD : exercices page 2 de 2

On trouve une solution particulière de 37x + 22y = 1 (possible car 37 et 22 sont • Théorème de Gauss.
premiers entre eux) : (25, −42) (par exemple en remontant l’algorithme d’Euclide Attention, dans ce théorème, ne pas oublier l’hypothèse fondamentale : a et b sont
1 − 37x premiers entre eux.
ou bien en affichant le tableau des valeurs de , ce qui permet de conjecturer
22 D’autre part, ne pas oublier que ce théorème n’est qu’une implication et pas une
une solution et de la vérifier). équivalence.
On multiplie par 2 : (50, −84). • Lemme d’Euclide
On applique ensuite la méthode habituelle (voir cours) en utilisant le théorème de Ne pas le généraliser inconsidérément. Dans ce théorème, un des deux nombres doit
Gauss et en n’oubliant pas la réciproque : (x, y) = (50 − 22k, −84 + 37k) être conservé. Ne pas changer les deux nombres à la fois.
• Quels sont tous les multiples de n qui sont compris entre −(n − 1) et n − 1 ?
10. Avec la liste des nombres premiers de 2 à 59, combien faut-il faire de divisions eucli-
diennes pour vérifier que 2011 est premier ? On admettra que 2011 est premier. • PGCD(a, b) = b ⇔ ...? .
Démontrer qu’il existe un multiple de 2011 qui ne s’écrit qu’avec des chiffres 9 (utiliser C’est une équivalence, on peut s’en servir dans les deux sens.
le petit théorème de Fermat avec les puissances de 10). • Attention : dire que PGCD(a, kp) = p n’est pas équivalent à dire que p divise a (même
si p est premier).
On essaye√ toutes les divisions par les nombres premiers inférieurs ou
• Qu’est-ce qu’une fraction irréductible ?
égaux à 2011 ≈ 44, 84. Les nombres premiers inférieurs à 44 sont :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43. Il y en a 14. • Si un nombre divise a et b, alors il divise ...? (et la réciproque est vraie aussi).
D’après le petit théorème de Fermat : puisque 10 est premier avec 2011, on a • PGCD(ka, kb) = ...? (piège si k < 0).
102010 ≡ 1 [2011]. Donc 102010 − 1 est divisible par 2011. • Lorsque p est un nombre premier, dire que PGCD(a, b) = p équivaut à ...? .
Ce nombre est solution, puisqu’il s’écrit uniquement avec des chiffres 9 (2010 chiffres Attention à bien obtenir une équivalence, et pas seulement : PGCD(a, b) est un mul-
9), puisque 10 2010 2
− 1 = 9(1 + 10 + 10 + · · · + 10 2009
) (somme des termes d’une tiple de p.
suite géométrique). • Savoir comment on trouve une solution particulière (x, y) de ax+by = 1 en remontant
l’algorithme d’Euclide, puis comment on en déduit ensuite toutes les solutions (en
11. Démontrer que, si a est premier avec b et c, alors il est premier avec bc. faisant attention d’obtenir une équivalence).
Il existe u et v tels que au + bv = 1 (Bézout). De même au0 + cv 0 = 1. On multiplie • Equation ax + by = c lorsque c = PGCD(a, b).
les deux égalités entre elles. On obtient ax + bcy = 1, donc a est premier avec bc Savoir se ramener à a0 x + b0 y = 1
(Bézout). • Attention à l’équation ax + by = c lorsque c n’est pas le PGCD de a et b.
Ou bien : a n’a aucun facteur premier commun avec b ni avec c, donc il ne peut Les solutions ne se déduisent pas directement de celles de ax + by = PGCD(a, b)
pas en avoir avec bc, puisque bc n’a pas d’autres facteurs premiers que ceux de b et • Petit théorème de Fermat.
ceux de c. Ne pas oublier l’hypothèse fondamentale : a est premier avec p (et p est premier).
Donc ne pas pas appliquer le théorème dans des situations non adaptées.
12. m et n sont deux entiers naturels non nuls. calculer PGCD(mn, n(2m + 1))
PGCD(mn, n(2m + 1)) = nPGCD(m, 2m + 1) (théorème)
Or PGCD(m, 2m + 1) = 1 puisque m et 2m + 1 sont premiers entre eux (Bézout :
(2m + 1) − m = 1).
Donc PGCD(mn, n(2m + 1)) = n

Théorèmes utilisés (à retrouver)