# Arithmétique/Exercices/Diviseurs communs
## Exercice 3-1

Pour chacun des entiers naturels a et b donnés, trouver l'ensemble des diviseurs D(a) et D(b). Déduisez-en le PGCD de a et b.
1° a = 48 ; b = 32.
2° a = 120 ; b = 168.
3° a = 60 ; b = 96.
1° a = 2$^4$×3 donc D(a) = {2$^p$×3$^q$ | 0 ≤ p ≤ 4 et 0 ≤ q ≤ 1}.
    b = 2$^5$ donc D(b) = {2$^p$ | 0 ≤ p ≤ 5}.
    D(a)∩D(b) = {2$^p$ | 0 ≤ p ≤ 4} donc pgcd(a,b) = 2$^4$ = 16.
2° a = 2$^3$×3×5 donc D(a) = {2$^p$×3$^q$×5$^r$ | 0 ≤ p ≤ 3, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
    b = 2$^3$×3×7 donc D(b) = {2$^p$×3$^q$×7$^r$ | 0 ≤ p ≤ 3, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
    D(a)∩D(b) = {2$^p$×3$^q$ | 0 ≤ p ≤ 3 et 0 ≤ q ≤ 1} donc pgcd(a,b) = 2$^3$×3 = 24.
3° a = 2$^2$×3×5 donc D(a) = {2$^p$×3$^q$×5$^r$ | 0 ≤ p ≤ 2, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
    b = 2$^5$×3 donc D(b) = {2$^p$×3$^q$ | 0 ≤ p ≤ 5 et 0 ≤ q ≤ 1}.
    D(a)∩D(b) = {2$^p$×3$^q$ | 0 ≤ p ≤ 2 et 0 ≤ q ≤ 1} donc pgcd(a,b) = 2$^2$×3 = 12.

## Exercice 3-2

Dans les exemples suivants, indiquez si les nombres a et b sont premiers entre eux.
1° a = 42 ; b = 65.
2° a = 285 ; b = 1463.
3° a = 360 ; b = 707.
1° Oui car 11b – 17a = 1.
2° Non car a et b sont divisibles par 19.
3° Oui car 707×83 – 360×163 = 1.

## Exercice 3-3

Trouver le PGCD des nombres suivants :
a) 360 et 2100 ;
b) 468 et 312 ;
c) 700 et 840 ;
d) 1640 et 492.
a) pgcd(6×60, 35×60) = 60 ;
b) pgcd(3×156, 2×156) = 156 ;
c) pgcd(5×140, 6×140) = 140 ;
d) pgcd(10×164, 3×164) = 164.

## Exercice 3-4

Expliquer pourquoi, dans chacun des cas suivants, on peut donner très rapidement le PGCD de a et b.
1° $a=5\times 12,\,b=11\times 12$
2° $a=3\times 15,\,b=8\times 15$
3° $a=22\times 26,\,b=15\times 26$
1° 5 et 11 sont premiers entre eux donc pgcd(a, b)=12.
2° 3 et 8 sont premiers entre eux donc pgcd(a, b)=15.
3° 22 et 15 sont premiers entre eux donc pgcd(a, b)=26.

## Exercice 3-5

Trouver le PGCD des trois nombres a, b, c.
1° a = 162 ; b = 270 ; c = 180.
2° a = 504 ; b = 630 ; c = 1764.
Note : Le PGCD de trois entiers est le plus grand des diviseurs positifs communs à ces trois entiers.
1° pgcd(a, c) = pgcd(9×18, 10×18) = 18 | b donc pgcd(a, b, c) = 18.
2° pgcd(a, b) = pgcd(126×4, 126×5) = 126 | c donc pgcd(a, b, c) = 126.

## Exercice 3-6

a et b sont deux entiers, a = 18 ; trouvez quelles sont les valeurs de b sachant que b est premier avec a et 20 < b < 30.
b n'est divisible ni par 2, ni par 3 donc b = 23, 25 ou 29.

## Exercice 3-7

a et b sont deux entiers, a = 630 ; le PGCD de a et b est égal à 105 ; 600 < b < 1100. Trouver b.
b = 105c, c premier avec 630/105 = 14 et strictement compris entre 600/105 et 1100/105 c'est-à-dire entre 5 et 11, donc c = 9 et b = 945.

## Exercice 3-8

Résolvez dans ℕ$^2$ les systèmes :
a) ${\begin{cases}x+y=72\\\operatorname {pgcd} (x,y)=8\end{cases}}$
b) ${\begin{cases}x+y=420\\\operatorname {pgcd} (x,y)=35\end{cases}}$
c) ${\begin{cases}x+y=5664\\\operatorname {pgcd} (x,y)=354\end{cases}}$
a) x = 8a et y = 8b, avec a, b premiers entre eux et a + b = 72/8, c'est-à-dire b = 9 – a et a non multiple de 3. Les solutions sont donc (x, y) = (8a, 72 – 8a) pour a = 1, 2, 4, 5, 7, 8.
b) x = 35a et y = 35b, avec a, b premiers entre eux et a + b = 420/35, c'est-à-dire b = 12 – a et a non multiple de 2 ni 3. Les solutions sont donc (x, y) = (35a, 420 – 35a) pour a = 1, 5, 7, 11.
c) x = 354a et y = 354b, avec a, b premiers entre eux et a + b = 5664/354, c'est-à-dire b = 16 – a et a impair. Les solutions sont donc (x, y) = (354a, 5664 – 354a) pour a = 1, 3, 5, 7, 9, 11, 13, 15.

## Exercice 3-9

Trouver les entiers naturels $x>y$ vérifiant :
    ${\begin{cases}x^{2}-y^{2}=2916\\\operatorname {pgcd} (x,y)=18\end{cases}}$
x = 18a et y = 18b avec a, b premiers entre eux et (a + b)(a – b) = 2916/18$^2$, c'est-à-dire a – b = 1 et a + b = 9, soit a = 5 et b = 4, donc x = 90 et y = 72.

## Exercice 3-10

Dans un repère $(O;{\vec {i}},{\vec {j}})$, le point M a pour coordonnées deux entiers $a$ et $b$ premiers entre eux. Démontrer que sur le segment [OM], les seuls points à coordonnées entières sont les extrémités.
Soient $t\in \left[0,1\right]$, $x=ta$ et $y=tb$. Alors, $ya=tab=xb$ donc si $x$ et $y$ sont entiers, d'après le théorème de Gauss, $a$ divise $x$ et $b$ divise $y$, c'est-à-dire (puisque $(a,b)\neq (0,0)$) $t\in \mathbb {Z}$. Donc $t=0$ ou $1$.

## Exercice 3-11

a et b sont deux entiers non nuls et g est leur PGCD ; p, q, r, s sont des entiers tels que ps – qr = 1. On pose A = pa + qb et B = ra + sb. Quel est le PGCD g' de A et B ?
g divise A et B donc il divise g'. Réciproquement, g' divise sA – qB = a et pB – rA = b donc il divise g. Donc g' = g.

## Exercice 3-12

a et b sont deux entiers. A = 11a + 2b et B = 18a + 5b. Démontrer que :
1° si l'un des deux nombres A ou B est divisible par 19, il en est de même pour l'autre ;
2° si a et b sont premiers entre eux, A et B ne peuvent avoir d'autres diviseurs communs que 1 et 19.
1° 5A – 2B = 19a.
2° Si n divise A et B alors il divise sA – qB = 19a et pB – rA = 19b donc il divise pgcd(19a, 19b) = 19pgcd(a, b) = 19.

## Exercice 3-13

a est un entier. On pose m = 20a + 357 et n = 15a + 187, et l'on note g le PGCD de m et n. Démontrer que :
1° g divise 323 ;
2° « g est un multiple de 17 » est équivalent à « a est un multiple de 17 » ;
3° « g est un multiple de 19 » est équivalent à « il existe un entier k, tel que a = 19k + 4 » ;
4° 289 est le plus petit entier positif a tel que g = 323.
1° g divise 3m – 4n.
2° $357=21\times 17$ et $187=11\times 17$ donc si 17 divise a alors il divise m et n, c'est-à-dire g. Réciproquement, s'il divise g, alors il divise $21n-11m=95a=(17\times 6a)-7a$ donc aussi 7a, si bien que (d'après le théorème de Gauss) il divise a.
3° Modulo 19, $m=a+19a+(19+2)\times (19-2)\equiv a-4$ et $n=-4a+19a+(19-8)\times (19-2)\equiv -4m$.
4° $323=17\times 19$ donc d'après les trois questions précédentes, g = 323 si et seulement si $a$ est à la fois de la forme $17j$ et de la forme $19k+4$. Or 17j – 19k = 4 équivaut à 17(j – 36) = 19(k – 32). Donc g = 323 si et seulement si a est de la forme 17(36 + 19i) = 612 + 323i. Le plus petit entier positif de cette forme est bien 612 – 323 = 289.

## Exercice 3-14

Soit g le PGCD de deux entiers a et b.
* Si c est un entier premier avec b, démontrer que pgcd(ac, b) = g.
* Si g = 1, démontrer par récurrence que pour tout entier naturel m, a$^m$ et b sont premiers entre eux, puis en déduire que pour tous entiers naturels m et n, a$^m$ et b$^n$ sont premiers entre eux.
* Quel est le PGCD de a$^m$ et b$^m$, pour m entier naturel ?
* Déduire du 3° que si a$^m$ divise b$^m$, alors a divise b.
* g divise a et b donc ac et b donc g divise pgcd(ac, b). Réciproquement, si b est premier avec c alors pgcd(ac, b) l'est aussi (car c'est un diviseur de b), donc d'après le théorème de Gauss, puisqu'il divise ac, il divise a. Il divise ainsi a et b, donc g.
* Récurrence : l'initialisation est immédiate (a$^0$ = 1 est premier avec n'importe qui) et l'hérédité se déduit de la question 1, appliquée à c = a$^m$. Conséquence : en remplaçant dans cette implication (a, b) par (b, a$^m$) (qui, d'après l'implication elle-même, est encore un couple d'entiers premiers entre eux), on en déduit que toute puissance de b est première avec a$^m$.
* D'après 2° pour n = m, appliqué aux entiers a/g et b/g (premiers entre eux), pgcd(a$^m$, b$^m$) = g$^m$×pgcd(a$^m$/g$^m$, b$^m$/g$^m$) = g$^m$×1 = g$^m$.
* Si a$^m$ divise b$^m$ alors a$^m$ = pgcd(a$^m$, b$^m$) = g$^m$ donc a est égal à g, qui divise b.

## Exercice 3-15

Soient a et b premiers entre eux.
* Démontrer que a + b et ab sont premiers entre eux.
* En est-il de même pour a + b et a$^2$ + b$^2$ ?
* Voir Arithmétique/Exercices/Fractions, 1°. Ou alors : si p premier divise a + b et ab alors il divise a + b et a ou b donc il divise a et b.
* Non. Exemple : a = b = 1.
| Multiples et diviseurs | PPCM et PGCD |