Théorème Chinois et applications

Publié par

Théorème Chinois et applications

Publié le : jeudi 21 juillet 2011
Lecture(s) : 411
Nombre de pages : 4
Voir plus Voir moins
Théorème Chinois et conséquences
Page
1
G. COSTANTINI
THÉORÈME CHINOIS ET APPLICATIONS
1.
Un morphisme de groupe injectif remarquable
Soient (
m
,
n
)
(
*
)
2
.
Considérons l'application
ƒ
qui à tout entier relatif
x
associe un couple constitué de sa classe modulo
m
et de
sa classe modulo
n
:
ƒ
:
m
×
n
x
( [
x
]
m
, [
x
]
n
)
Où : [
x
]
m
=
{
y
|
y
-
x
m
}
Montrons que
ƒ
est un
morphisme de groupes additifs
:
2200
(
x, y
)
(
)
2
,
ƒ
(
x
+
y
)
=
( [
x
+
y
]
m
, [
x
+
y
]
n
)
Et d'après les lois sur les classes :
ƒ
(
x
+
y
)
=
( [
x
]
m
+
[
y
]
m
, [
x
]
n
+
[
y
]
n
)
Et par propriétés des couples :
ƒ
(
x
+
y
)
=
( [
x
]
m
, [
x
]
n
)
+
( [
y
]
m ,
[
y
]
n
)
=
ƒ
(
x
)
+
ƒ
(
y
)
Ce qui prouve que
ƒ
est un morphisme du groupe (
,
+
) sur le groupe produit
(
29
m
,
+
×
(
29
n
,
+
.
C'est même un morphisme d'anneaux (car
ƒ
(
xy
)
=
( [
xy
]
m
, [
xy
]
n
)
=
( [
x
]
m
, [
x
]
n
)
×
( [
y
]
m ,
[
y
]
n
)
=
ƒ
(
x
)
×
ƒ
(
y
) et
ƒ
(1)
=
( [1]
m
, [1]
n
)
Déterminons
le noyau de
ƒ
:
Ker(
ƒ
)
=
{
x
|
ƒ
(
x
)
=
( [0]
m
, [0]
n
)}
=
{
x
| [
x
]
m
=
[0]
m
et [
x
]
n
=
[0]
n
}
=
m
n
Or, on sait que :
m
n
=
p
p
=
ppcm(
m, n
)
Donc :
Ker(
ƒ
)
=
p
où ppcm(
m, n
)
On a donc Ker(
ƒ
)
{0} et
ƒ
n'est pas un morphisme injectif.
Nous allons maintenant définir un nouveau morphisme
ƒ
sur
p
qui aura même image que
ƒ
.
Pour cela, il suffit de constater que l'image, par
ƒ
, d'une classe est indépendante du représentant choisi dans
cette classe :
On a :
ƒ
(
x
1
)
=
ƒ
(
x
2
)
ƒ
(
x
1
-
x
2
)
=
( [0]
m
, [0]
n
)
Ce qui signifie que
x
1
-
x
2
est un multiple commun de
m
et
n
donc multiple de
p
=
ppcm(
m, n
).
Donc [
x
1
-
x
2
]
p
=
[0]
p
, c'est-à-dire [
x
1
]
p
=
[
x
2
]
p
.
Nous pouvons donc légitimement définir l'application :
ƒ
:
p
m
×
n
[
x
]
p
( [
x
]
m
, [
x
]
n
)
On a donc, plus simplement :
ƒ
([
x
]
p
)
=
ƒ
(
x
).
Il est clair que
ƒ
est un morphisme de groupes additifs
:
2200
([
x
]
p
, [
y
]
p
)
(
29
p
2
:
ƒ
([
x
]
p
+
[
y
]
p
)
=
ƒ
([
x
+
y
]
p
)
=
ƒ
(
x
+
y
)
=
ƒ
(
x
)
+
ƒ
(
y
)
=
ƒ
([
x
]
p
)
+
ƒ
([
y
]
p
)
Théorème Chinois et conséquences
Page
2
G. COSTANTINI
(Puisque
ƒ
est un morphisme)
C'est même un isomorphisme d'anneaux car
ƒ
l'est.
Montrons que
ƒ
est un morphisme injectif
:
Ker(
ƒ
)
=
{
[
x
]
p
p
|
ƒ
([
x
]
p
)
=
0}
=
{
[
x
]
p
p
|
ƒ
(
x
)
=
0}
=
{
[
x
]
p
p
|
x
Ker(
ƒ
)}
Ker(
ƒ
)
=
{
[
x
]
p
p
|
x
p
}
=
{[0]
p
}
Remarque : on dit que l'on a factorisé
ƒ
:
ƒ
=
ƒ
o
s
s
est la surjection canonique de
dans
p
.
Bilan :
Pour tous
m
et
n
entiers naturels non nuls, il existe un morphisme injectif
ƒ
entre
ppcm(
, )
m n
et
m
×
n
qui, à toute classe [
x
]
ppcm(
m, n
)
fait correspondre le couple ( [
x
]
m
, [
x
]
n
).
2.
Un cas particulier important
Supposons maintenant que
m
et
n
soient premiers entre eux. Dans ce cas : ppcm(
m, n
)
=
mn
.
Dans ce cas, comme card
(
29
mn
=
mn
=
card
(
29
m
n
×
, le morphisme
ƒ
est également
bijectif
.
C'est le
théorème Chinois :
Si
m
n
=
1, alors
mn
2245
m
×
n
Exemple :
6
2
3
2245
×
Intéressons-nous à une forme réciproque de ce théorème, en ce sens.
Supposons que l'application
ƒ
définie ci-dessus entre
mn
et
m
×
n
soit un isomorphisme.
Peut-on affirmer que
m
n
=
1 ?
Pour répondre affirmativement à cette question, nous avons besoin du lemme suivant :
Lemme
L'ordre d'un élément dans un groupe est invariant par isomorphisme :
Soient
G
et
G'
deux groupes d'ordre fini
n
*
. Soit
ϕ
:
G
G'
un isomorphisme.
Soit
x
G
d'ordre
k
. Alors
ϕ
(
x
) est d'ordre
k
dans
G'
.
Preuve :
Notons
k'
l'ordre de
ϕ
(
x
).
Adoptons des notations additives. Si
x
=
0
G
alors
x
est d'ordre 1. Comme
ϕ
(0
G
)
=
0
G'
,
ϕ
(
x
) est aussi d'ordre 1.
Supposons désormais
x
0. On a :
x
d'ordre
k
(
kx
=
0
G
et (
px
=
0
G
k
|
p
))
Comme
ϕ
est un morphisme, on a donc : 0
G'
=
ϕ
(0
G
)
=
ϕ
(
kx
)
=
k
ϕ
(
x
)
Donc
k'
divise
k
.
Mais comme
ϕ
est bijective, en utilisant
ϕ
-
1
, on a :
0
G
=
ϕ
-
1
(0
G'
)
=
ϕ
-
1
(
k'
ϕ
(
x
))
=
k'
ϕ
-
1
(
ϕ
(
x
))
=
k'x
Théorème Chinois et conséquences
Page
3
G. COSTANTINI
Donc
k
divise
k'
.
D'où
k'
=
k
et le lemme est prouvé.
Revenons maintenant à l'étude de la "réciproque" du théorème Chinois :
L'ordre de [1]
mn
est
mn
dans
mn
. Donc, d'après le lemme, comme on a supposé
ϕ
isomorphisme
(d'anneaux), son image
ƒ
([1]
mn
)
=
( [1]
m
, [1]
n
) est aussi d'ordre
mn
.
Supposons un instant que
d
=
m
n
1. Alors, il existe des entiers
m'
,
n'
tels que :
m
=
m'd
,
n
=
n'd
et
m'
n'
=
1
On aurait alors :
m'n'd
( [1]
m
, [1]
n
)
=
(
mn'
[1]
m
,
m'n
[1]
n
)
=
( [0]
m
, [0]
n
)
Donc, ( [1]
m
, [1]
n
) serait d'ordre au plus
m'n'd
<
mn
, ce qui est absurde.
Donc
m
n
=
1.
Remarque : on peut faire un raisonnement beaucoup plus rapide :
Si
ƒ
est un isomorphisme, c'est que ppcm(
m,n
)
=
mn
donc
m
n
=
1.
3.
Application 1 : systèmes de congruences
Des entiers
a
,
b
,
m
et
n
étant donnés, on considère le système suivant :
(
S
)
]
[
]
[
n
b
x
m
a
x
Deux questions se posent :
1)
À quelle condition, nécessaire et suffisante, le système admet des solutions.
2)
Comment déterminer ces solutions.
Il y a un cas royal, c'est
m
n
=
1. Dans ce cas, la surjectivité du morphisme
ƒ
assure l'existence de
solutions (qui seront, de plus, de la forme
x
=
x
0
+
kmn
).
Voici un procédé algorithmique permettant de les trouver :
D'après le théorème de Bézout :
5
(
u
,
v
)
2
tels que :
mu
+
nv
=
1
Posons
x
0
=
bmu
+
anv
.
On a clairement :
x
0
anv
[
m
]
Or,
anv
=
a
-
amu
, donc :
x
0
a
[
m
]
On montre, de même, que :
x
0
b
[
n
]
On a donc une solution particulière
x
0
.
Soit
x
une solution quelconque. On a alors :
-
-
]
[
0
]
[
0
0
0
n
x
x
m
x
x
Donc
m
| (
x
-
x
0
) et
n
| (
x
-
x
0
)
Or,
m
n
=
1, donc
mn
| (
x
-
x
0
).
D'où :
x
=
x
0
+
kmn
.
(
a
|
c
et
b
|
c
et
a
b
=
1)
ab
|
c
Preuve : on a
c
=
aa'
et
b
|
aa'
.
Or,
a
b
=
1 donc
b
|
a'
donc
ab
|
c
.
Théorème Chinois et conséquences
Page
4
G. COSTANTINI
Mais peut-il exister des solutions même si
m
n
1 ? Quel procédé pour les trouver ?
Remarquons que le système (
S
) est équivalent à :
5
(
k
,
h
)
2
tels que
+
=
+
=
hn
b
x
km
a
x
5
(
k
,
h
)
2
tels que
+
=
+
+
=
hn
b
km
a
km
a
x
5
(
k
,
h
)
2
tels que
-
=
-
+
=
a
b
hn
km
km
a
x
Or, l'équation d'inconnues
h
et
k
:
km
-
hn
=
b
-
a
est une équation de Diophante. On sait qu'une telle
équation admet des solutions si et seulement si
m
n
divise
b
-
a
.
On énonce donc :
Le système
]
[
]
[
n
b
x
m
a
x
admet des solutions si et seulement si
m
n
divise
b
-
a
.
(C'est évidement le cas lorsque
m
n
=
1)
En résolvant l'équation de Diophante, on trouve
h
(ou
k
) et donc
x
.
Application 2 : indicatrice d'Euler
On suppose que
m
n
=
1. Reprenons notre isomorphisme :
ƒ
:
mn
m
×
n
[
x
]
mn
( [
x
]
m
, [
x
]
n
)
Soit [
x
]
mn
(
29
mn
. Notons [
y
]
mn
son inverse.
On a :
( [1]
m
, [1]
n
)
=
ƒ
([1]
mn
)
=
ƒ
([
x
]
mn
[
y
]
mn
)
=
ƒ
([
x
]
mn
)
ƒ
([
y
]
mn
)
Donc
ƒ
([
x
]
mn
) est inversible dans
(
29
(
29
m
n
×
.
Réciproquement, si
ƒ
([
x
]
mn
) est inversible dans
(
29
(
29
m
n
×
alors
x
m
=
1 et
x
n
=
1
Donc
x
mn
=
1 et donc [
x
]
mn
(
29
mn
.
On a donc un isomorphisme (induit par
ƒ
) entre
(
29
mn
et
(
29
(
29
m
n
×
.
On en déduit :
si
m
n
=
1 alors
ϕ
(
mn
)
=
ϕ
(
m
)
ϕ
(
n
)
Application : comme
ϕ
(
p
)
=
p
-
1 et
ϕ
(
p
r
)
=
p
r
-
p
r
-
1
pour tout premier
p
, si
n
=
i
r
i
i
p
alors :
ϕ
(
n
)
=
n
-
i
i
p
1
1
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.