Arithmétique/Exercices/PPCM et PGCD

Exercice 4-1

Pour chacun des couples d'entiers (a, b) suivants, trouver leur PPCM.

1. a = 24 ; b = 56.
2. a = 180 ; b = 450.
3. a = 308 ; b = 4004.
4. a = 120 ; b = 300.
5. a = 72 ; b = 108.
6. a = 175 ; b = 490.

Solution

1. a/8 = 3 et b/8 = 7 sont premiers entre eux donc ppcm(a, b) = 8×ppcm(3, 7) = 8×3×7 = 168.
2. a/90 = 2 et b/90 = 5 sont premiers entre eux donc ppcm(a, b) = 90×ppcm(2, 5) = 90×2×5 = 900.
3. b = 13×a donc ppcm(a, b) = b.
4. a/60 = 2 et b/60 = 5 sont premiers entre eux donc ppcm(a, b) = 60×ppcm(2, 5) = 60×2×5 = 600.
5. a/36 = 2 et b/36 = 3 sont premiers entre eux donc ppcm(a, b) = 36×ppcm(2, 3) = 36×2×3 = 216.
6. a/35 = 5 et b/35 = 14 sont premiers entre eux donc ppcm(a, b) =35×ppcm(5, 14) = 35×5×14 = 2450

 

Exercice 4-2

Pour chacun des couples d'entiers (a, b) suivants, trouver leur PGCD et déduisez-en leur PPCM.

1. a = 24 ; b = 56.
2. a = 300 ; b = 750.
3. a = 1386 ; b = 546.

Solution

1. a/8 = 3 et b/8 = 7 sont premiers entre eux donc pgcd(a, b) = 8 et ppcm(a, b) = ab/8 = 3b = 7a = 168.
2. a/150 = 2 et b/150 = 5 sont premiers entre eux donc pgcd(a, b) = 150 et ppcm(a, b) = ab/150 = 2b = 5a = 1500.
3. a/42 = 33 et b/42 = 13 sont premiers entre eux donc pgcd(a, b) = 42 et ppcm(a, b) = ab/42 = 33b = 13a = 18018.

 

Exercice 4-3

Le PPCM de deux nombres est 216. L'un des deux nombres est 72. Quel est l'autre ?

Solution

Les deux nombres sont x = ad et y = bd = 72 avec a et b premiers entre eux et d tels que 216 = abd = 72a, donc a = 3, d = 9k et bk = 8. L'autre nombre est donc x = 27k avec k = 1, 2, 4 ou 8, c'est-à-dire x = 27, 54, 108 ou 216.

 

Exercice 4-4

Quel est le plus petit entier strictement supérieur à 40 qui, divisé par 140 et par 252, donne 40 comme reste ?

Solution

n – 40 doit être > 0 et divisible par ppcm(140, 252) = ppcm(5×28, 9×28) = 5×9×28 = 1260. La plus petite valeur est 1260 + 40 = 1300.

 

Exercice 4-5

1° Trouvez tous les diviseurs naturels de 108.

2° Trouvez tous les couples (x, y) d'entiers naturels dont le PGCD d et le PPCM m sont tels que m – 3d = 108, avec 10 < d < 15.

Solution

1° 108 = 2²×3³ a pour diviseurs positifs tous les nombres de la forme 2^p×3^q avec 0 ≤ p ≤ 2 et 0 ≤ q ≤ 3 (il y en a 3×4 = 12).

2° x = ad et y = bd et m = abd avec a et b premiers entre eux.

108 = m – 3d = (ab – 3)d et 10 < d < 15 donc d = 12 et ab = 12 donc {a, b} = {3, 4} et {x, y} = {36, 48} ou {a, b} = {1, 12} et {x, y} = {12, 144}.

 

Exercice 4-6

Résolvez dans ℕ², les systèmes :

a) ${\begin{cases}xy=16128\\\operatorname {pgcd} (x,y)=24\end{cases}}$

b) ${\begin{cases}xy=1734\\\operatorname {pgcd} (x,y)=17\end{cases}}$

c) ${\begin{cases}xy=439230\\\operatorname {pgcd} (x,y)=121\end{cases}}$

Solution

a) x = 24a et y = 24b avec a et b premiers entre eux et ab = 16128/24² = 28 donc {a, b} = {1, 28} et {x, y} = {24, 672}, ou {a, b} = {4, 7} et {x, y} = {96, 168}.

b) x = 17a et y = 17b avec a et b premiers entre eux et ab = 1734/17² = 6 donc {a, b} = {2, 3} et {x, y} = {34, 51}, ou {a, b} = {1, 6} et {x, y} = {17, 102}.

c) x = 121a et y = 121b avec a et b premiers entre eux et ab = 439230/121² = 30 donc {a, b} = {5, 6} et {x, y} = {605, 726}, ou {a, b} = {3, 10} et {x, y} = {363, 1210}, ou {a, b} = {2, 15} et {x, y} = {242, 1815}, ou {a, b} = {1, 30} et {x, y} = {121, 3630}.

 

Exercice 4-7

x et y sont deux entiers naturels, m est leur PPCM, d leur PGCD, et l'on note a et b les entiers tels que x = ad et y = bd.

1. Démontrer que a + b et ab sont premiers entre eux.
2. Déduisez-en que pgcd(x + y, m) = d.

Solution

1. Voir Arithmétique/Exercices/Fractions#Exercice 7-4, 1°.
2. Se déduit de la question précédente et des égalités x + y = (a + b)d et m = (ab)d.

 

Exercice 4-8

Résolvez, dans ℕ², les systèmes :

a) ${\begin{cases}xy=1512\\\operatorname {ppcm} (x,y)=252\end{cases}}$

b) ${\begin{cases}xy=300\\\operatorname {ppcm} (x,y)=60\end{cases}}$

c) ${\begin{cases}x+y=276\\\operatorname {ppcm} (x,y)=1440\end{cases}}$

Solution

x = ad et y = bd avec a et b premiers entre eux et :

a) d = 1512/252 = 6 et ab = 252/6 = 42 donc {a, b} = {6, 7} et {x, y} = {36, 42}, ou {a, b} = {3, 14} et {x, y} = {18, 84}, ou {a, b} = {2, 21} et {x, y} = {12, 126}, ou {a, b} = {1, 42} et {x, y} = {6, 252}.

b) d = 300/60 = 5 et ab = 60/5 = 12 donc {a, b} = {3, 4} et {x, y} = {15, 20}, ou {a, b} = {1, 12} et {x, y} = {5, 60}.

c) d = pgcd(1440, 276) (d'après l'exercice précédent) = pgcd(12×120, 12×23) = 12, ab = 1440/12 = 120 et a + b = 276/12 = 23, donc {a, b} = {8, 15} et {x, y} = {96, 180}.

 

Exercice 4-9

Trouver deux entiers positifs x et y sachant que leur PGCD est 24 et que leur PPCM est 1344.

Solution

x = 24a et y = 24b avec a et b premiers entre eux et ab = 1344/24 = 56 donc {a, b} = {7, 8} et {x, y} = {168, 192} ou {a, b} = {1, 56} et {x, y} = {24, 1344}

 

Exercice 4-10

a et b sont deux entiers tels que a > b > 0 ; g est leur PGCD et m leur PPCM.

1°  Pour cette question, a = n(2n – 1) et b = (n – 1)(2n – 1), avec n entier positif. Déterminez alors g et m.

2°  Soient p et q premiers entre eux tels que p > q > 0. Exprimer, en fonction de p et q, les nombres a et b tels que m(a + b) = abg [1], p = a/g et q = b/g.

3°  Parmi les nombres a et b qui satisfont à la relation [1], trouver ceux qui satisfont à g = a – b [2].

4°  Démontrer que les couples (a, b) qui satisfont à la fois à [1] et à [2], sont tels que (a – b)² = a + b [3].

5°  Soit un entier r > 0. Calculer en fonction de r (lorsqu'il en existe) les solutions (a, b) de [3] pour lesquelles r est le reste de la division de a par b, et préciser la valeur de g correspondante.

6°  Même question pour r = 0.

Solution

1°  g = pgcd(2n² – n, 2n² – 3n + 1) = pgcd(2n² – n, –2n + 1) = 2n – 1 et m = ab/g = n(2n – 1)(n – 1).

2°  ab = mg, donc m(a + b) = abg équivaut à a + b = g², ou encore : p + q = g. On a alors : a = p(p + q) et b = q(p + q).

3°  Si de plus g = a – b, c'est-à-dire p – q = 1 alors g = 2q + 1 (donc g impair > 1), a = g(g + 1)/2 et b = g(g – 1)/2.

4°  S'il existe un entier c > 1 tel que a = c(c + 1)/2 et b = c(c – 1)/2 alors (même si c est pair) a – b = c et a + b = c², donc (a – b)² = a + b.

5°  Soit (a, b) une solution ; notons c = a – b (> 0). Alors, c² = c + 2b donc b = c(c – 1)/2 et a = b + c = c(c + 1)/2. Enfin, c > 3 (d'après l'hypothèse 0 < r < b) donc r = c (car on a bien c < b).

Par conséquent, il n'y a pas de solution si r = 1, 2 ou 3, tandis que pour r > 3, l'unique solution est (a, b) = (r(r + 1)/2, r(r – 1)/2), et g est égal à r/2 si r est pair et à r si r est impair.

6°  Soit (a, b) une solution. Alors, b divise a (donc g = b). Notons k l'entier a/b (> 1). On a k + 1 = (k – 1)²b ≥ (k – 1)² donc k ≤ 3. Les deux seules solutions (a, b) sont donc (6, 3) et (3, 1).

 

Exercice 4-11

Pour $n\in \mathbb {N}$, soit $D_{n}$ le PGCD des deux entiers $n^{2}+100$ et $(n+1)^{2}+100$.

1. Démontrer que $D_{n}=\operatorname {pgcd} \left(2n+1,n^{2}+100\right)$.
2. En déduire que $D_{n}=\operatorname {pgcd} \left(2n+1,n^{2}+100,2(n^{2}+100)-(2n+1)n\right)$.
3. En déduire que $D_{n}=\operatorname {pgcd} \left(401,n-200\right)$.
4. En déduire les deux valeurs possibles de $D_{n}$.

Solution

1. $D_{n}=\operatorname {pgcd} \left((n+1)^{2}+100-\left(n^{2}+100\right),n^{2}+100\right)$.
2. Immédiat.
3. $D_{n}=\operatorname {pgcd} \left(2n+1,n^{2}+100,200-n\right)$ (d'après la question précédente) donc
   ${\begin{aligned}D_{n}&=\operatorname {pgcd} \left(2n+1+2(200-n),n^{2}+100+(200+n)(200-n),200-n\right)\\&=\operatorname {pgcd} \left(401,100\times 401,200-n\right)\\&=\operatorname {pgcd} \left(401,n-200\right).\end{aligned}}$
4. $401$ est premier donc s'il divise $n-200$ alors $D_{n}=401$ et sinon, $D_{n}=1$.

 

Exercice 4-12

Trouvez deux entiers positifs a et b tels que a² + b² = 5409 et PPCM(a, b) = 360.

Solution

$3$ divise $360=\operatorname {ppcm} (a,b)$ donc il divise $a$ ou $b$, donc $9$ divise $a^{2}$ ou $b^{2}$. Comme $9$ divise aussi $5409=a^{2}+b^{2}$, il divise $a^{2}$ et $b^{2}$. Donc $3$ divise $a$ et $b$.

Soient $c=a/3$ et $d=b/3$. Alors, $\operatorname {ppcm} (c,d)=120$ et $c^{2}+d^{2}=601$, premier avec $120$, donc $c$ et $d$ sont premiers entre eux et $cd=120$, donc

$(c-d)^{2}=601-2.120=361=19^{2}$ et

$(c+d)^{2}=601+2.120=841=29^{2}$.

La solution est $\{c,d\}=\{5,24\}$, c'est-à-dire $\{a,b\}=\{15,72\}$.

 

Exercice 4-13

Déterminer tous les triplets $(a,b,c)\in (\mathbb {N} ^{*})^{3}$ vérifiant :

${\begin{cases}\operatorname {ppcm} (a,b)&=42\\\operatorname {pgcd} (a,c)&=3\\a+b+c&=29\end{cases}}$

Solution

Analyse : $a=3a'$, $c=3c'$, $b=29-a-c\equiv 2{\bmod {3}}$, donc $\operatorname {ppcm} (a',b)=14$, en particulier $b\mid 14$, donc $b=2$ ou $14$.

• Si $b=2$ : $a'+c'=9$ et $\operatorname {ppcm} (a',2)=14$ donc $a'=7$ et $c'=2$, d'où $(a,b,c)=(21,2,6)$.
• Si $b=14$ : $a'+c'=5$ et $a'\mid 14$ donc $(a',c')=(1,4)$ ou $(2,3)$, d'où $(a,b,c)=(3,14,12)$ ou $(6,14,9)$.

Synthèse : on vérifie que les trois seuls triplets possibles trouvés sont effectivement solutions, car on a bien pour chacun d'eux : $\operatorname {pgcd} (a',c')=1$.

 

Liens externes

• « Calculateur de PPCM », sur dcode.fr
• « Calculateur de PGCD », sur dcode.fr, par trois méthodes
• « Décomposition en facteurs premiers », sur dcode.fr