Pgcd
Exercice 1. a est premier à b =⇒ pgcd(a, bc) = pgcd(a, c)
Soient a, b, c ∈ Z tels que a ∧ b = 1. Montrer que a ∧ (bc) = a ∧ c.
Exercice 2. pgcd(a + b, ppcm(a, b))
Soient a, b entiers, d = a ∧ b, m = a ∨ b. Chercher (a + b) ∧ m.
Exercice 3. pgcd((a − b)3 , a3 − b3 )
Soient a, b ∈ Z. Chercher (a − b)3 ∧ (a3 − b3 ).
Exercice 4. pgcd(n3 + n, 2n + 1)
Soit n ∈ N. Chercher (n3 + n) ∧ (2n + 1).
Exercice 5. pgcd(15n2 + 8n + 6, 30n2 + 21n + 13)
Soit n ∈ N. Chercher (15n2 + 8n + 6) ∧ (30n2 + 21n + 13).
Exercice 6. pgcd et ppcm imposés
Soient d, m ∈ N∗ . Donner une condition nécéssaire et suffisante sur d et m pour qu’il existe a, b ∈ Z tels que
a ∧ b = d et a ∨ b = m.
Résoudre ce problème pour d = 50 et m = 600.
Exercice 7. ppcm(x, y) + 11pgcd(x, y) = 203
Trouver les couples d’entiers (x, y) ∈ Z2 tels que : x ∨ y + 11(x ∧ y) = 203.
2
Exercice 8. x + y 2 = 85113, ppcm(x, y) = 1764
x2 + y 2 = 85113
Résoudre :
x ∨ y = 1764.
Exercice 9. ppcm(x,
y) = 210pgcd(x, y), y − x = pgcd(x, y)
x ∨ y = 210(x ∧ y)
Résoudre :
y − x = x ∧ y.
Exercice 10. pgcd(x, y) = x + y − 1
Résoudre dans Z : x ∧ y = x + y − 1.
Exercice 11. ppcm(x, y) = x + y − 1
Résoudre dans Z∗ : x ∨ y = x + y − 1.
Exercice 12. pgcd(x, y) = x − y, ppcm(x, y) = 300
∗
nx ∧y =x−y
Résoudre dans N :
x ∨ y = 300.
Exercice 13. pgcd(an − 1, am − 1)
Soient a, m, n ∈ N∗ , a > 2, et d = (an − 1) ∧ (am − 1).
1) Soit n = qm + r la division euclidienne de n par m. Démontrer que an ≡ ar [am − 1].
2) En déduire que d = (ar − 1) ∧ (am − 1), puis d = a(n∧m) − 1.
3) A quelle condition am − 1 divise-t-il an − 1 ?
Exercice 14. pgcd multiple
Soient a1 , . . ., an ∈ N∗ et bi =
Q
aj . Montrer que a1 , . . ., an sont deux à deux premiers entre eux si et seulement
j6=i
si b1 , . . ., bn sont premiers entre eux dans leur ensemble.
[Link] mardi 20 février 2007
Solutions
Exercice 2.
= d.
Exercice 3.
= |a − b|(a ∧ b)2 ou 3|a − b|(a ∧ b)2 .
Exercice 4.
3 2 si n ≡ 2 [5] , d=5
8(n + n) = (2n + 1)(4n − 2n + 5) − 5 =⇒ d = (2n + 1) ∧ 5 =⇒
si n ≡
6 2 [5] , d = 1.
Exercice 5.
= 1.
Exercice 6.
{a, b} ∈ {50, 600}, {150, 200} .
Exercice 7.
{a, b} ∈ {1, 192}, {3, 32}, {7, 126}, {14, 63} .
Exercice 8.
{x, y} = {147, 252}.
Exercice 9.
x = 14k, y = 15k.
Exercice 10.
x impair, y = 2 − x.
Exercice 11.
x = 1 ou y = 1.
Exercice 12.
(300, 150), (150, 100), (100, 75), (75, 60), (60, 50).
Exercice 13.
1) am − 1 | (aqm − 1)ar = an − ar .
2) A ∧ (AQ + R) = A ∧ R. Algorithme d’Euclide sur les exposants de a.
3) ssi m | n.
[Link] page 2