Divisibilité, division euclidienne et PGCD

B. 0 divise tout entier relatif — 0 ne divise que 0 : a = k × 0 impose a = 0. En revanche tout entier b divise 0, car 0 = 0 × b, et b divise −b = (−1) × b.

A. quotient 27 et reste 1 — 37 × 27 = 999 et 1 000 − 999 = 1, avec 0 ≤ 1 < 37. Un reste de 38 est impossible : il doit être strictement inférieur à 37.

C. 2 — 9 × 28 = 252 et 254 − 252 = 2, donc 254 = 9 × 28 + 2 avec 0 ≤ 2 < 9.

D. 17 — 51 = 1 × 34 + 17 puis 34 = 2 × 17 + 0 : le dernier reste non nul est 17. Contrôle : 51 = 17 × 3 et 34 = 17 × 2.

A. 0, 1, 2, 3, 4, 5 — Le reste r vérifie 0 ≤ r < 6 : il peut valoir 0 (division exacte), mais jamais 6.

C. 6 — Les diviseurs positifs de 63 sont 1, 3, 7, 9, 21 et 63 : il y en a six. Dans ℤ, il y en a douze avec leurs opposés.

B. leur PGCD est égal à 1 — C’est la définition : pgcd(a ; b) = 1. Par exemple 14 et 15 sont premiers entre eux alors qu’aucun des deux n’est premier, et 3 et 9 sont impairs sans être premiers entre eux.

D. n — Tout entier divise 0, donc les diviseurs communs de n et 0 sont exactement les diviseurs de n : le plus grand est n.

B. impair — C’est la forme d’un entier impair : le double d’un entier, augmenté de 1. Pour k = 4, 2k + 1 = 9 n’est pas premier.

D. 5 391 — 5 + 3 + 9 + 1 = 18 est un multiple de 9 : 5 391 = 9 × 599. Les sommes des chiffres des trois autres nombres valent 19, 17 et 22.

A. 5a − 3b — d divise toute combinaison linéaire de a et b à coefficients entiers, ici 5a + (−3)b. Avec d = 2, a = 4, b = 6 : 2 ne divise ni 11, ni 17, ni 3.

B. 59 = 8 × 7 + 3 — Le reste doit vérifier 0 ≤ r < 8 : seul 3 convient. Les autres égalités sont justes, mais 11 et 19 dépassent 8 et −5 est négatif.

C. 123 — 1 353 = 1 × 861 + 492 ; 861 = 1 × 492 + 369 ; 492 = 1 × 369 + 123 ; 369 = 3 × 123 + 0. Contrôle : 861 = 123 × 7 et 1 353 = 123 × 11.

B. 9 — 252 = 1 × 180 + 72, 180 = 2 × 72 + 36, 72 = 2 × 36 + 0 : le PGCD vaut 36. Les diviseurs communs sont ceux de 36 : 1, 2, 3, 4, 6, 9, 12, 18 et 36.

B. 17/23 — pgcd(1 071 ; 1 449) = 63, avec 1 071 = 63 × 17 et 1 449 = 63 × 23. 51/69 et 153/207 sont égales à 17/23 mais restent simplifiables ; 7/9 n’est pas égale à la fraction, car 7 × 1 449 ≠ 9 × 1 071.

D. quotient −17 et reste 8 — 15 × (−17) = −255 et −255 + 8 = −247, avec 0 ≤ 8 < 15. Un reste négatif n’est jamais acceptable, et 15 × (−16) + 7 = −233.

A. 76 — Ce sont les 13k avec 1 ≤ 13k ≤ 1 000. Comme 13 × 76 = 988 et 13 × 77 = 1 001 > 1 000, il y en a 76.

A. 2 — a = 12a′, b = 12b′ avec a′ + b′ = 5, a′ < b′ et a′, b′ premiers entre eux : (1 ; 4) et (2 ; 3), d’où (12 ; 48) et (24 ; 36).

A. 1 — Tout diviseur commun divise (n + 1) − n = 1 : deux entiers consécutifs sont toujours premiers entre eux.

B. 1 — 2n = 10k + 6 = 5(2k + 1) + 1 avec 0 ≤ 1 < 5 : le reste vaut 1. Le nombre 6 n’est pas un reste possible dans une division par 5.

A. 5 — Les diviseurs communs de a et b sont exactement les diviseurs de leur PGCD 15 : 1, 3, 5 et 15. Ni 30, ni 10, ni 2 ne divise 15.

C. 8 — n + 3 doit être un diviseur de 10 dans ℤ : ±1, ±2, ±5, ±10, soit 8 valeurs, donc 8 entiers n (de −13 à 7). Le nombre 4 ne compte que les diviseurs positifs.

D. 3 — N = 24q + 9 = 6(4q + 1) + 3 avec 0 ≤ 3 < 6 : comme 6 divise 24, le reste par 6 est celui de 9, soit 3.

C. (b ; 5) — Comme 0 ≤ 5 < b, 5 est le reste de la division de a par b : on divise ensuite b par 5, et pgcd(a ; b) = pgcd(b ; 5).

D. si d divise ab, alors d divise a ou b — Contre-exemple : 6 divise 4 × 15 = 60, mais 6 ne divise ni 4 ni 15. Les trois autres sont des propriétés du cours (combinaison linéaire, transitivité).

A. pgcd(a ; b) = pgcd(a − b ; b) — Les couples (a ; b) et (a − b ; b) ont les mêmes diviseurs communs. Contre-exemples : a = 3, b = 1 donne pgcd(2 ; 4) = 2 ; a = 6, b = 3 donne pgcd(9 ; 18) = 9 ; a = 4, b = 2 donne pgcd(4 ; 3) = 1.

C. {1 ; 2 ; 4 ; 8} — Tout diviseur commun divise (n + 8) − n = 8. Les quatre diviseurs de 8 sont atteints : n = 1 donne 1, n = 2 donne 2, n = 4 donne 4 et n = 8 donne 8. La valeur 6 ne divise pas 8.

B. si a divise b + c et a divise b, alors a divise c — c = (b + c) − b est une combinaison de deux multiples de a. Contre-exemples : 2 divise 1 + 1 sans diviser 1 ; 2 et 4 divisent 4, mais 2 × 4 = 8 ne divise pas 4 ; pgcd(8 ; 9) = 1 alors que ni 8 ni 9 n’est premier.

A. 5 — −1 = 6 × (−1) + 5 avec 0 ≤ 5 < 6 : le quotient vaut −1 et le reste 5. Un reste est toujours positif ou nul.

B. n + 2 — 2n + 4 = 2(n + 2) et 3n + 6 = 3(n + 2). Avec le facteur commun n + 2 ≥ 1 : pgcd = (n + 2) × pgcd(2 ; 3) = n + 2.

D. 4 — n + 9 = (n + 1) + 8, donc n + 1 divise n + 9 si et seulement s’il divise 8 : n + 1 ∈ {1 ; 2 ; 4 ; 8} et n ∈ {0 ; 1 ; 3 ; 7}. Le nombre 8 compterait aussi les diviseurs négatifs, impossibles car n + 1 ≥ 1.

C. (2n + 3)/(4n + 5) — Tout diviseur commun de 2n + 3 et 4n + 5 divise 2(2n + 3) − (4n + 5) = 1. Ailleurs : 3n + 6 = 3(n + 2) ; les deux termes de 2n/(4n + 2) sont pairs ; pour n = 1, la dernière vaut 2/6.

A. pgcd(b ; 4) — Comme 0 ≤ 4 < b, 4 est le reste de la division de a par b, d’où pgcd(a ; b) = pgcd(b ; 4). Pour b = 6 : a = 46 et pgcd(46 ; 6) = 2, alors que pgcd(7 ; 4) = 1 et pgcd(46 ; 7) = 1.

D. 5 — 3(4n + 1) − 4(3n + 2) = 12n + 3 − 12n − 8 = −5 : tout diviseur commun divise 5. Pour n = 1, les deux nombres valent 5 : le PGCD peut valoir 5, il n’est pas toujours 1.

C. 4 — N² = 25q² + 30q + 9 = 5(5q² + 6q + 1) + 4 avec 0 ≤ 4 < 5. Le nombre 9 n’est pas un reste possible dans une division par 5.

B. a′ et b′ sont premiers entre eux — C’est l’écriture de référence : pgcd(a ; b) = d × pgcd(a′ ; b′), donc pgcd(a′ ; b′) = 1. Pour a = 20 et b = 36 : d = 4, a′ = 5, b′ = 9, ni premiers tous les deux, ni multiples l’un de l’autre.