Arithmétique/Exercices/Diviseurs communs
Exercice 3-1
[modifier | modifier le wikicode]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 = 24×3 donc D(a) = {2p×3q | 0 ≤ p ≤ 4 et 0 ≤ q ≤ 1}.
- b = 25 donc D(b) = {2p | 0 ≤ p ≤ 5}.
- D(a)∩D(b) = {2p | 0 ≤ p ≤ 4} donc pgcd(a,b) = 24 = 16.
2° a = 23×3×5 donc D(a) = {2p×3q×5r | 0 ≤ p ≤ 3, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
- b = 23×3×7 donc D(b) = {2p×3q×7r | 0 ≤ p ≤ 3, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
- D(a)∩D(b) = {2p×3q | 0 ≤ p ≤ 3 et 0 ≤ q ≤ 1} donc pgcd(a,b) = 23×3 = 24.
3° a = 22×3×5 donc D(a) = {2p×3q×5r | 0 ≤ p ≤ 2, 0 ≤ q ≤ 1 et 0 ≤ r ≤ 1}.
- b = 25×3 donc D(b) = {2p×3q | 0 ≤ p ≤ 5 et 0 ≤ q ≤ 1}.
- D(a)∩D(b) = {2p×3q | 0 ≤ p ≤ 2 et 0 ≤ q ≤ 1} donc pgcd(a,b) = 22×3 = 12.
Exercice 3-2
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]Expliquer pourquoi, dans chacun des cas suivants, on peut donner très rapidement le PGCD de a et b.
1°
2°
3°
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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]Résolvez dans ℕ2 les systèmes :
a)
b)
c)
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
[modifier | modifier le wikicode]Trouver les entiers naturels vérifiant :
x = 18a et y = 18b avec a, b premiers entre eux et (a + b)(a – b) = 2916/182, 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
[modifier | modifier le wikicode]Dans un repère , le point M a pour coordonnées deux entiers et premiers entre eux. Démontrer que sur le segment [OM], les seuls points à coordonnées entières sont les extrémités.
Soient , et . Alors, donc si et sont entiers, d'après le théorème de Gauss, divise et divise , c'est-à-dire (puisque ) . Donc ou .
Exercice 3-11
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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
[modifier | modifier le wikicode]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° et donc si 17 divise a alors il divise m et n, c'est-à-dire g. Réciproquement, s'il divise g, alors il divise donc aussi 7a, si bien que (d'après le théorème de Gauss) il divise a.
3° Modulo 19, et .
4° donc d'après les trois questions précédentes, g = 323 si et seulement si est à la fois de la forme et de la forme . 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
[modifier | modifier le wikicode]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, am et b sont premiers entre eux, puis en déduire que pour tous entiers naturels m et n, am et bn sont premiers entre eux.
- Quel est le PGCD de am et bm, pour m entier naturel ?
- Déduire du 3° que si am divise bm, 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 (a0 = 1 est premier avec n'importe qui) et l'hérédité se déduit de la question 1, appliquée à c = am. Conséquence : en remplaçant dans cette implication (a, b) par (b, am) (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 am.
- D'après 2° pour n = m, appliqué aux entiers a/g et b/g (premiers entre eux), pgcd(am, bm) = gm×pgcd(am/gm, bm/gm) = gm×1 = gm.
- Si am divise bm alors am = pgcd(am, bm) = gm donc a est égal à g, qui divise b.
Exercice 3-15
[modifier | modifier le wikicode]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 a2 + b2 ?
- 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.
- Non. Exemple : a = b = 1.