FICHIER COMP 6198MTSSpe n 1 .pdf



Nom original: FICHIER_COMP_6198MTSSpe_n_1.pdf

Ce document au format PDF 1.6 a été généré par Adobe InDesign CS5 (7.0.4) / Adobe PDF Library 9.9, et a été envoyé sur fichier-pdf.fr le 25/11/2013 à 19:46, depuis l'adresse IP 82.229.x.x. La présente page de téléchargement du fichier a été vue 984 fois.
Taille du document: 3.1 Mo (17 pages).
Confidentialité: fichier public


Aperçu du document


Ouverture
Une première partie de ce chapitre reprend la
notion de PGCD de deux entiers naturels, que les
élèves de terminale connaissent depuis le collège,
pour les étendre aux entiers relatifs. Une méthode
efficace de calcul du PGCD est l’algorithme
d’Euclide. Historiquement il n’est pas présent
en tant que tel dans les Éléments d’Euclide, mais
il se rapproche de l’algorithme des différences
si l’on remplace les différences successives par
des divisions. Beaucoup de propriétés sont des
conséquences de l’algorithme d’Euclide, en particulier celle selon laquelle les diviseurs communs à
deux entiers sont les diviseurs de leur PGCD.
Une seconde partie est consacrée au théorème
de Bézout. Selon ce théorème, « 
l’équation
ax + by = 1 admet des solutions entières si et
seulement si a et b sont premiers entre eux ».
On le doit à Gaspard Bachet de Méziriac (Problèmes plaisants et délectables qui se font par
les nombres, 1624) ; Étienne Bézout (17301783) étendit ce résultat aux polynômes. Il serait
donc plus logique de l’intituler théorème de
Bachet-Bézout, comme c’est le cas dans certains
ouvrages.
Ce théorème peut être démontré en utilisant
l’algorithme d’Euclide ou en étudiant les combinaisons linéaires à coefficients entiers de a et de
b. On en déduit une propriété remarquable du
PGCD : les multiples du PGCD sont les combinaisons linéaires de a et b.
Une troisième partie est consacrée au théorème de
Gauss, qui affirme que si un entier a divise le produit bc et s’il est premier avec b, alors il divise c. Ce
théorème a été énoncé sous cette forme par Gauss
dans Disquisitiones Arithmeticae, en 1801, et se
démontre facilement avec le théorème de Bézout.
Applications
De nombreuses applications se déduisent de ces
théorèmes. On abordera par exemple :
–– La résolution des équations diophantiennes
de la forme ax + by = c : le théorème de Bézout
permet de dire à quelle condition une telle
équation a des solutions. L’algorithme d’Euclide
et le théorème de Gauss permettent de trouver
une solution particulière, puis toutes les solutions.

–– La résolution de problèmes de calendriers, de
conjonctions, planétaires etc.
–– Le théorème des restes chinois : pendant le premier siècle de notre ère, le mathématicien chinois
Sun Zi a traité, dans un livre d’arithmétique, le
problème qui consiste à trouver un nombre dont
on donne les restes respectifs (2, 3, 2) dans les
divisions par 3, 5 et 7. Le problème est réapparu
au xiiie siècle, à nouveau en Chine, d’où son nom.
Il a été ensuite été étudié en Occident à plusieurs
reprises à partir de la Renaissance. Le problème
de conjonctions des planètes peut se ramener à
ce problème.
–– L’application à la cryptographie avec le chiffrement affine et le chiffrement de Hill.
Réponse à la question
On note T le temps en heures écoulé entre la
première observation de l’astronome et une
apparition simultanée de Ganymède et Callisto.
On note x le nombre de révolutions nécessaires
pour Ganymède et y le nombre de révolutions
nécessaires pour Callisto.
On cherche donc des entiers naturels x et y tels
T 172x
que Ì
, ce qui revient à trouver deux
ÓÔT 8 400y
entiers naturels x et y tels que 172x = 8 + 400y,
soit 43x – 100y = 2 (E). On sait que, 100 et 43
étant premiers entre eux, l’équation (E) a des
solutions entières.
Recherche d’une solution particulière :
7 × 43 – 3 × 100 = 1, d’où 14 × 43 – 6 × 100 = 2.
Une solution particulière de (E) est donc le couple
(x0 ; y0) = (14 ; 6).
Recherche de toutes les solutions entières de
(E) ⇔ 43(x – x0) = 100(y – y0).
Soit (x ; y) un couple d’entiers solution. 100
divise alors 43(x – x0) et est premier avec 43,
donc divise x – x0 ; il existe donc un entier relatif k tel que x – x0 = 100k. En reportant dans (E)
on obtient ainsi 100(y – y0) = 43 × 100k, soit
y – y0 = 43k.
Réciproquement, s’il existe un entier relatif k tel
Ôx - x0 100k
que Ì
, alors l’équation
ÓÔy - y0 43k

100(y – y0) = 43(x – x0) est vérifiée.
Les solutions au problème de synchronisation des
lunes de Jupiter sont donc les solutions entières

26 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

2

PGCD, théorème
de Gauss
e
m

o
é
th

e

u
o
z
é
 B
e
d

positives de (E), soit les couples (x ; y) tels qu’il existe
x 14 100k
un entier naturel k tel que Ì
, ce qui
ÔÓy 6 43k
correspond à T = 172(14 + 100k), soit
T = 2 408 + 17 200k.
Ainsi, l’astronome verra Callisto et Ganymède
ensemble pour la première fois dans 2  408  heures,
soit 100 jours et 8 heures, et le phénomène se
reproduira toutes les 17 200 heures, soit tous les
716 jours et 16 heures.

Vérifier ses acquis
1 1. a. Vrai : 6 divise 144 et 36.
b. Vrai : N = (144 – 36)(144 + 36) = 180k.
c. Vrai : 144 et 36 sont multiples de 9.
d. Vrai : 60 est un diviseur de 180.
2. a. Faux, d’après le critère de divisibilité.
b. Vrai, d’après le critère de divisibilité.
c. Vrai : 9 999 = 33 × 303.
d. Faux.
3. a. Vrai.   b. Vrai.   c. Vrai.
d. Faux : 12 est multiple de 6 et 3 mais non de 18.

7 1. a. (x, y) ∈ {(1, 72), (2, 36), (3, 24), (4, 18),
(6, 12), (8, 9)}.
b. (x + 2, y – 3) ∈ {(1, 63), (3, 21), (7, 9), (9, 7),
(21, 3), (63, 1)}, (x, y) ∈ {(1, 24), (5, 12), (7, 10),
(19, 6), (61, 4)}.
c. (x, y) = (6, 5).
d. Pas de solution entière.
e. (x, y) = (9, 5).
2. a. Pas de solution. b. 5 × 1 – 3 × 1 = 2.
c. 5 × 2 + 3 × (–3) = 1.
d. 55 × 2 + 33 × (–3) = 11.
3. a. 5 ≡ 0 [5] donc, par somme, –3y ≡ 2 [5].
b. Congruences modulo 5
y

0

1

2

3

4

–3y

0

2

4

1

3

c. –3y ≡ 2 [5] ⇔ y = 1 + 5k, k Œ ¢.
d. 5x = 2 + 3y = 2 + 3(1 + 5k)  = 5(1 + 3k),
donc x = 1 + 3k. Si (x, y) est solution, alors
(x, y) = (1 + 3k, 1 + 5k). Réciproquement, ces
couples conviennent.

b. Oui.
d. Oui.

3 1. a. D(140) = {1, 2, 4, 5, 7, 10, 14, 20, 28,
35, 70, 140}.
b. D(105) = {1, 3, 5, 7, 15, 21, 35, 105}.
c. PGCD (140, 105) = 35.
d. Par l’algorithme d’Euclide.
2. a. b. 2 011 = 2 000 + 11 ; 2 000 = 11 × 181 + 9 ;
11 = 9 + 2 ; 9 = 2 × 4 + 1, donc
PGCD(2 011 ; 2 000) = 1.
c. PGCD(3 795, 6 555) = 345.
4 1. a. Tout diviseur commun de 2 011 et 2 012
divise 2 012 – 2 011 = 1.
b. 2 011 et 2 012 sont premiers entre eux.
2. 77 × 345 – 58 × 458 = 1.
Tout diviseur commun à 345 et 458 divise 1, donc
345 et 458 sont premiers entre eux.

5 Dans cet exercice, à la question b. on cherche
la fraction égale à g dont le numérateur est égal
à 9 348.
5
779
a. PGCD(190, 114) = 38, donc f et g
.
3
899
779 ¥ 12
9 348
b. g

.
899 ¥ 12 10 788

Activités d’introduction
Activité 1

1 a. Les diviseurs positifs de 180 sont :
1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45,
60, 90, 180.
b. Les diviseurs positifs de 140 sont :
1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140.
c. Les diviseurs communs de 180 et 140 sont :
1, 2, 4, 5, 10, 20. Le plus grand diviseur commun
de 140 et 180 est 20.
La longueur c est égale à 20.

2 a.
L

180

140

100

60

40

20

l

140

40

40

40

20

20

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  27

© éditions Belin, 2012.

2 1. a. et b. 12 452 = 139 × 89 + 81
et 0 ≤ 81 < 89.
2. a. Non, 35 > 11.
c. Non, –2 < 0.

6 1. a. 3a = 1 + 5k, k Œ ¢.
b. Si 6 divise ab, alors 6 divise a ou 6 divise b.
Proposition fausse si par exemple a = 2 et b = 3.
2. b ; c ; d.
3. b ; c ; d.

A

F

C

G

H

I

J

K N

L

E

M

B

b. Soit L et l deux entiers naturels tels que L ≥ l :
si d divise L et l, alors d divise l et L – l et réciproquement, si d divise l et L – l, alors d divise l et
L – l + l = L. Donc d divise L et l si et seulement si
d divise l et L – l.
Ainsi c est un diviseur commun de L et l si et seulement si c est un diviseur commun de L et L – l.
On continue ces équivalences en remplaçant L et
l par (L – l et l) ou (l et L – l). En supposant que c
existe, on arrive à c = L – l = l. Dans ce cas, c est
bien un diviseur de l et L = 2l et par équivalence,
on peut conclure que c est à chaque étape un
diviseur de L et l (sous couvert qu’il existe).
c. i. À l’étape i, si Li = li, la suite s’arrête, sinon,
on a 0 < li < Li. Par suite Li+1 ∈ {Li – li ; l}, d’où
Li+1 < Li.
ii. D’après le principe de la descente infinie, cette
suite est finie et en un nombre fini d’étapes on
arrivera au cas L = l, ce qui donne l’existence de c.
iii. La suite (Li) est une suite d’entiers, strictement
décroissante, ayant pour plus petite valeur c > 0.
En supposant initialement 0 < l < L, elle a donc
au maximum L – 1 termes. Ce nombre est atteint
lorsque l = 1.
d. c est solution du problème si et seulement si,
à chaque étape, c est un diviseur commun des
dimensions du rectangle intermédiaire, donc en
particulier du dernier qui est un carré. Par conséquent c est le plus grand diviseur commun de L et l.

Activité 2

1 PGCD(a ; a) = a.
2 On remarque une symétrie par rapport à la
première diagonale qui traduit la commutativité
du PGCD.
3 PGCD(a ; 2) ∈ {1 ; 2}. On peut conjecturer
que les nombres 2, 3 et 5 sont premiers.
4 PGCD(a ; 4} ∈ {1 ; 2 ; 4}.
PGCD(a ; 6) ∈ {1 ; 2 ; 3 ; 6}.

5 a. On a PGCD(a ; 4) = 4 lorsque a est un multiple de 4. Idem pour 6.
b. Soit b non nul.
PGCD(a ; b) = b ⇔ a est un multiple de b.
c. Soit b non nul.
⇒ : On sait que PGCD(a ; b), soit b, divise a, donc
a est un multiple de b.
⇐ : a est un multiple de b donc b (b ≠ 0) divise
a et comme b est le plus grand diviseur de b,
PGCD(a ; b) = b.
6 a. La périodicité semble être égale au
nombre b.
c. On montre que PGCD(a ; b) divise
PGCD(a – b ; b) et inversement.
7 PGCD(180 ; 140) = PGCD(40 ; 140) = …
= PGCD(20 ; 40) = 20.
Activité 3

1 a. (x0 ; y0) (1 ; - 1) est une solution de
6x + 5y = 1.
b. (x1 ; y1) (4x0 ; 4y0) (4 ; - 4) est une solution
de 6x + 5y = 4.
c. 12x 30y 42 € 2x 5y 7, donc une
solution est (1 ; 1).
d. On remarque que s’il existait une solution
entière (x ; y), 6 diviserait 12x + 30y, donc devrait
diviser 40, ce qui est faux. Donc l’équation
12x + 30y = 40 n’a pas de solution dans Z.
Conjecture : le PGCD de a et b doit diviser le
second membre.
2 b. Les entiers positifs de la forme 12x + 30y
avec – 4 ≤ x ≤ 4 et – 4 ≤ y ≤ 4 sont :
0, 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78,
84, 90, 96, 102, 108, 114, 120, 126, 132, 138,
144, 156, 168 ; ce sont des multiples positifs de
6, qui est le PGCD de 12 et 30.
c. Il semble que l’on obtient presque tous les
entiers naturels de 0 à 44 (on ne les obtient
pas tous du fait des contraintes – 4 ≤ x ≤ 4
et – 4 ≤ y ≤ 4).
d. On conjecture que les entiers de la forme
ax + by sont les multiples du PGCD de a et b.
3 a. E′ contient a et b, donc E′ est bien une
partie non vide de N. Elle admet un plus petit
élément d qui s’écrit d = au + bv.
b. Tout multiple de d s’écrit kd = a(ku) + b(kv)
(k entier relatif), donc est un élément de E.
c. Soit e = am + bn un élément de E. On a
e = qd + r avec 0 ≤ r < d. On en déduit que :

28 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

D

4 a. et b. PGCD(6 ; 5) = 1, il est donc normal
que ces deux équations aient des solutions dans Z.
c. PGCD(12 ; 30) = 6 et 42 est un multiple de 6, il est
donc normal que cette équation ait des solutions.
d. PGCD(12 ; 30) = 6 et 6 ne divise pas 40, le
résultat trouvé est donc conforme.
5 a. Il est clair que tout diviseur du PGCD de a
et b est un diviseur commun de a et b.
On remarque qu’une conséquence de l’étude
précédente est que PGCD(a ; b) s’écrit
PGCD(a ; b) = au + bv. On en déduit que tout diviseur commun de a et b divise au + bv = PGCD(a ; b).
b. S’il existe des entiers relatifs x et y tels que
ax + by = 1, on en déduit que tout diviseur commun de a et b divise 1 et donc que PGCD(a ; b) = 1.
Réciproquement, il suffit d’utiliser la remarque précédente dans le cas particulier où PGCD(a ; b) = 1.
Activité 4

1 a. a = 6 et b = 5
lettre

F

E

R

M

A

T

N

= CODE(A3) – 65

5

4

17 12

0

19

N′

= MOD(6*A4 + 5 ; 26)

9

3

3

25

5

15

code

= CAR(A5 + 65)

J

D

D

Z

F

P

b. a = 3 et b = 5
lettre

F

E

R

M

A

T

N

5

4

17

12

0

19

N′

20

17

4

15

5

10

code

U

R

E

P

F

K

c. Dans le premier codage, on constate que deux
lettres distinctes sont codées par la même lettre.

2 a. i. PGCD(3 ; 26) = 1, d’après le théorème de
Bézout (voir activité 3), il existe deux entiers relatifs x et y tels que 3x + 26y = 1, donc (u ; v) = (x ;
–y) est une solution de 3x – 26y = 1.
Une solution évidente est (u ; v) = (9 ; 1).
ii. Ainsi 3 × 9 = 1 + 26, d’où 3 × 9 1[26].
iii. c(x) c(x¢) [26] € 3x 5 3x¢ 5 [26]
fi 3x 3x¢ [26] fi 9(3x) 9(3x¢) [26]
fi x x¢ [26].
b. i. au 1[26] si et seulement s’il existe un
entier relatif v tel que au + 26v = 1. Cette
condition est réalisée si et seulement si a et 26
sont premiers entre eux.
ii. En raisonnant comme en a., on montre que
si a et 26 sont premiers entre eux alors
c(x) c(x¢) [26] fi ax ax¢ [26]
fi u(ax) u(ax¢) [26] fi x x¢ [26].
Ainsi deux lettres distinctes sont codées par deux
lettres distinctes.
Réciproquement, si a et 26 ne sont pas premiers
entre eux, alors PGCD(a ; 26) = d et on a 26 = kd.
Si on considère la lettre de code k on lui attribue
le code c(k) ak b [26]. Or ak = a′dk = 26a′,
d’où ak 0 [26] et c(k) b [26], d’où c(k) c(0) [26]
ce qui signifie que deux lettres distinctes (A et la
lettre de code k) ont le même codage.
Un codage affine est « bon » si et seulement si a
est premier avec 26.
iii. Il y a 12 entiers compris entre 0 et 25 premiers avec 26 ; il y a donc 12 possibilités pour a
et 26 pour b, c’est-à-dire 12 × 26 = 312 « bons »
codages affines. Mais le codage a = 1, b = 0, qui
est l’identité, ne présente pas d’intérêt. Il y a
donc 311 bons codages.
3 a. i. y 3x 5 [26] fi 3x y - 5 [26]
fi x 9y 7 [26].
ii. Réciproquement,
x 9y 7 [26] fi 9y x - 7[26]
fi 3(9y) 3(x - 7) [26] fi y 3x 5 [26].

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  29

© éditions Belin, 2012.

r = (am + bn) – q(au + bv) = a(m – qu) + b(n – qv),
donc r est un élément de E positif et strictement
inférieur à d. La seule solution est r = 0 (d étant le
plus petit élément strictement positif de E). Puisque
r = 0, d divise e, autrement dit e est un multiple de d.
d. D’après b. et c., E est l’ensemble des multiples
de d.
e. i. De manière évidente, a et b sont des éléments de E. D’après d., on en déduit que d est
un diviseur commun de a et b et donc est nécessairement inférieur au plus grand des diviseurs
communs D. Ainsi d ≤ D.
ii. D divise a et b, donc divise au + bv = d et d ≠ 0.
Par conséquent D ≤ d.
iii. De i. et ii., on déduit D = d.
f. On vient de montrer que l’ensemble des
entiers de la forme ax + by (avec x et y entiers
relatifs) sont les multiples du PGCD de a et b.
On en déduit que l’équation ax + by = c admet
des solutions dans Z si et seulement si c est un
multiple de PGCD(a ; b).
g. C’est une conséquence de f. Si PGCD(a ; b) = 1,
tout entier c étant multiple de 1, alors toute équation de la forme ax + by = c admet des solutions
dans Z.

iii. y 3x 5 [26] € x 9y 7 [26].
La fonction de décodage est x 9y 7 [26].
b. Si a est premier avec 26, alors il existe u tel que
au 1[26].
On montre comme dans l’exemple que :
y ax b [26] € u(ax) u(y - b) [26]
€ x u(y - b) [26].

4 a. i. a et 26 étant premiers entre eux, il existe

un entier u tel que au 1[26].
Donc ab 0 [26] fi u(ab) u(0) [26] fi b 0 [26].
ii. Donc si 26 divise le produit ab et est premier
avec a, alors il divise b.
b. On peut démontrer de manière identique que si
c divise ab en étant premier avec a, alors c divise b.

Saisir a, b
Tantque b ≠ 0 faire
r = MOD(a ; b)
a = b ; b = r
FinTantque
Afficher a

3 a.
= B1

= MOD(A1 ; B1)

b. On s’arrête dès que 0 apparaît en colonne B.
Le PGCD est sur la même ligne en colonne A.
d. On adapte les formules qui sont dans la bulle
et dans l’éditeur :
= SI(B1 = 0 ; ”” ; B1)

= SI(A2 = ”” ; ”” ; MOD(A1 ; B1))

2TP Algorithmique 2  Coefficients de Bézout

Travaux pratiques

1
51 = 35 × 1 + 16 16 = 51 – 35

1
a

b

r

513

350

163

350

163

24

163

24

19

24

19

5

19

5

4

5

4

1

4

1

0
PGCD = 1

2 a.
a

b

r

1 404

264

84

264

84

12

84

12

0

12

0

PGCD = 12

a

b

r

264

1 404

264

1 404

264

……..

Peu importe l’ordre des entiers a et b.

35 = 16 × 2 + 3

3 = 35 – 2 × 16 3 = b – 2(a – b)

16 = 3 × 5 + 1

1 = 16 – 5 × 3

3 = −2a + 3b

1 = (a – b) – 5(−2a + 3b) 1 = 11a – 16b

Ainsi 11 ¥ 51 - 16 ¥ 35 1.

2 a. r2 a - bq2 au2 bv2 ; u2 1 et v2 -q2.
r3 b - (a - bq2)q3 -aq3 b(1 q2q3),
d’où u3 -q3 et v3 1 q2q3.
b. Pour k 4, soit la proposition :
(1)
Ô 2 i k ; ui et vi existent
Ì
et
v
q
(2)
u

u
u
q
u

u
ÓÔ k
k -2
k -1 k
k
k -2
k -1 k
Pour k = 4, (1) est vrai (voir question précédente).
r4 = r2 – r3q4 = (au2 + bv2) – (au3 + bv3)q4, donc
r4 = a(u2 – u3q4) + b(v2 – v3q4), d’où
u4 = u2 – u3q4 et v4 = v2 – v3q4 ; par conséquent
(2) est vrai.
La propriété est donc vraie pour k = 4.
Montrons que si la propriété est vraie pour un
entier k ≥ 4, alors elle est vraie pour k + 1.
Supposons que, pour un entier k ≥ 4, la
proposition soit vraie. Alors (1) est vrai et
rk 1 rk -1 - rkqk 1 (auk -1 bvk -1) - (auk bvk)qk 1
= a(uk -1 - ukqk 1) b(vk -1 - vkqk 1). En identifiant,
on a uk 1 uk -1 - ukqk 1 et vk 1 vk -1 - vkqk 1 ;
donc (2) est vrai.
La proposition est vraie pour k + 1 donc elle est
héréditaire ; étant vraie au rang 4, elle est vraie
pour tout k = 4.
c. En posant u0 = 1 et u1 = 0, la relation
de récurrence donne u2 = 1 – 0q2 = 1 et
u3 = 0 – 1q3 = –q3, relations toutes les deux
vraies. On vérifie de même pour v2 et v3.

30 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

1TP Algorithmique 1  Algorithme d’Euclide

16 = a – b

n

2

3

4

qn

1

2

5

un

1

–2

11

vn

–1

3

–16

3 b.
= MOD(A2 ; A3)

= QUOTIENT(A2 ; A3)

= C2 – C3*B4 correspond à la définition par
récurrence de la suite (u).
Dans D4 : = D2 – D3*B4
c. On doit s’arrêter dès la parution de 0 en
colonne A.

4 a. Les restes sont stockés en B. Les variables
auxiliaires sont R pour les restes et T pour les
suites U et V.
b. T = V1 ; V1 = V0 – QV1 ; V0 = T.
3TP TICE 1  Quel est le nombre de billes?

1 a.
A

B

C

D

1

n

modulo 5

2

0

= MOD(A2 ; 5) = MOD(A2 ; 7) = SI(ET(B2 = 3 ;
C2 = 2) ; ”1” ; ””)

modulo 7

test

b. On repère comme cela les nombres :
23

58

93

128

163

198

233

268

303

338

373

408

443

478

513

548

583

618

653

688

723

758

793

828

863

898

933

968

soit les nombres 23 + 35k, 0 k 27.

2 a. n est solution du système (S) si et seulement si il existe deux entiers k et k′ tels que
n 5k 3
.
Ì
ÔÓn 7k¢ 2
i. Si n est solution alors les entiers k et k′
définis ci – dessus vérifient 5k + 3 = 7k′ + 2, soit
7k′ – 5k = 1 (E).
ii. Résolution de l’équation (E).
Une solution évidente est (u ; v) = (–2 ; –3).
On a donc :
7k′ – 5k = 1 € 7k¢ - 5k 7u - 5v
€ 7(k¢ - u) 5(k - v) (E′).
Si (k′ ; k) couple d’entiers relatifs est solution de
l’équation (E′), alors 5 divise 7(k′ – u). Comme il

est premier avec 7, d’après le théorème de Gauss,
on en déduit que 5 divise k′ – u, d’où k′ – u = 5p
(p entier relatif). En reportant dans l’équation on
trouve : k – v = 7p.
k¢ - u 5p
Réciproquement si Ì
ÔÓk - v 7p
alors 7(k′ – u) = 5(k – v).
Les solutions de l’équation (E) sont les couples
k¢ -2 5p
(x ; y) tels que Ì
, p Œ ¢.
ÓÔk -3 7p
iii. On en déduit que si n entier relatif est solution
du problème alors il existe un entier relatif p
k¢ -2 5p
, p Œ ¢, d’où en reportant dans
tel que Ì
ÔÓk -3 7p
l’une des deux formules n = 5k + 3 et n = 7k′ + 2, on
obtient n = 5(–3 + 7p) + 3, c’est-à-dire n = –12 + 35p.
Donc, si n entier relatif est solution du système
(S), alors il existe un entier relatif p tel que
n = –12 + 35p.
b. Réciproquement, tout entier relatif de la forme
n = –12 + 35p (p entier relatif) vérifie le système (S).

3 a. D’après l’étude précédente les solutions de (S) sont les entiers naturels de la
forme – 12 + 35p (p ∈ Z).
n Œ • € -12 35p 0 € p 0 .
Donc les solutions du problème sont les entiers
naturels de la forme n = –12 + 35p (p Œ• *), ce
sont aussi les entiers naturels de la forme
23 + 35q (q Œ•).
b. La conjecture est donc prouvée et les solutions
inférieures à 100 sont : 23, 58 et 93. Il y a donc
3 réponses.
4TP TICE 2  Codage et décodage

1 a. Message codé : 220 ; 167 ; 2 ; 37 ; 224 ;
244 ; 224 ; 167 ; 30 ; 223 ; 44 ; 216 ; 251 ; 95 ;
44 ; 223 ; 23 ; 51 ; 195 ; 224 ; 188 ; 195 ; 224 ;
244 ; 224 ; 167 ; 251 ; 9 ; 51 ; 30 ; 52 ; 224 ; 51 ;
2 ; 224 ; 16 ; 244 ; 51 ; 37 ; 224 ; 51 ; 2 ; 224 ;
95 ; 209 ; 167 ; 244 ; 195
b. l infini et deux moins un égale zéro
D
 = CODE(B1)
= MOD(7*B2 ; 256)
244
= MOD(183*B4 ; 256)
= CAR(B5)

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  31

© éditions Belin, 2012.

d.

fi 7(n - p) 0 [256].
ii. Donc 256 divise 7(n – p) et comme 256 est premier avec 7, d’après le théorème de Gauss, 256
divise n – p. Donc n - p 0 [256] fi n p [256], et
comme n et p sont compris entre 0 et 255, n = p. Le
codage code bien deux lettres distinctes par deux
lettres distinctes. C’est donc un « bon » codage.
b. i. On peut, à l’aide d’un tableur, dresser la
table de multiplication par 7 modulo 256 et on
trouve que 7 ¥ 183 1[256]. D’où u = 183.

ii. On a donc 7u 1[256], d’où u(7n) n [256].
iii. C(n) 7n [256] fi uC(n) u(7n) [256], soit
n uC(n) [256] fi n 183C(n)  [256].
Réciproquement
n 183C(n) [256] fi 7n 7(183C(n)) [256]
fi 7n C(n) [256].
Donc C(n) 7n [256] € n 183C(n) [256].
La fonction de décodage est donc la fonction
qui à tout C(n) compris entre 0 et 255 fait correspondre n compris entre 0 et 255, reste de la
division euclidienne de 183C(n) par 256.

Exercices
Maîtriser le cours
1 À la question b. on cherche bien sûr le PGCD
de 44 et 154 (et non pas 77).
a. D(44) = {1, 2, 4, 11, 22, 44} et
D(154) = {1, 2, 7, 11, 14, 22, 77, 154}.
b. D(44) ∩ D(154) = {1, 2, 11, 22}.
Donc PGCD(44 ; 154) = 22.
2 a. 117 × 8 – 85 × 11 = 936 – 935 = 1.
b. Si d divise 117 et 85, d divise 1, donc
PGCD(117 ; 85) = 1.
3 a. Si d divise a et b, il divise a – b. Si d divise
b et a – b, il divise a. Les diviseurs communs à a
et b sont ceux de a et a – b.
D’où PGCD(a ; b) = PGCD(a – b ; b).
b. PGCD(216 ; –168) = PGCD(168 ; 48) =
PGCD(120 ; 48) = PGCD(72 ; 48) =
PGCD(24 ; 48) = 24.
4 a. Si d divise a et b, il divise a – kb. Si d divise
b et a – kb, il divise kb + kb = a. Les diviseurs
communs à a et b sont ceux de a et a – kb.
D’où PGCD(a – kb ; b) = PGCD(a ; b).

b. PGCD(3n + 2 ; n – 3) = 
PGCD(3n + 2 – 3(n – 3) ; n – 3) = PGCD(11 ; n – 3).
Les valeurs possibles sont 1 et 11.

5 Faux : PGCD(6 ; 4) = 2, PGCD(5 ; 3) = 1.
6 a. (3n + 5) – 3(n + 2) = 3n + 5 – 3n – 6 = –1.
b. PGCD(3n + 5 ; n + 2) =
PGCD(3n + 5 – 3(n + 2) ; n + 2) = PGCD(–1 ; n + 2) = 1
7 a. Voir propriété 5 page 50.
b. 1 320 = 825 + 495 ;
825 = 495 + 330 ; 495 = 330 + 165 ;
330 = 165 × 2 donc PGCD(1 320 ; 825) = 165.
c. 1 849 = 1 517 + 332 ;
1 517 = 332 × 4 + 189 ; 332 = 189 + 143 ;
189 = 143 + 46 ; 143 = 46 × 3 + 5 ;
46 = 5 × 9 + 1, donc PGCD(1 849 ; 1 517) = 1.
8 Application directe avec la calculatrice.
9 a. n est un entier naturel qui divise 1 320 et
825, c’est donc un diviseur de leur PGCD 165 (voir
exercice 7). Donc n ∈ {1, 3, 5, 11, 15, 33, 55, 165}.
b. 1 320 = 165 × 8 et 825 = 165 × 5 donc 165 lots
de 8 + 5. On procède de même et on trouve :
55 lots de 24 + 15 ; 33 lots de 40 + 25 ; 15 lots de
88 + 55 ; 11 lots de 120 + 75 ; 5 lots de 264 + 165 ;
3 lots de 440 + 275.
10 a. PGCD(ac ; bc) = c PGCD(a ; b).
b. PGCD(2 012 × 11 ; 2 012 × 12) = 
2 012PGCD(11 ; 12) = 2 012 × 1 = 2 012.
c. PGCD(50 ; –120) = 10 × PGCD(5 ; –12) = 10.
11 a. Voir propriété 10 page 54.
b. (117, 85), (117, 11), (8, 85) et (8, 11) sont les
paires d’entiers naturels premiers entre eux.
12 a. a et b sont premiers entre eux, donc il existe
un couple d’entiers relatifs (u, v) tels que au + bv = 1.
b. De même, il existe (u′, v′) tels que au′ + cv′ = 1.
c. 1 = (au + bv)(au′ + cv′) = a(auu′ + ucv′ + u′bv) 
+ bc(vv′) = aU + bcV avec U = auu′ + ucv′ + u′bv
et V = vv′, entiers relatifs, donc a et bc sont premiers entre eux.
13 a. Voir propriété 11 page 54.
b. a = ub = vc, u et v entiers. b divise cv et il est
premier avec c, donc il divise v. Il existe donc
k ∈ Z tel que v = bk, d’où a = bck et a est donc
divisible par bc.
c. 2 352 est pair et divisible par 3, donc par 6.
14 a. 5x = 7y, donc 5 divise 7y or 5 est premier
avec 7, donc 5 divise y. Il existe k tel que y = 5k.
En remplaçant, x = 7k. Réciproquement, (7k, 5k)
est solution.

32 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

2 a. i. C(n) C(p) [256] fi 7n 7p [256]

15 D’après l’exercice 13.b., x – 3 est divisible par
5 et 7 premiers entre eux, donc par leur produit
35, d’où x – 3 = 35k et x = 3 + 35k, k ∈ Z.
16 a. Faux ;

b. Vrai ;

c. Vrai.

17 a. Faux : 5 et 3 sont premiers entre eux mais
2 et 8 ne sont pas premiers entre eux ;
b. Vrai ;
c. Vrai ;
d. Vrai.
e. Vrai ;
f. Vrai ;
g. Vrai.

Appliquer les capacités attendues
19 a. Si d divise 1 635 et 1633, d divise 2, donc
d = 1 ou d = 2 ou d = –1 ou d = –2.
b. 1 635 et 1633 étant impairs, d = 1 ou d = –1.
c. PGCD(1 635 ; 1 633) = 1.
20 a. n + 1 – n = 1, donc si d divise n et n + 1,
alors d = 1 ou d = –1.
b. PGCD(n, n + 1) = 1.
c. Deux entiers consécutifs sont premiers entre eux.
21 a. a – b = 2 donc les diviseurs communs de a
et b sont 1 ou 2 ou –1 ou –2.
b. 2n et 2n + 2 étant pairs, PGCD (a ; b) = 2.
c. Deux entiers pairs consécutifs ont pour PGCD 2.
22 a. Si un entier d divise a et b, alors d divise
3a – b = 5.
b. PGCD (a, b) ∈ {1, 5}.
24 225 = 75 × 3. a doit être un multiple de 75
inférieur à 225, donc a ∈ {75, 150}.
26
620 – 452 = 168 PGCD(620 ; 452) = PGCD(168 ; 452)
452 – 168 = 284 PGCD(168 ; 452) = PGCD(168 ; 284)
284 – 168 = 116 PGCD(168 ; 284) = PGCD(168 ; 116)
168 – 116 = 52

PGCD(168 ; 116) = PGCD(52 ; 116)

116 – 52 = 64

PGCD(52 ; 116) = PGCD(52 ; 64)

64 – 52 = 12

PGCD(52 ; 64) = PGCD(52 ; 12)

52 – 12 = 40

PGCD(52 ; 12) = PGCD(40 ; 12)

40 – 12 = 28

PGCD(40 ; 12) = PGCD(28 ; 12)

28 – 12 = 16

PGCD(28 ; 12) = PGCD(16 ; 12)

16 – 12 = 4

PGCD(16 ; 12) = PGCD(4 ; 12) = 4

PGCD(620 ; 452) = PGCD(4 ; 12) = 4.

27 a. PGCD(275 ; 134) = PGCD(275 – 134 ; 134)
= PGCD(141 ; 134) = PGCD(141 – 134 ; 134)
= PGCD(7 ; 134)
b. 134 = 7 × 19 + 1, donc 7 est premier et ne
divise pas 134 et PGCD(7 ; 134) = 1.
28 PGCD(275 ; 123) = PGCD(257 – 2 × 123 ; 123)
= PGCD(11 ; 123).
Or 11 est premier et ne divise pas 123 donc
PGCD(11 ; 123) = 1. Ainsi PGCD(257 ; 123) = 1.
29 Cet algorithme calcule le PGCD par la
méthode des différences. PGCD(432, 168) = 24.
31 PGCD(n ; 3n + 13) = PGCD(n ; 3n + 13 – 3n)
= PGCD (n, 13) donc si 13 divise n,
alors PGCD(n ; 3n + 13) = 13,
sinon PGCD(n ; 3n + 13) = 1.
32 a = 5n + 4 et b = 3n – 1.
a. PGCD(a ; b) = PGCD(a – 2b ; b) =
PGCD(–n + 6 ; 3n – 1).
b. PGCD(3n – 1 ; –n + 6) =
PGCD(3n – 1 + 3(–n + 6) ; –n + 6) =
PGCD(17 ; –n + 6).
c. Par transitivité de l’égalité, on a le résultat
PGCD(a ; b) = PGCD(17 ; –n + 6).
d. PGCD(a ; b) ∈ {1, 17}.
e. Si n = 6 + 17k, alors a = 85k + 34 = 17(5k + 2)
et b = 17(3k + 1) d’où PGCD(a ; b) = 17, sinon,
PGCD(a ; b) = 1.
33 a. PGCD(a ; b) = PGCD(a – 2b ; b) = 
PGCD(9 ; n + 3).
b. i. PGCD(a, b) = 9 ⇔ n + 3 = 9k ⇔ n ≡ 6 [9].
ii. PGCD(a ; b) = 3 ⇔ n + 3 = 3k et n + 3 ≠ 9k ⇔
n ≡ 0 [9]ou n ≡ 3 [9].
iii. Pour toutes les autres valeurs, PGCD(a ; b) = 1.
35 a. PGCD(A ; B) = PGCD(A – B ; B) =
PGCD(a + 2b ; 4a + 7b) = 
PGCD(a + 2b ; 4a + 7b – 4(a + 2b)) = 
PGCD(a + 2b ; −b) = PGCD(a + 2b – 2b ; −b) =
PGCD(a ; −b) = PGCD(a ; b).
b. Si d divise a et b, d divise toute combinaison
linéaire de a et b. Ainsi d divise 5a + 9b et 4a + 7b
donc d divise A et B. Si d divise A et B, d divise
4A – 5B = b et d divise 9B – 7A = a. L’ensemble
des diviseurs communs de A et B étant égal à
l’ensemble des diviseurs communs de a et b,
PGCD(A ; B) = PGCD(a ; b).
37 a. 455 = 312 + 143 ; 312 = 2 × 143 + 26 ;
143 = 5 × 26 + 13 ; 26 = 2 × 13,
d’où PGCD(455, 312) = 13.
b. PGCD(276 ; 978) = 6.
c. PGCD(1 938 ; 589) = 19.

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  33

© éditions Belin, 2012.

b. 18x = 27y équivaut à 2x = 3y. Les solutions
sont les couples de forme (3k, 2k), k ∈ Z.
c. (2 + 7k, –3 + 5k), k ∈ Z.
d. (–5 + 6k, 7k), k ∈ Z.

38 a. PGCD (2 011 ; 2 001) = 1.
b. PGCD (6 002 ; 2 006) = 2.
c. PGCD (1 515 ; 1 918) = 1.

e. PGCD(a, b) = PGCD(A, B) donc a et b sont premiers entre eux si et seulement si à A et B sont
premiers entre eux.

39 a. b. Propriétés des puissances.

51 a. a divise ac donc tout diviseur commun de
a et bc est un diviseur commun de ac et bc donc
de PGCD(ac ; bc).
b. Par homogénéité, PGCD(ac ; bc) = 
cPGCD(a ; b) = c. Ainsi tout diviseur commun de
a et bc est un diviseur de c.
c. PGCD (a, c) = 1. Donc a est premier avec bc.

212

– 1 ;
– 1) =
PGCD(221 – 1 – 29(212 – 1) ; 212 – 1) =
PGCD(29 – 1 ; 212 – 1).
d. 212 – 1 = (29 – 1)23 + 23 – 1 donc
PGCD(212 – 1 ; 29 – 1) = PGCD(29 – 1 ; 23 – 1).
Or 23 – 1 divise 29 – 1, donc PGCD (a ; b) = 23 – 1 = 7.

41 PGCD(a ; b) = 44, donc les diviseurs communs
positifs de a et b sont ceux de 44, à savoir 1, 2, 4,
11, 22, 44.
42 a. 2 790 = an + 7 et 2 657 = bn + 6, avec
0 ≤ 7 < n et 0 ≤ 6 < n, donc an = 2 783 et
bn = 2 651. Ainsi n est un diviseur commun à
2 783 et 2 651.
b. n divise PGCD(2 783, 2 651) = 11 et n ≥ 8
donc n = 11.
43 n divise PGCD(2 370, 2 205) = 15 et n ≥ 11,
donc n = 15.

44 PGCD(210, 360) = 30. La mesure d’un côté le
plus grand possible est 30 cm
46 a. PGCD(m ; 3m + 1) = 
PGCD(m ; 3m + 1 – 3m) = 1.
b. PGCD(nm ; n(3m + 1)) = 
nPGCD(m ; 3m + 1) = n × 1 = n.
47 a. a = n(n + 5) b = (n + 5)(n + 2).
b. n + 2 – n = 2 donc PGCD(n ; n + 2) divise 2. Si
n est pair, n + 2 aussi donc PGCD(n ; n + 2) = 2,
sinon PGCD(n ; n + 2) = 1.
c. PGCD(a ; b) = (n + 5)PGCD(n ; n + 2) = n + 5 si
n est impair et 2n + 10 si n est pair.

48 a = 5n2 + 4n = n(5n + 4),

b = 4n2 + 3n = n(4n + 3).
4(5n + 4) – 5(4n + 3) = 1 ; si d divise
5n + 4 et 4n + 3, d = 1 ou d = –1. Donc
PGCD(5n + 4 ; 4n + 3) = 1.
PGCD(5n2 + 4n ; 4n2 + 3n) = 
nPGCD(5n + 4, 4n + 3) = n.

50 a. Si d divise a et b, d divise toute combinaison linéaire de a et b, donc 2a + 5b et 3a + 7b.
Ainsi d divise A et B.
b. 3A – 2B = 6a + 15b – 6a – 14b = b.
c. 5B – 7A = 15a + 35b – 14a – 35b = a.
d. Si d divise A et B, d divise 3A – 2B = b et d
divise 5B – 7A = a.

52 a. Si d divise a + b et a, d divise a + b – a = b,
donc si a et b sont premiers entre eux alors a + b
est premier avec a et b.
b. a + b est premier avec a et b premiers entre
eux, donc avec leur produit ab.
54 2(3n + 2) – (6n + 5) = 1 donc
PGCD(3n + 2, 6n + 5) = PGCD(1, 6n + 5) = 1 ;
la fraction est donc irréductible.
55 9(7n + 4) – 7(9n + 5) = 1 donc si d divise 7n + 4
et 9n + 5, d = 1 donc PGCD(7n + 4, 9n + 5) = 1 ;
la fraction est donc irréductible.
56 a. A = 2a + 3b, B = 5a + 7b, a = 3B – 7A,
b = 5A – 2B donc PGCD(a, b) = PGCD(A, B) (voir
exercice 50).
b. On en déduit que A et B premiers entre eux
équivaut à a et b premiers entre eux, d’où l’équivalence entre l’irréductibilité des deux fractions.
58 Soit d = PGCD(a ; b). Il existe des entiers a′
et b′ premiers entre eux tels que a = da′, b = db′,
a + b = d(a′ + b′) donc (a′ + b′) = 9.
{a′, b′} ∈ {{1, 8}, {2, 7}, {4, 5}} donc
{a, b} ∈ {{8, 64}, {16, 56}, {32, 40}}.
59 Soit d = PGCD(a ; b). Il existe des entiers a′ et
b′ premiers entre eux tels que a = da′, b = db′,
ab = d2a′b′ donc a′b′ = 55 = 1 × 55 = 5 × 11.
Ainsi {a′, b′} ∈ {{1, 55}, {5, 11}} donc
{a, b} ∈ {{14, 770}, {70, 154}}.
60 On utilise les mêmes notations que pour
l’exercice précédent. a = da′, b = db′, ab = d2a′b′
donc a′b′ = 30 donc {a′, b′} ∈ {{1, 30}, {2, 15},
{3, 10}, {5, 6}} donc {a, b} ∈ {{d, 30d}, {2d, 15d},
{3d, 10d}, {5d, 6d}} (avec d = 169).
61 On utilise les mêmes notations que pour
l’exercice précédent. a = da′, b = db′,
d’où a2 – b2 = d2(a′2 – b′2).
On en déduit : a′2 – b′2 = (a′ – b′)(a′ + b′) = 95
d’où a′ + b′ et a′ – b′ sont entiers naturels.

34 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

c. PGCD(221

63
83 = 47 + 36

36 = a – b

47 = 36 + 11

11 = 47 – 36 = b –(a – b) = 2b – a

36 = 11 × 3 + 3 3 = (a – b) – 3(2b – a) = 4a – 7b
11 = 3 × 3 + 2 2 = (2b – a) – 3(4a – 7b) = 23b −13a
3 = 2 + 1

1 = (4a – 7b) – (23b – 13a) = 17a – 30b

Ainsi 17 × 83 – 30 × 47 = 1, soit
83 × 17 + 47 × (−30) = 1. Le couple solution
obtenu avec l’algorithme d’Euclide est donc
(u ; v) = (17 ; −30).

64 a. (u, v) = (–109, 371). b. (3u, 3v).
65 a. 155 = 65 × 2 + 25, 65 = 25 × 2 + 15,
25 = 15 + 10, 15 = 10 + 5, 10 = 5 × 2 + 0, d’où
PGCD(a ; b) = 5.
b. 25 = a – 2b ; 15 = 5b – 2a ; 10 = 3a – 7b ;
5 = 12b – 5a ;
(u ; v) = (–5, 12) vérifie au + bv = PGCD(a ; b).
66 On effectue la multiplication de a par tous
les entiers naturels successifs jusqu’à trouver le
plus petit u tel que au ≡ 1 [b]. On trouve u et
1- au
alors v = 
.
b
68 a. a – bn2 = 1 ;
b. a – 2nb = 1.
69 a. 3b – 2a = 1 ;

b. 7b – 5a = 1.

b2

70 a. Si a et sont premiers entre eux, il existe
u et v entiers tels que au + b2v = au + b(bv) = 1,
donc au + bV = 1, donc a et b sont premiers entre
eux.
b. au + bv = 1, donc (au + bv)2 = 1, donc
a(au2 + 2buv) + b2v2 = 1, donc a et b2 sont
premiers entre eux.
71 (a2 + ab – b2)2 = 1 donc a2 + ab – b2 = 1
ou a2 + ab – b2 = –1.
a2 + ab – b2 = 1 ⇔ a(a + b) + b(–b) = 1 ;
a2 + ab – b2 = –1 ⇔ a(–a – b) + b(b) = 1.
Dans les deux cas, d’après le théorème de Bézout
a et b sont premiers entre eux.
72 a. En développant,
au + bv = (a + b)u + b(v – u).

b. a et b sont premiers entre eux, il existe donc
(u, v) tels que 1 = au + bv = (a + b)u + b(v – u),
d’où b et a + b sont premiers entre eux.
c. 1 = au + bv = (a + b)v + a(u – v), d’où a et
a + b sont premiers entre eux.
d. D’après la question c. on sait que a + b est
premier avec a, donc il existe des entiers U et V
tels que (a + b)U + aV = 1.
D’après b. on sait que a + b est aussi premier
avec b, donc il existe des entiers U′ et V′ tels que
(a + b)U′ + bV′ = 1.
En multipliant membre à membre ces égalités on
obtient
(a + b)[(a + b)UU ′ + bUV ′ + aU ′V] + ab(VV ′) = 1,
donc a + b et ab sont premiers entre eux.

74 Soit un couple d’entiers (x ; y) solution.
Alors 4 divise 5(y – 3) et est premier avec 5,
donc divise (y – 3), et il existe un entier k tel que
(y – 3) = 4k.
De 4(x – 2) = 5(y – 3), on déduit 4(x – 2) = 4 × 5k
donc (x – 2) = 5k.
Réciproquement, si (x, y) = (2 + 5k, 3 + 4k), alors
4(x – 2) = 5(y – 3).
Donc S = {(2 + 5k, 3 + 4k), k ∈ Z}
75 55(x + 2) = 10(y – 7) ⇔ 11(x + 2) = 2(y – 7).
Voir exercice 74 : S = {(–2 + 2k, 7 + 11k), k ∈ Z}.
77 a = n(n + 7)(n + 11).
• Divisibilité par 2 : ou n est pair et a est pair ou
n est impair donc n + 1 est pair et a est pair, donc
a ≡ 0 [2].
• Divisibilité par 3 :
ou n 0 [3]
ou n ≡ 1 [3], alors n + 2 ≡ 0 [3],
ou n ≡ 2 [3], alors n + 1 ≡ 0 [3].
Dans les 3 cas, a ≡ n(n + 1)(n + 2) [3]
donc a ≡ 0 [3].
Ainsi a est divisible par 2 et 3, premiers entre eux,
donc par 6.

78 a. 10 ≡ 1 [9], donc par compatibilité avec les
puissances, 10n ≡ 1 [9].
b. Par compatibilité avec la somme, 10n + 8 ≡ 9 [9],
donc 10n + 8 ≡ 0 [9], donc est divisible par 9.
c. 10 et 8 sont pairs, donc 10n + 8 est divisible
par 2 et 9 premiers entre eux, donc par 18.
80 a. 9 × 5 + 11 × (–4) = 1.
b. 18x + 15y = 6 ⇔ 6x + 5y = 2
et 6 × (–3) + 5 × 4 = 2.
c. 7 × (–3) + 12 × 2 = 3.
d. Il n’y a pas de solution car s’il y avait une solution 3 devrait diviser 8.

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  35

© éditions Belin, 2012.

Donc a′ + b′ et a′ – b′ sont deux entiers naturels
qui sont des diviseurs associés de 95. De plus
a′ – b′ ≤ a′ + b′. Ainsi (a′ – b′ ; a′ + b′) = (1 ; 95)
ou (5 ; 19), d’où (a′ ; b′) = (48 ; 47) ou (12 ; 7).
On remarque que a′ et b′ sont premiers entre eux.
On en déduit que (a ; b) = (432 ; 423) ou (108 ; 63).
On vérifie que ces couples solutions conviennent.

82 (x0 ; y0) = (13, –20) ; (x1 ; y1) = (65, –100).
84 Soit l’équation (E) : 8x + 5y = 1.
a. (x0 ; y0) = (2, –3).
b. Puisque 8x0 + 5y0 = 1, 8x + 5y = 1 équivaut à
8x + 5y = 8x0 + 5y0, soit 8(x – x0) = 5(y0 – y).
c. D’après le théorème de Gauss, (voir exercice
74), S = {(2 + 3k, –3 – 8k), k ∈ Z}.
85 a. i. 23 et 13 sont premiers entre eux donc
l’équation 23x – 13y = 1 admet une solution dans Z.
ii. (x0 ; y0) = (4, 7).
b. (x1 ; y1) = (8, 14).
c. S = {(8 + 13k, 14 + 23k), k ∈ Z}.

86 a. 34x + 24y = 6 ⇔ 2(17x + 12y) = 2 × 3 ⇔ 
17x + 12y = 3.
b. 17 × 5 + 12 × (–7) = 1.
c. 17 × 15 + 12 × (–21) = 3
ou 17 × 3 + 12 × (–4) = 3.
d. S = {(3 + 12k, –4 – 17k), k ∈ Z}.
e. Pas de solution.
87 1. Faux : voir exercice 4.
2. Vrai : 2 et 3 sont premiers entre eux.
3. Faux : voir exercice 12.
4. Faux : voir exercices 5 et 7.
5. Vrai : PGCD(2a + b ; 3a + 2b) = PGCD(2a + b ;
a + b) = PGCD(a + b ; a) = PGCD(a ; b).
88 1. a. Faux.  b. Vrai.  c. Vrai.  d. Vrai.
2. a. Vrai.  b. Faux.  c. Faux.  d. Vrai.
3. a. Faux.  b. Faux.  c. Faux.  d. Vrai.
89 1. On donne N et la machine affiche
PGCD(A ; B). Les valeurs possibles sont 1 ou 7.
2. 5a – 4b = 7. d divise a et b, donc d divise
5a – 4b, donc d divise 7 donc d = 1 ou d = 7.
3. a. 3 – 4n + 3 = 7k ⇔ 7k – 4n = 3 donc (1,1)
est une solution particulière. Si (k, n) est solution,
alors 7(k – 1) = 4(n – 1). 7 divise 4(n – 1) et est
premier avec 4 donc divise (n – 1) d’après Gauss
et n = 7p + 1, k = 4p + 1. Réciproquement, ces
solutions conviennent.
b. De même, n = 7p + 1 et k = 5p + 1.
4. Si r = 1, d = 7, sinon d = 1.
90 a. On utilise le programme précédent.
d = 1 ou d = 3.
b. 2a – 5b = 3. d divise a et b, donc d divise
2a – 5b donc d divise 3 donc d = 1 ou d = 3.

c. 5 ≡ 2 [3] et 4 ≡ 1 [3] donc a ≡ b [3].
PGCD(a, b) = 3 si et seulement si 3 divise b.
2n + 1 = 3k donc n = 3p + 1 (voir exercice 89)

91 a. d = 1 ou d = 2
b. a – 5b = 2. d divise a et b, donc d divise a – 5b
donc d divise 2 donc d = 1 ou d = 2.
c. PGCD(a, b) = 2 si et seulement si a et n sont
pairs donc n2 impair donc n impair.
92 a. d = PGCD(3n, n + 1) divise 3n et n + 1
donc d divise 3(n + 1) – 3n = 3.
d = 3 si n + 1 = 3k donc n = 3k – 1. Sinon, d = 1.
b. Par homogénéité, PGCD(6n2, 2n(n + 1)) = 2n × d.
93 a. d = PGCD (n + 10, n – 2) = 
PGCD(n – 2, n + 10 – n + 2) = PGCD(n – 2, 12).
b. d divise 12 donc d ∈ {1, 2, 3, 4, 6, 12).
c. Si n = 12k + 2, alors 12 divise n + 10 et n – 2,
donc PGCD = 12.
n 10
d.
est irréductible si PGCD = 1.
n-2
Si n est pair, n + 10 et n – 2 sont pairs, donc
PGCD = 2k. Par conséquent n est impair.
n + 10 ≡ n – 2 [3] donc si n = 3k + 2, PGCD = 3k.
Or n est impair, donc n = 6p + 3 ou 6p + 1.
n + 10 = 6p + 11 et n – 2 = 6p – 1 ne sont pas
divisibles par d ∈ {2, 3, 4, 6, 12).
94 1. a. En développant,
(n + 3)(3n2 – 9n + 16) = 3n3 − 11n + 48.
b. f(n) = 3n2−9n + 16 = 3n(n – 3) + 16, f(0) = 16,
f(1) = 10, f(2) = 10 et pour n ≥ 3, f(n) ≥ 16, donc
f(n) ∈ N.
2. Voir le savoir-faire 1 page 49.
3. D’après 2. avec a = 3n3 − 11n, b = n + 2,
c = 3n2 – 9n + 16 et 1, on obtient
PGCD(3n3 – 11n ; n + 3) = PGCD(48 ; n + 3)
4. a. D48 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}
3n3 - 11n
b.
 ∈ N si n + 3 divise 3n3 − 11n, et
n 3
si n + 3 divise 48, n ∈ {0, 1, 3, 5, 9, 13, 21, 45}.
Réciproquement, toutes ces valeurs conviennent.
95 1. Pour n = 11, a = 1078, b = 161,
PGCD(a, b) = 7 ;
pour n = 12, a = 1440, b = 200, PGCD(a, b) = 40.
2. a = n(n − 4)(n + 3), b = (n – 4)(2n + 1).
3. a. d divise α et β donc d divise 2β – α = 5.
b. 2n + 1 = 5k ⇔ 1 = 5k – 2n et (1, 2) est solution.
Donc n = 2 + 5p (voir exercice 89) et n + 3 ≡ n – 2 [5].
4. d = 5 ⇔ n ≡ 2 [5].
On note D = PGCD(a ; b). Par homogénéité,
D = (n – 4) × PGCD(α, nβ).

36 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

81 Voir exercice 63 : 41 × 5 + 12 × (–17) = 1.

96 1. d(n) divise M – N = 2 donc d(n) = 1 ou
d(n) = 2.
2. Si n est pair, N et M sont impairs donc d(n) = 1.
3. Si n est impair, N et M sont pairs donc d(n) = 2.
4. 81n2 − 1 = MN.
b. Si n est impair, M = 2M′ et N = 2N′ donc
MN = 4M′N′.
Si n est pair, MN est impair et ne peut-être multiple de 4.
97 1. On utilise l’algorithme d’Euclide pour calculer le PGCD.
2. Quelque soit n, d(n) = c – 1, indépendant de n.
3. 2n+1 – 1 – 2(2n – 1) = 1 donc d’après le théorème de Bézout, pour c = 2, c(n + 1) et c(n) sont
premiers entre eux.
4. a. c ≡ 1[c – 1] donc par puissance,
cn ≡ 1[c – 1] donc c – 1 divise C(n) quelque soit n.
c – 1 divise donc dc(n).
b. cn+1 – 1 – c(cn – 1) = c – 1 donc dc(n), qui
divise C(n + 1) et C(n), divise c – 1. On retrouve
la conjecture : dc(n) = c – 1.
5. Ici c = 2 012 donc PGCD = 2 011.
98 1. (k3)2 = (k2)3 = k6.
2. a. d2u2 = d3v3, d ≠ 0 donc u2 = dv3.
b. v divise u2 et est premier avec u donc v divise
u tout en étant premier avec u, donc v = 1.
3. b = d = u2 et a = du = u3. La réciproque est montrée en 1.
4. n = a2 = b3 = u6 d’après 3.
On vérifie que pour tout r tel que 1 ≤ r ≤ 6,
r6 ≡ 1 [7].
Donc soit u ≡ 0 [7] et n ≡ 0 [7] soit u6 ≡ 1 [7]
et n ≡ 1 [7].
99 a. a est premier avec b donc il existe
(u, v) ∈ Z tels que au + bv = 1.
a est premier avec c donc il existe (u′, v′) ∈ Z tels
que au′ + cv′ = 1. En multipliant, au′′ + bcv′′ = 1,
(u′′, v′′) ∈ Z donc a est premier avec bc.
b. c. n + 1 – n = 1 et 2(n + 1) – (2n + 1) = 1 donc
n + 1 est premier avec n et avec 2n + 1 donc avec
n(2n + 1).
100 1. Si x = 0, alors y2 = 0 donc y = 0.
2. a. (E) ⇔ (x – y)2 – xy = 0 ⇔ x2 – 3xy + y2 = 0.
b. Soit d = PGCD(x, y) et x = dx′, y = dy′, x′ et y′
étant premiers entre eux.
En divisant par d ≠ 0, x′2 – 3x′y′ + y′2 = 0.

c. x′(3y′ – x′) = y′2 donc x′ divise y′2. Or x′ est premier avec y′ donc divise y′ d’après le théorème de
Gauss, donc x′ = 1.
d. Ainsi x′ =  1 et y′ est solution de 1  –  3y′ + y′2 = 0.
3. Cette équation n’a pas de solution dans Z,
donc (E) n’a pas de solution entière.

101 1. a. x est premier avec y donc il existe
(u, v) ∈ Z tel que xu + yv = 1 donc
v(x + y) + (u – v)x = 1 donc x est premier avec S,
de même y est premier avec S.
b. D’après l’exercice 99.a., S = x + y et P = xy
sont premiers entre eux.
c. x et y ne peuvent être pairs tous les deux.
S’ils sont tous deux impairs, S est pair et P est
impair et si x et y sont de parité différente, S est
impair et P pair.
2. a. D84 = {1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84}
b.
S et P sont premiers entre eux, donc
{S, P} ∈ {{1, 84}, {3, 28}, {4, 21}, {7, 12}}. Seul
(7, 12) convient, avec 3 + 4 = 7 et 3 × 4 = 12.
3. a = da′, b = db′ donc d (a′ + b′) = 84 et
d2 a′b′ = d3. Donc a′b′ = d et S × P = 84.
En supposant a′ < b′, a = 3 × 12 = 36 et
b = 4 × 12 = 48.
102 1. En développant :
(x−1)(1 + x + x2 + … + xk−1) = xk −1.
2. Voir l’exercice 163 page 39.
3. a. Voir la propriété 8 page 52.
b. Il existe des entiers relatifs u et v′ tels que
m′u + n′v′ = 1 donc mu − n(–v′) = d.
c. mu = nv + d. donc. amu = anv+d = anvad =
(amu − 1) – (anv − 1)ad = anvad – 1 – anvad + ad = 
ad − 1.
c. D’après 2., (ad − 1) divise (amu − 1) et
(anv − 1) donc divise ∆, leur PGCD. D’après b.
∆ divise (amu −1) et (anv −1) donc ad −1. Donc
∆ = ad −1.
d. PGCD (263−1, 260−1) = 2d – 1,
avec d = PGCD(60, 63) = 3 donc
PGCD(263−1, 260−1) = 7.
103 1. Voir propriété 12 page 54.
2. a. Voir AP3 page 41.
b. n(n + 1)(n + 2) est un multiple de 2 et 3 (voir
exercice 93 page 30), premiers entre eux, donc de
6.
c. Si l’un des 4 nombres est multiple de 4, et un
autre de la forme 4p + 2, alors le produit est multiple de 8 et de 3, premiers entre eux, donc de leur
produit 24.
d. n(n + 1)(n + 2)(n + 3)(n + 4) est multiple 5 et
de 24 premiers entre eux, donc de 120.

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  37

© éditions Belin, 2012.

α – 2n = 1 donc α et n sont premiers entre eux.
Donc si δ divise α et n β, alors δ, premier avec
n divise donc β. Ainsi D = 5(n – 4) si n ≡ 2 [5] et
D = (n – 4) sinon.

104 a. Soit d = PGCD(a, b). a = da′, b = db′,
PGCD(a′, b′) = 1.
a da¢ a¢
 = 
 =  (d ≠ 0).
b db¢ b¢
c a
b.  =   ⇔ ad = bc ⇔ a′d = b′c.
d b
D’après le théorème de Gauss, d, premier avec
c, divise b′c, donc divise b′ et b′, premier avec a′,
divise a′d, donc divise d.
b′ ∈ N, d ∈ N donc b′ = d ≠ 0. Par division, on
déduit que a′ = c.
105 a. D78 = {1, 2, 3, 6, 13, 26, 39, 78} et
D14 = {1, 2, 7, 14} et leurs opposés.
p
p
p
b. 78( )3 + u( )2 + v −14 = 0 ⇔
q
q
q
–78p3 = q(up2 + vpq + 14q2).
q divise 78p3 et est premier avec q donc avec q3,
donc q divise 78. De même p divise 14.
c. Il y a au maximum 64 nombres rationnels dont
4 entiers et 30 non entiers positifs.
106 a. an = 10n – 1 + 10n–2 + … + 10 + 1 = 

(10n –1)/9.

an = 10n

D’où 9
−1.
b. Dans la division euclidienne par 2 013, il y a
2 013 restes possibles donc parmi 2 014 premiers
termes de la suite, il en existe deux, au moins,
ayant le même reste.
ap – an ≡ 0 [2 013]
c. am = 10m–1 + 10m–2 + … + 10k + 10k–1 + … + 10 + 1 ;
am = 10k(10m–1–k + 10m–2–k + … + 1) + ak ;
am – ak = am–k × 10k.
d. PGCD (2 013, 10) = 1.
Si 2 013 divise am – ak, alors 2 013, premier avec
10k, divise am–k.
e. On déduit ce résultat de b., c., d.
f. X = 1, A = 1.
TantQue Mod (A, 2 013) ≠ 0
A = A*10 + 1
X = X + 1
FinTanQue.
Afficher N
On pourra remarquer que an+1 = 10 an + 1.
On trouve n = 60. Dans cet exercice, utiliser un
tableur est plus rapide.

107 1. a. 78 × 143 + u39 × 142 + v14 × 392 − 
14 × 393 = 0.
En divisant par 39 × 14, 14u + 39v = 1 129. (2)

b. Voir le savoir-faire 9 page 53.
a = 39, b = 14.
39 = 2 × 14 + 11 ; 11 = a – 2b ;
14 = 11 + 3 ; 3 = b – (a – 2b) = 3b – a ;
11 = 3 × 3 + 2 ; 2 = (a – 2b) – 3(3b – a) = 4a – 11b ;
3 = 2 + 1 ; 1 = (3b – a) – (4a – 11b) = 14b – 5a ;
14(–25) + 39 × 9 = 1.
c. S = {(–25 + 39k, 9 – 14k), k ∈ Z}
d. Pour k = 1, u = 14 donc le couple cherché est
(14, –5).

108 1. a. 11 et 7 sont premiers entre eux donc
d’après le théorème de Bézout, 11u − 7v = 1 ;
(2 ; 3) est un tel couple : 11 × 2 – 7 × 3 = 1
b. (10, 15) est une solution particulière de
l’équation (E) ; (3, 4) en est une autre.
2. S = {(3 + 7k, 4 + 11k), k ∈ Z}, 0 ≤ 3 + 7k ≤ 50
et 0 ≤ 4 + 11k ≤ 50. Donc k ∈ {0, 1, 2, 3, 4}. Il y
a 5 points qui conviennent.
109 1. a. 20u − 9v = 2 donc v ≡ 0 [2].
b. d divise u et v donc d divise 2. D’où d = 1 ou d = 2.
2. (1, 2) est solution et S = {(1 + 9k, 2 + 20k), k ∈ Z}.
3. 2 divise y donc PGCD(x ; y) = 2 si et seulement
x est pair, donc k impair.
110 À la question 2.a. on veut montrer que le
couple (a ; −b) est solution de (E).
1. a. 8 × 2 + 5(–3) = 1
b. S = {(2 + 5k, –3 – 8k), k ∈ Z}.
2. a. N = 8a + 1 = 5b + 2 donc 8a – 5b = 1 donc
a = 2 + 5k
b. N = 8(2 + 5k) + 1 = 40k + 17 = 5(3 + 8k) + 2
3. S = {(200 + 5k, –300 – 8k), k ∈ Z}.
4. Si x désigne le nombre d’hommes et y celui
des femmes, 8x + 5y = 100 et x ≥ 0, y ≥ 0 donc
200 + 5k ≥ 0 et k ≥ – 40 d’où – 300 – 8k ≥ 0 et
k ≤ – 38.
Si k = –38, x = 10 et y = 4. Si k = –39, x = 5 et y = 12.
Si k = –40, x = 0 et y = 20 (cas à éliminer).
111 1. 105u = 6 + 81v donc 35x − 27y = 2.
2. a. a = 35, b = 27.
35 = 27 + 8 ; 8 = a – b ;
27 = 3 × 8 + 3 ; 3 = b – 3(a – b) = 4b – 3a,
8 = 3 × 2 + 2 ; 2 = (a – b) – 2(4b – 3a) = 7a – 9b ;
3 = 2 + 1 ; 1 = (4b – 3a) – (7a – 9b) = 13b – 10a.
D’où (–10, –13) solution de (E2)
b. (–20 ; –26) solution de (E1).
c. S = {(–20 + 27k, –26 + 35 k), k ∈ Z}.
d. On cherche le plus petit couple positif : (7, 9)
Entre J0 et J1 il s’écoulera 7 × 105 = 735 jours.
3. a. 735 = 366 + 365 + 4 ce qui nous mène au
20 décembre 2013.

38 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

En règle générale, on peut montrer que le proÊ nˆ
duit de p nombres consécutifs vaut Á ˜ p!
Ë p¯

112 1. a. Si a est le nombre de tas de 7, et b celui
de tas de 5, n = 7a + 5 = 5b + 3, d’où le système.
b. n0 = 33, le nombre suivant est 68, et ils sont
espacés de 35.
2. a. 5 et 7 sont premiers entre eux, donc d’après
le théorème de Bézout, (u ; v) existe.
b. n2 ≡ 5 × 5v [7]. Or 5v ≡ 1 [7] donc n2 ≡ 5 [7].
n2 ≡ 3 × 7u [5]. Or 7u ≡ 1 [5] donc n2 ≡ 3 [5].
(u, v) = (–2, 3) donc n2 = 3 × 7(–2) + 5 × 5 × 3 = 33.
2. a. n − n2 est divisible par 5 et 7 premiers
entre eux, donc d’après le théorème de Gauss,
par leur produit, 35 et n − n2 ≡ 0 [35].
b. Réciproquement, si n = 33 + 35k alors n ≡ 5 [7]
et n ≡ 3 [5].
3. 150 < 33 + 35k < 200 ⇔ 117 < 35k < 167.
Le seul entier qui convient pour k est 4 donc Chloé
a 173 jetons.
113 1. a. 239 = 18 × 13 + 5 = 14 × 17 + 1.
b. Par définition des congruences,
N = 17x + 1 = 13y + 5 donc 17x – 13y = 5 – 1 = 4.
2. a. (1, 1) est solution donc S = {(1 + 13k,
1 + 17k), k ∈ Z}.
b. N = 17x + 1 = 17(1 + 13k) + 1 = 18 + 221k.
N 5 [13]
3. D’après 2., si Ì
, alors N ≡ 18 [221].
ÔÓN 1[17]
Réciproquement, si N ≡ 18 [221], alors
N = 18 + 221k donc N ≡ 5 [13] et N ≡ 1 [17].

Préparer le BAC
Exercices guidés BAC
123 Partie A
1. 11 × (–7) − 26 × (–3) = 1.
2. Soit (x, y) une solution,
alors 11(x + 7) = 26(y + 3).
11 divise 26(y + 3) et est premier avec 26 donc,
d’après le théorème de Gauss, 11 divise y + 3 et
y + 3 = 11k.
En remplaçant on obtient x + 7 = 26k. Réciproquement, (–7 + 26k, –3 + 11k) est solution.
3. Pour k = 1, 0 ≤ –7 + 26 ≤ 25 donc (19, 8) est
solution.

Partie B
1. W → 22 → 50 → 16 → Q.
2. a. D’après A 3., 11 × 19 – 8 × 26 = 1,
donc 11 × 19 ≡ 1 [26].
Si 11x ≡ j [26], alors 19 × 11x ≡ 19 j [26].
Or 11 × 19 ≡ 1 [26], donc 11x × 19 ≡ x [26],
et x ≡ 19 j [26].
Si x ≡ 19 j [26], alors 11x ≡ 11 × 19 j [26].
Or 11 × 19j ≡ j [26] donc 11x ≡ i [26].
b. y ≡ 11x + 8 [26], donc y – 8 ≡ 11x [26],
donc x ≡ 19(y – 8) [26].
3. W → 22, donc si y = 22, x ≡ 19 × 14 [26], donc
x = 6 et W → G.
4. Algorithme pour coder et décoder :
L1, L2, L3 listes telles que L1 existe.
Début
Pour x allant de 0 à 25 faire
L1(x) = CAR(x + 65)
L2(x) = CAR(MOD(11x + 8 ; 26) + 65)
L3(x) = CAR(MOD(19(x + 18) ; 26) + 65)
FinPour
Afficher L1, L2, L3

124 1. 20+1 + 1 = 3 = x0 et si xn = 2n+1 + 1,

alors xn+1 = 2(2n+1 + 1) − 1 = 2n+1+1 + 1.
2. a. PGCD (9, 17) = 1 donc x2 et x3 sont premiers entre eux.
b. 2xn − xn+1 = 1 donc xn et xn+1 sont premiers
entre eux.
3. a. Par récurrence : 2x0 – y0 = 6 – 1 = 5.
Si 2xn − yn = 5, alors 2xn+1 − yn+1 = 2(2xn − 1)
– (2yn + 3) = 2(2xn − yn) – 5 = 10 – 5 = 5.
Par conséquent pour tout n de N, 2xn – yn = 5.
b. yn = 2 xn – 5 = 2n+2 – 3.
c. 22 ≡ – 1 [5] donc 24 ≡ 1 [5].
Or 24k+r = (24)k × 2r donc 24k+r ≡ 2r [5].
Par suite, si p ≡ r [4], 2p ≡ 2r [5]
4. a. On conjecture que dn = 5 si n = 4k + 1 et
dn = 1 dans les autres cas.
b. 2xn − yn = 5 donc dn = PGCD (xn, yn) divise 5.
On a donc dn = 1 ou dn = 5.

QCM – Vrai ou faux BAC
125 Dans cet exercice, la proposition l. est modifiée :
x 2 [4]
l. Il n’existe aucun entier relatif x tel que Ì
.
ÓÔx 5 [6]
a. Vrai. PGCD (2 004 ; 4 002) = 
6PGCD(334 ; 667) et 2 × 334 – 667 = 1.
b. Vrai. 3n3 − 11n = (n + 3)(3n2 – 9n + 16) – 48.
c. Vrai d’après l’algorithme d’Euclide.

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  39

© éditions Belin, 2012.

4. La conjonction suivante aura lieu dans
27 × 105 = 81 × 35 = 2 835 jours, soit 7 ans
et demi environ.

126 1. b.  2. c.  3. b.  4. b.c.  5. c.

Exercice BAC
127 Partie A
1. Voir propriété 11 page 54.
2. Voir propriété 12 page 54.
Partie B
1. a. Exemple d’algorithme :
Entrer N.
Pour k variant de 1 à N, A = 17k + 9. B = (A – 3)/5
Si partie décimale de B = 0, afficher A.
b. On trouve 43, 128, 213. La première solution
positive semble être 43 et on obtient les autres
en ajoutant 85.
2. a. 17 et 5 sont premiers entre eux, donc
d’après le théorème de Bézout il existe un couple
(u ; v) d’entiers relatifs tels que 17u + 5v = 1.
b. n0 ≡ 9 × 5v [17]. Or 5v ≡ 1 [17]
donc n0 ≡ 9 [17].
n0 ≡ 3 × 17u [5]. Or 17u ≡ 1 [5] donc n0 ≡ 3 [5].
c. (u, v) = (–2, 7)
donc n0 = 3 × 17(–2) + 5 × 7 × 9 = 213.
3. a. n ≡ 9 [17] et n ≡ 3 [5] et n0 ≡ 9 [17]
et n0 ≡ 3 [5]. D’où n ≡ n0 [17] et n ≡ n0 [5].
n − n0 est divisible par 17 et 5, premiers entre
eux, donc par leur produit.

b. n0 ≡ 43 [85], donc si n appartient à S,
n = 43 + 85k où k est un entier relatif.
Réciproquement, si n = 43 + 85k, alors n ≡ 9 [17]
et n ≡ 3 [5] et n appartient à S.

128 Cas 1
1. Soit x une solution, (x – n) = ka = k′b, donc
ka′ = k′b′.
2. a′ divise k′b′ et est premier avec b′, donc
d’après le théorème de Gauss divise k′ et k′ = k′′a′
donc k′b = k′′a′b′ et (x – n) = k′′da′b′ = kµ.
3. Si x – n = k µ = kab′ = ka′b, alors x est solution.
4. La solution est de la forme x = n + kµ.
Exemple : n = –1, a = 4, b = 6, d = 2, a′ = 2, b′ = 3
et µ = 12 et x = 12k – 1.
Cas 2
1. a. x = n + ka = m + k′b donc m – n = ka – k′b.
b. a et b sont premiers entre eux donc, d’après
le théorème de Bézout, il existe (u, v) tels que
au + bv = 1.
2. a. Soit x0 = n + (m – n)au = n(1 – au) + ma
u = nbv + mau.
b. x0 ≡ nbv [a] or bv ≡ 1 [a] donc x0 ≡ n [a]
de même, x0 ≡ m [b].
c. Si x ≡ x0 [a] et x0 ≡ n [a], alors x ≡ n [a] de même,
x ≡ m [b].
Si x est solution, x ≡ n [a] et x0 ≡ n [a],
donc x ≡ x0 [a].
d. On est ramené au premier cas et µ = ab.
Exemple : 5 × 3 – 7 × 2 = 1
donc x0 = 6 × 5 × 3 – 7 × 2 × 2 = 62.
Ainsi les solutions sont x = 62 + 35k = 35k′ + 27
Applications
a. x = 5 + 9k = 7 + 27k′
donc 2 = 9k + 27k′ = 9(k + 3k′) : impossible car
9 ne divise pas 2.
b.  x = 5 + 54k = 23 + 48k′ donc 18 = 54k + 48k′
= 6(9k + 8k′), donc 3 = (9k + 8k′).
Or 3 × 9 – 3 × 8 = 1. Posons
x0 = 5 + 3 × 54 = 23 + 3 × 48 =
23 × 9 – 5 × 8 = 167.
En reprenant le cas 1 puis le cas 2, a = 54, b = 48,
d = 6, a′ = 9, b′ = 8, m = 432, x = 167 + 342k.

129 1. 5 × 5 + 4 × 17 =  93 et 5  × 4 + 4 × 15 = 80
donc z = 15, t = 2.
Ainsi FE → PC, de même RM → DO et AT → LZ.
2. a. En multipliant la 1re ligne par d, la 2e par
–b et en les additionnant, puis la 1re ligne par –c
et la 2e par a, on obtient S′.
b. ∆ est premier avec n ⇔ ∆u + vn = 1 d’après le
théorème de Bézout.

40 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

d. Faux. 2n + 1 – 2n = 1 donc n et 2n + 1 sont
toujours premiers entre eux.
e. Faux. PGCD(1 + 3 ; 2 + 1) = 1.
f. Vrai d’après le théorème de Gauss et après
vérification.
g. Vrai. Si a ≡ b (p), alors na ≡ nb (p).
Si na ≡ nb (p), alors n(a – b) ≡ 0 (p). D’où p
divise n(a – b) et est premier avec n, donc d’après
le théorème de Gauss, p divise a – b.
h. Vrai d’après le théorème de Gauss et après
vérification.
i. Vrai. Si d divise 3n + 4 et 4n + 3 divise
4(3n + 4) – 3 (4n + 3) = 7, alors d divise 7.
Si n = 7k + 1, 3n + 4 = 7(3k + 1)
et 4n + 3 = 7(4k + 1), alors 7 divise d.
j. Faux. 7 – 5 = 2
k. Vrai. 11 ≡ 2 [3] et 11 ≡ 1 [5]. Si n ≡ 2 [3] et
n ≡ 1 [5], alors n ≡ 11 [3] et n ≡ 11 [5], donc
n – 11 est divisible par 3 et 5 premiers entre eux,
il l’est donc aussi par leur produit.
l. Vrai. Si x = 2 + 4k, il est pair et s’il vaut 5 + 6k,
il est impair.

130 1. a. Pour n ≠ 0, a2 + b2 = c2 ⇔
(na)2 + (nb)2 = (nc)2
b. Supposons a = da′, b = db′. On a
(da′)2 + (db′)2 = d2 (a′2 + b′2) = c2 donc d2 divise
c2 donc d divise c. On procède de même pour les
autres cas.
c. Si a et b sont premiers entre eux et d divise a et c,
alors (d’après b.) d divise b donc d = 1 et a et c sont
premiers entre eux. En divisant a, b, et c par le plus
grand des diviseurs commun aux trois, on obtient
des nombres deux à deux premiers entre eux.
2. a. b. Pour un TPI, les trois ne peuvent être pairs.
S’il y a 1 ou 3 nombres impairs, a2 + b2 – c2 ≡ 1 [2] :
impossible donc il y a 2 nombres impairs et un pair.
c. Si c est pair, a et b sont impairs (voir exercice 78 page 30) alors a2 ≡ 1 [4] d’où c2 ≡ 2 [4],
impossible donc c est impair.
d. a et c sont impairs et b est pair.
3. a. i. a2 + b2 = c2 ⇔ b2 = c2 – a2 = (c + a)(c – a).
Or a et c sont impairs donc c + a et c – a et b
sont pairs.
2

Ê bˆ
Ê c aˆ Ê c - aˆ b c a c - a
ÁË 2˜¯ ÁË 2 ˜¯ ÁË 2 ˜¯ 2 , 2 , 2 sont donc
des entiers naturels.
c a
c-a
ii. Si d divise
et
, alors d divise leur
2
2
somme c et leur différence a donc d = 1 (TPIR).
b
iii. On applique la propriété avec z =  ,
2
c a
c-a
x = 
et y = 
.
2
2
iv. c = x + y = u2 + v2 ; a = x – y = u2 – v2
et b2 = c2 – a2 = 4 u2 v2.
b = 2uv où u et v sont premiers entre eux et de
parités différentes puisque x et y le sont.
b. Réciproquement, si b = 2uv, a = u2 – v2 et
c = u2 + v2.
Avec u et v premiers entre eux et de parités différentes tels que 0 < v < u, alors a2 + b2 = c2
donc b est pair, a et c sont impairs.
Si d divise a et c, d est impair et divise 2u2 et 2v2.
Or si u et v sont premiers entre eux, u2 et v2 aussi
donc d = 1.
Si d divise c et b, d est impair donc divise uv, et d
divise b + c = (u + v)2.

Or uv et u + v sont premiers entre eux (voir exercice 101) donc d = 1.
4. Il suffit de faire afficher les listes et dim(L1) qui
donne le nombre d’éléments de chaque liste.

131 1. f(x) = anxn + an–1xn–1 + … + a1x =
x(anxn–1 + an–1xn–2 + … + a1).
p
2. a. qnf( ) = anpn + an–1pn–1q + … + a1p
q
qn–1 + a0qn = 0.
b. anpn = –(an–1pn–1q + … + a1p qn–1 + a0qn).
= –q(an–1pn–1 + … + a1p qn–2 + a0qn–1).
c. Soit u et v tels que up + vq = 1, alors
1 = (up + vq)n = q × u′ + v′pn.
d. D’après le théorème de Gauss, q divise pn × an
et est premier avec pn donc divise an. De même,
a0qn = –p(anpn–1 + … + a1qn–1).
p
3
3. p divise 3 et q divise 2 donc ∈ {–3, – , –1, 1,
q
2
3
, 3}. On cherche les valeurs entières de 3x–3 – 2x4
2
p
pour x =  . Pour a = –5, f(–1) = 0 et pour a = 1,
q
f(1) = 0. Aucune autre valeur ne convient.
4. a. p divise 21 et q divise 4 donc p ∈ {–21, –7,
–3, –1, 1, 3, 7, 21} et q ∈ {1, 2, 4}. À la calcula7
trice on teste les 24 valeurs et on trouve : a = 
4
2
b. Par identification, f(x) = (4x – 7)(x  – 3).
7
c. S = {– 3, 3, }.
4
132 Si la fonction f telle que f(x) = x7 + 3x + 3 a

p
, alors q divise 1 et p divise 3. Les
q
seules racines possibles sont –3, –1, 1, 3 et
aucune ne convient.
une racine

133 Soit d la distance entre deux arbres ; d est un
diviseur commun à 132, 156 et 204.
132 = 11 × 12, 156 = 13 × 12 et 204 = 17 × 12.
Les diviseurs communs à ces trois nombres sont
les diviseurs de 12. Le nombre d’arbres sera
minimal si la distance est maximale. Il faudra
11 + 13 + 17 + 1, soit 42 arbres au minimum.
134 Soit xi le nombre de départs pour chacun
des navires et T le nombre de jours écoulés. T est
donc un multiple commun à 8, 10 et 15.
T = 8x1 = 10x2 = 15x3.
8x1 = 10x2 ⇔ 4x1 = 5x2.
5 divise 4 x1 et est premier avec 4 donc d’après
le théorème de Gauss divise x1. Ainsi x1 = 5k et
T = 40k.
40k = 15x3 ⇔ 8k = 3x3.

Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss n  41

© éditions Belin, 2012.

c. ∆x ≡ (dz – bt) [n], donc ∆∆x ≡ ∆′ (dz – bt) [n].
Or ∆∆′ ≡ 1 [n] donc x∆∆′ ≡ x [n] donc
x ≡ ∆′ (dz – bt) [n] 0 ≤ x ≤ n et y ≡ ∆′ (–cz + at) [n],
0 ≤ y ≤ n.
3. On pose (a, b) = (5, 17) et (c, d) = (4, 15), n = 26.
a. ∆ = 7. On cherche ∆′ tel que 7∆′ – 26v = 1. On
trouve ∆′ = 15.
b. FI QM FP OA JG HK → VO US ET ES BO NS

Accompagnement
personnalisé
 AP 1

1. Les trois raisonnements sont faux.
Réponse 1. Théorème faux : d divise a + b donc d
divise a et d divise b.
Réponse 2. Théorème faux : PGCD (a + b, a + c) =
PGCD(b, c).
Réponse 3. Mauvaise compréhension du théorème.
• Autres raisonnements :
a. faux, b. exact, c. exact, d. faux.
• Propriétés fausses :
–– si d divise a + b, alors d divise a et d divise b.
–– confusion entre il existe u et v et pour tout
(u, v)…
• Raisonnements b. et c. exacts mais incomplets.
–– raisonnement b. : si d divise a et d divise b, d
divise toute combinaison linéaire entière de a et b.
–– raisonnement c. : si a = bq + r,
PGCD (a, b) = PGCD (b r).
• Raisonnement possible :
dn divise An et An+1, donc divise toute combinaison linéaire entière de An et An+1, en particulier
An+1 – An = 2n(2 – 1) = 2n
2. a. exact  b. exact  c. réponse non complète.
• Rédaction :
a. Pour tout n, An ≡ p [2] donc An a même parité
que p.
b. An+1 ≡ p [2] donc An ≡ An+1 [2]. Si 2 divise An
et An+1, 2 divise dn, sinon dn est impair ;
dn a même parité que An, donc que p.
c. n = p = 2 011 donc d est impair. Or les
diviseurs de dn sont ceux de 2n qui sont des
puissances de 2. Seule 20 = 1 est impair donc
PGCD(22011 + 2 011, 22012 + 2 011) = 1.

 AP 3

Dans cet exercice la question 3. a été modifiée comme suit :
3. a. Montrer que n divise si – sj et que
–(n – 1) ≤ si – sj ≤ n – 1.
b. En déduire que si = sj.

1. 1 est premier avec tout nombre et
n – (n – 1) = 1 donc n est premier avec n – 1.
2. a. Par définition de ri, n divise asi – ri.
b. Si d divise n et ri, d divise asi premier avec n
donc avec d donc d = 1.
c. ri est premier avec n et est élément de S par
définition de S.
3. a. ri = rj donc asi ≡ asj [n]. Alors n divise
a(si – sj) et est premier avec a donc n divise
a(si – sj) ;
1 ≤ si ≤ n – 1, 1 ≤ sj ≤ n – 1
donc –(n – 1) ≤ si – sj ≤ n – 1.
b. Le seul multiple de n entre –(n – 1) et n – 1 est
0 donc si = sj donc i = j, ce qui est impossible.
c. Il y a donc j(n) nombres ri distincts dans S.
4. a. r1 × … × rj(n) = s1 × … × sj(n) donc
as1 × … × asj(n)  ≡ s1 × … × sj(n)  [n].

b. aj(n)s1 × … × sj(n)  ≡ s1 × … × sj(n)  [n] donc n
divise (aj(n) – 1)s1 × … × sj(n) .

c. On applique le savoir faire 10 puis on raisonne
par récurrence. On utilise ensuite le théorème de
Gauss, pour conclure que n divise (aj(n) – 1).
5. D’après 4.c., si a est un entier naturel premier
avec n, aj(n) ≡ 1 [n].

 AP 4

1. a. D26 = {1, 2, 13, 26} ; les nombres premiers avec 26 n’ont aucun diviseur dans D26.
Il y a 13 nombres impairs inférieurs à 26 et un
seul multiple de 13 donc j(26) = 12
b. 122 = 144 = 130 + 14 donc 122 ≡ 14 [26] et
14 × 12 ≡ 12 [26], d’où l’alternance.
132 ≡ 13 [26] donc pour tout n, 13n ≡ 13 [26].
c. Si a est impair différent de 13, a12 ≡ 1 [26]
d’après AP3 5. et AP4 1.a.
Tout nombre b pair < 26 s’écrit b = 2kc où c est
impair différent de 13 et k ≥ 1.
212 ≡ 14 [26] et 14k ≡ 14 [26] donc b12 ≡ 14 [26].
Pour tout b, b13 ≡ b [26].
e. k = 1, k = 13 conviennent, mais aussi 5, 7, 11.
2. a. 7 et 12 sont premiers entre eux donc
d’après le théorème de Bézout, il existe (u, v)
entiers relatifs tels que 7u = 1 + 12v.
b. 7 × 7 = 1 + 12 × 4 donc u = 7.
c. (n7)u = n1+12v = n1+12v donc d’après 1.d.,
(n7)u ≡ n [26].
i. Si n7 ≡ m7 [26], par puissance, (n7)u ≡ (n7)
u [26] alors n ≡ m [26].
ii. Si a ≡ n7 [26], alors au ≡ (n7)u [26].
3. Il lui suffit de faire la même chose, puisque u = 7.

42 n Chapitre 2 n PGCD, théorème de Bézout et théorème de Gauss

© éditions Belin, 2012.

3 divise 8k et est premier avec 8 donc d’après
le théorème de Gauss, divise k. Ainsi k = 3k′ et
T = 120k′.
Le prochain départ commun aura lieu dans
120 jours, c’est-à-dire le 9 août.


Aperçu du document FICHIER_COMP_6198MTSSpe_n_1.pdf - page 1/17
 
FICHIER_COMP_6198MTSSpe_n_1.pdf - page 3/17
FICHIER_COMP_6198MTSSpe_n_1.pdf - page 4/17
FICHIER_COMP_6198MTSSpe_n_1.pdf - page 5/17
FICHIER_COMP_6198MTSSpe_n_1.pdf - page 6/17
 




Télécharger le fichier (PDF)


FICHIER_COMP_6198MTSSpe_n_1.pdf (PDF, 3.1 Mo)

Télécharger
Formats alternatifs: ZIP



Documents similaires


cours arithmetique specialite maths terminale 14
demonstration
chap 2
fichier comp 6198mtsspe n 1
chapitre1 notions d arithmetique
identite de bezout