Exercice 1.
1. a, b et q appartiennent à ℤ , alors PGCD(a, b) = PGCD(b, a – bq).
Montrons que D(a, b) = D(b, a – bq).
Soit d ∈ ℤ . Si d/a et d/b, alors d/(a-bq) ; et réciproquement si d/b et d/(a-bq), alors d/(bq+a-bq), soit d/a.
2. n ∈ ℤ, 5n 3 − n = (n + 2)(5n 2 −10n + 19) − 38 .
D’après1., PGCD(5n 3 − n, n + 2) = PGCD(n + 2, −38) = PGCD(n + 2, 38) .
3. (n+2)/ (5n 3 − n)
⇔ PGCD(5n 3 − n, n + 2) = n + 2
⇔ PGCD(n + 2,38) = n + 2
⇔ (n + 2) / 38
⇔ n + 2 = ±1, ±2, ±19, ±38
⇔ n ∈ {−40, −21, −4, −3, −1, 0,17,36}
4. PGCD(5n 3 − n, n + 2) = PGCD(n + 2,38) , les valeurs possibles font partie des diviseurs strictement
positifs de 38, soit 1, 2, 19 et 38.
Ce PGCD vaut 19 si 19 divise n+2 et si 38 ne divise pas n+2, soit n + 2 = 19(2p + 1) , où p ∈ ℤ ,
Ce qui équivaut à n ≡ 17 [38] .
Exercice 2.
k ∈ ℤ . On : 9k + 4 = 4(2k - 1) + k + 8 et 2k – 1 = 2(k + 8) – 17, donc, d’après l’exercice 1,
PGCD(x, y) = PGCD(k + 8, 17).
Les valeurs possibles de ce PGCD sont donc 1 et 17.
Il est égal à 17 si et ssi 17 divise k + 8, soit k ≡ 9[17 ] , sinon il vaut 1.
Exercice 3.
1. n ∈ ℤ . On a : 9n – 5 = 3(3n+4) – 17, donc, d’après l’exercice1, PGCD(A, B) = PGCD(3n+4, 17).
Les valeurs possibles de ce PGCD sont donc 1 et 17.
Ce PGCD vaut 17 si et ssi 17 divise 3n + 4.
Cherchons les valeurs de n pour lesquelles il existe k ∈ ℤ tel que 3n + 4 = 17k.
Résolvons l’équation : 17k – 3n = 4 (1). 17 × (−1) − 3(−6) = 1 , donc (-4, -24) est une solution particulière
de (1).
On a :
17k − 3n = 4
⇔ 17k − 3n = 17 × (−4) − 3 × (−24)
⇔ 17(k + 4) = 3(n + 24) (2)
3 divise 17(k + 4) et PGCD( 17, 3) = 1, donc, d'après le théorème de Gauss, 3 divise k + 4 ; il existe donc
p ∈ ℤ tel que k + 4 = 3p. Il vient alors, en remplaçant dans (2), 17 × 3p = 3(n + 24) , soit n + 24 = 17p.
Les solutions sont donc :
k = −4 + 3p
n = −24 + 17p, p ∈ ℤ
Conclusion : si n ≡ 10[17] , alors PGCD(A, B) = 17, sinon il vaut 1.
2. PGCD(A, B ) = 17, donc il existe h ∈ ℤ tel que n = 10 + 17h.
On a alors : A = 17(2 + 3h) , B = 17(5 + 9 h) et PPCM(A, B) = 17× (2 + 3h)(5 + 9h) .
On cherche h tel que 27h 2 + 33h + 10 = 52 . On a :
27h 2 + 33h + 10 = 52
⇔ 27h 2 + 33h − 42 = 0 ou 27h 2 + 33h + 62 = 0 (ici ∆<0)
⇔ h = −2 ou h = 7 / 9
Seul h = -2 convient, ce qui donne A = - 68 et B = - 221.
Exercice 4.
On considère sur ℤ 2 l’équation : 324x − 245y = 7 (1).
1. On a : 245 = 5.7 2 , 324 = 22.34 , donc 7 divise 245 et PGCD(7, 324) = 1.
Soit (x, y) une solution de (1), alors 324x = 7 + 245y, donc 7 divise 324x ; or PGCD(7, 324) = 1, donc, par
le théorème de Gauss, 7 divise x.
2. PGCD(324, 245) = 1, en utilisant l’algorithme, on trouve 324× (−31) − 245(−41) = 1 .
(-217, -287) est une solution particulière de (1).
On a :
324x − 245y = 7
⇔ 324x − 245y = 324 × (−217) − 245 × (−287)
⇔ 324(x + 217) = 245(y + 287) (2)
245 divise 324(x + 217) et PGCD( 324, 245) = 1, donc, d'après le théorème de Gauss, 245 divise x + 217 ;
il existe donc p ∈ ℤ tel que x + 217 = 245p. Il vient alors, en remplaçant dans (2),
324 × 245p = 245(y + 287) , soit y + 287 = 324p.
Les solutions sont donc :
x = −217 + 245p
y = −287 + 324p, p ∈ ℤ
3. Soit (x, y) une solution de (1) et PGCD(x, y) = d, d divise x et d divise y, donc d divise 324x – 245y,
soit d divise 7. Les valeurs possibles de d sont 1 et 7.
Cherchons les solutions de (1) pour lesquelles d vaut 7.
7 divise x, donc d vaut 7 si et ssi 7 divise y. Or 7 divise 287, donc 7 divise y si et ssi 7 divise 324p.
PGCD(7, 324) = 1, donc, par le théorème de Gauss, 7 divise 324p si et ssi 7 divise p.
Conclusion : PGCD(x, y) = 7 si et ssi p est un multiple de 7, sinon PGCD(x, y) = 1.
