Dans Z/6Z, la première équation peut s’écrire : 5 x + 2 y = 3.
En multipliant par 5, cette équation devient : x + 4 y = 3 , soit
x = 2 y + 3, ou encore : x = 2y + 3 + 6k avec k ∈ Z.
Reportons cette expression dans la seconde équation :
3y + 2k ≡ 0 (mod 5) , puis y ≡ k (mod 5) en effectuant des calculs dans
Z/5Z.
On obtient donc (en reportant la valeur de y dans l’expression qui donne x) :
x = 3 + 8k + 10k
y = k + 5k
avec k ∈ Z et k ∈ Z
Exercice 1.11 : Lemme chinois et application
1. Soit p et q des entiers premiers entre eux. Soit a et b des entiers. Montrer qu’il
existe un entier x tel que :
x ≡ a ( p)
x ≡ b (q)
2. Soit p et q deux entiers. Montrer l’équivalence :
le groupe produit Z/ pZ × Z/qZ est cyclique ⇐⇒ p ∧ q = 1.
1. L’hypothèse « premiers entre eux » doit vous faire penser au théorème de Bézout.
Comme p et q sont premiers entre eux, d’après le théorème de Bézout il
existe des entiers u et v tels que pu + qv = 1.
En terme de congruences, cette égalité entraîne que : pu ≡ 1 (q) et
qv ≡ 1 ( p).
D’autre part, on a : pu ≡ 0 ( p) et qv ≡ 0 (q).
Donc, en posant x = bpu + aqv, on a bien :
x ≡ a ( p) et x ≡ b (q) ,
c’est-à-dire que x est une solution du problème posé.
L’appelation « lemme chinois » vient du fait que les chinois de la Haute Antiquité
utilisaient ce résultat en astronomie. Étant donnés deux astres dont les durées de
révolution et les positions sont connues, le temps qu’ils mettront à retrouver la
même position s’obtient en utilisant ce lemme.
2. Pour démontrer une équivalence, on démontre deux implications. Et dans une
deuxième question, il est fréquent que le résultat de la première question soit utile.
© Dunod. La photocopie non autorisée est un délit.
15
Chapitre 1 • Algèbre générale
En multipliant par 5, cette équation devient : x + 4 y = 3 , soit
x = 2 y + 3, ou encore : x = 2y + 3 + 6k avec k ∈ Z.
Reportons cette expression dans la seconde équation :
3y + 2k ≡ 0 (mod 5) , puis y ≡ k (mod 5) en effectuant des calculs dans
Z/5Z.
On obtient donc (en reportant la valeur de y dans l’expression qui donne x) :
x = 3 + 8k + 10k
y = k + 5k
avec k ∈ Z et k ∈ Z
Exercice 1.11 : Lemme chinois et application
1. Soit p et q des entiers premiers entre eux. Soit a et b des entiers. Montrer qu’il
existe un entier x tel que :
x ≡ a ( p)
x ≡ b (q)
2. Soit p et q deux entiers. Montrer l’équivalence :
le groupe produit Z/ pZ × Z/qZ est cyclique ⇐⇒ p ∧ q = 1.
1. L’hypothèse « premiers entre eux » doit vous faire penser au théorème de Bézout.
Comme p et q sont premiers entre eux, d’après le théorème de Bézout il
existe des entiers u et v tels que pu + qv = 1.
En terme de congruences, cette égalité entraîne que : pu ≡ 1 (q) et
qv ≡ 1 ( p).
D’autre part, on a : pu ≡ 0 ( p) et qv ≡ 0 (q).
Donc, en posant x = bpu + aqv, on a bien :
x ≡ a ( p) et x ≡ b (q) ,
c’est-à-dire que x est une solution du problème posé.
L’appelation « lemme chinois » vient du fait que les chinois de la Haute Antiquité
utilisaient ce résultat en astronomie. Étant donnés deux astres dont les durées de
révolution et les positions sont connues, le temps qu’ils mettront à retrouver la
même position s’obtient en utilisant ce lemme.
2. Pour démontrer une équivalence, on démontre deux implications. Et dans une
deuxième question, il est fréquent que le résultat de la première question soit utile.
© Dunod. La photocopie non autorisée est un délit.
15
Chapitre 1 • Algèbre générale