A p p l i c a t i o n
1. Démontrez que 143 et 100 sont premiers entre eux.
2. Déterminez tous les couples (u,v) d'entiers relatifs tels que :
143 u + 100 v = 1 .
S o l u t i o n
1. La décomposition en facteurs premiers des deux nombres s'écrit :
143 = 11 × 13 ; 100 = 2
2
× 5
2 .
Comme il n'y a aucun facteur premier commun à ces deux décompositions, les
nombres 100 et 143 sont premiers entre eux.
L'algorithme d'Euclide conduit à une deuxième démonstration de ce résultat. Il prouve l'existence de nombres u et v du théorème de Bézout, en fournissant explicitement
une solution particulière.
Il s'agit de réaliser une suite de divisions euclidiennes : de 143 par 100, puis de 100
par le reste r 1 obtenu, puis de r 1 par r 2 … On obtient :
143 = 100 × 1 + 43
100 = 43 × 2 + 14
43 = 14 × 3 + 1
Comme cet algorithme se termine par 1, c'est une nouvelle preuve que 143 et 100 sont
premiers entre eux.
On va en déduire un exemple de nombres u et v tels que :
143 u + 100 v = 1 ,
par des substitutions successives des restes en partant de la dernière égalité où figure
déjà le 1 du second membre.
1 = 43 − 14 × 3
= 43 − (100 − 43 × 2) × 3 = (−3) × 100 + 7 × 43
= (−3) × 100 + 7 × (143 − 100) = 7 × 143 + (−10) × 100.
Les nombres u 0 = 7 et v 0 = −10 vérifient donc 143 u 0 + 100 v 0 = 1 .
2. Considérons des entiers relatifs u et v tels que 143 u + 100 v = 1.
En retranchant l'égalité précédente, on obtient :
143 (u − u 0 ) = 100 (v 0 − v) .
143 divise donc 100 (v 0 − v). Comme 143 est premier avec 100, on en déduit, d'après
le théorème de Gauss, que 143 divise (v 0 − v), c'est-à-dire qu'il existe k ∈ Z tel que :
v 0 − v = 143 k.
En reportant, on obtient aussi : u − u 0 = 100 k.
39
F I C H E 8 – A r i t h m é t i q u e d a n s Z
© Dunod – La photocopie non autorisée est un délit.
8
1. Démontrez que 143 et 100 sont premiers entre eux.
2. Déterminez tous les couples (u,v) d'entiers relatifs tels que :
143 u + 100 v = 1 .
S o l u t i o n
1. La décomposition en facteurs premiers des deux nombres s'écrit :
143 = 11 × 13 ; 100 = 2
2
× 5
2 .
Comme il n'y a aucun facteur premier commun à ces deux décompositions, les
nombres 100 et 143 sont premiers entre eux.
L'algorithme d'Euclide conduit à une deuxième démonstration de ce résultat. Il prouve l'existence de nombres u et v du théorème de Bézout, en fournissant explicitement
une solution particulière.
Il s'agit de réaliser une suite de divisions euclidiennes : de 143 par 100, puis de 100
par le reste r 1 obtenu, puis de r 1 par r 2 … On obtient :
143 = 100 × 1 + 43
100 = 43 × 2 + 14
43 = 14 × 3 + 1
Comme cet algorithme se termine par 1, c'est une nouvelle preuve que 143 et 100 sont
premiers entre eux.
On va en déduire un exemple de nombres u et v tels que :
143 u + 100 v = 1 ,
par des substitutions successives des restes en partant de la dernière égalité où figure
déjà le 1 du second membre.
1 = 43 − 14 × 3
= 43 − (100 − 43 × 2) × 3 = (−3) × 100 + 7 × 43
= (−3) × 100 + 7 × (143 − 100) = 7 × 143 + (−10) × 100.
Les nombres u 0 = 7 et v 0 = −10 vérifient donc 143 u 0 + 100 v 0 = 1 .
2. Considérons des entiers relatifs u et v tels que 143 u + 100 v = 1.
En retranchant l'égalité précédente, on obtient :
143 (u − u 0 ) = 100 (v 0 − v) .
143 divise donc 100 (v 0 − v). Comme 143 est premier avec 100, on en déduit, d'après
le théorème de Gauss, que 143 divise (v 0 − v), c'est-à-dire qu'il existe k ∈ Z tel que :
v 0 − v = 143 k.
En reportant, on obtient aussi : u − u 0 = 100 k.
39
F I C H E 8 – A r i t h m é t i q u e d a n s Z
© Dunod – La photocopie non autorisée est un délit.
8