# Arithmétique/Exercices/PPCM et PGCD
## Exercice 4-1

Pour chacun des couples d'entiers (a, b) suivants, trouver leur PPCM.
* a = 24 ; b = 56.
* a = 180 ; b = 450.
* a = 308 ; b = 4004.
* a = 120 ; b = 300.
* a = 72 ; b = 108.
* a = 175 ; b = 490.
* a/8 = 3 et b/8 = 7 sont premiers entre eux donc ppcm(a, b) = 8×ppcm(3, 7) = 8×3×7 = 168.
* a/90 = 2 et b/90 = 5 sont premiers entre eux donc ppcm(a, b) = 90×ppcm(2, 5) = 90×2×5 = 900.
* b = 13×a donc ppcm(a, b) = b.
* a/60 = 2 et b/60 = 5 sont premiers entre eux donc ppcm(a, b) = 60×ppcm(2, 5) = 60×2×5 = 600.
* a/36 = 2 et b/36 = 3 sont premiers entre eux donc ppcm(a, b) = 36×ppcm(2, 3) = 36×2×3 = 216.
* 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.
* a = 24 ; b = 56.
* a = 300 ; b = 750.
* a = 1386 ; b = 546.
* 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.
* 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.
* 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 ?
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 ?
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.
1° 108 = 2$^2$×3$^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 ℕ$^2$, 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}}$
a) x = 24a et y = 24b avec a et b premiers entre eux et ab = 16128/24$^2$ = 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$^2$ = 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$^2$ = 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.
* Démontrer que a + b et ab sont premiers entre eux.
* Déduisez-en que pgcd(x + y, m) = d.
* Voir Arithmétique/Exercices/Fractions, 1°.
* 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 ℕ$^2$, 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}}$
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.
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)$^2$ = 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.
1° g = pgcd(2n$^2$ – n, 2n$^2$ – 3n + 1) = pgcd(2n$^2$ – 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$^2$, 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$^2$, donc (a – b)$^2$ = a + b.
5° Soit (a, b) une solution ; notons c = a – b (> 0). Alors, c$^2$ = 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)$^2$b ≥ (k – 1)$^2$ 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$.
* Démontrer que $D_{n}=\operatorname {pgcd} \left(2n+1,n^{2}+100\right)$.
* En déduire que $D_{n}=\operatorname {pgcd} \left(2n+1,n^{2}+100,2(n^{2}+100)-(2n+1)n\right)$.
* En déduire que $D_{n}=\operatorname {pgcd} \left(401,n-200\right)$.
* En déduire les deux valeurs possibles de $D_{n}$.
* $D_{n}=\operatorname {pgcd} \left((n+1)^{2}+100-\left(n^{2}+100\right),n^{2}+100\right)$.
* Immédiat.
* $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}}$
* $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$^2$ + b$^2$ = 5409 et PPCM(a, b) = 360.
$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}}$
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$.