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.

Solution

1° a = 2⁴×3 donc D(a) = {2^p×3^q | 0 ≤ p ≤ 4 et 0 ≤ q ≤ 1}.

b = 2⁵ donc D(b) = {2^p | 0 ≤ p ≤ 5}.

D(a)∩D(b) = {2^p | 0 ≤ p ≤ 4} donc pgcd(a,b) = 2⁴ = 16.

2° a = 2³×3×5 donc D(a) = {2^p×3^q×5^r | 0 ≤ p ≤ 3, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.

b = 2³×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 = 24.

3° a = 2²×3×5 donc D(a) = {2^p×3^q×5^r | 0 ≤ p ≤ 2, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.

b = 2⁵×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²×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.

Solution

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.

Solution

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$

Solution

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.

Solution

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.

Solution

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.

Solution

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 ℕ² 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}}$

Solution

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}}$

Solution

x = 18a et y = 18b avec a, b premiers entre eux et (a + b)(a – b) = 2916/18², 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.

Solution

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 ?

Solution

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.

Solution

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.

Solution

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.

1. Si c est un entier premier avec b, démontrer que pgcd(ac, b) = g.
2. 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ⁿ sont premiers entre eux.
3. Quel est le PGCD de a^m et b^m, pour m entier naturel ?
4. Déduire du 3° que si a^m divise b^m, alors a divise b.

Solution

1. 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.
2. Récurrence : l'initialisation est immédiate (a⁰ = 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.
3. 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.
4. 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.

1. Démontrer que a + b et ab sont premiers entre eux.
2. En est-il de même pour a + b et a² + b² ?

Solution

1. Voir Arithmétique/Exercices/Fractions#Exercice 7-4, 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.
2. Non. Exemple : a = b = 1.