Théorème des restes chinois

kvf300
kvf300
dans Arithmétique
Bonjour

Je suis en train d'essayer de démontrer le théorème des restes chinois et je voulais savoir si ceci vous semble correct :

$\textbf{Théorème des restes chinois}$
Soient $m$ et $n$ deux entiers premiers entre eux. Le système de congruence : \begin{center}
$\left\{
\begin{array}{l}
x\equiv a[m]\\
x\equiv b[n]
\end{array}
\right.$
\end{center} admet une unique solution $x$ modulo $mn$.

Démonstration:
$m$ et $n$ sont premiers entre eux donc il existe $u$ et $v$ deux entiers relatifs tel que $um+vn=1$.
On a donc:
$aum+avn=a$, c'est à dire $anv\equiv a[m]$.
$bum+bvn=b$, c'est à dire $bum\equiv b[n]$.
Donc $bum+avn\equiv b [n]$ et $bum+avn\equiv a [m]$. Donc $x=bum+avn$ est solution du système.
De plus, $\forall k\in \mathbb{Z}, x+kmn\equiv a[n]$ et $x+kmn\equiv n[m]$.
Donc toutes les solutions s'écrivent sous la forme $x+kmn, k\in \mathbb{Z}$.
Unicité:
Soient $x$ et $y$ deux solutions du système : $$ \begin{cases}
x\equiv a[m]\\
x\equiv b[n]
\end{cases}\quad\text{ et }\qquad \begin{cases}
y\equiv a[m]\\
y\equiv b[n]
\end{cases} $$ Donc par soustraction : \begin{center}
$\left\{
\begin{array}{l}
y-x\equiv 0[m]\\
y-x\equiv 0[n]
\end{array}
\right.$
\end{center} Donc $m|(y-x)$ et $n|(y-x)$ donc $mn|(y-x)$ donc il existe $k\in \mathbb{Z}$ tel que $y-x=kmn$ ie $y=x+kmn$. D'où l'unicité.

Réponses

  • chris93
    chris93
    A la fin de l'étape "Existence", tu déduis que toutes les solutions sont de la forme $x+kmn$...Il faudrait mieux dire que tous les éléments de la forme $x+kmn$ sont solutions. A priori, tu n'as pas encore démontré que toutes les solutions sont de cette forme. Parcontre, quand tu prouves l'unicité, à ce moment-là, tu peux écrire que toutes les solutions sont de la forme $x+kmn$ où $x$ est la solution particulière que tu as exhibée.
  • jhildenbrand
    jhildenbrand
    Bonjour,

    Vous pouvez aussi exhiber un isomorphisme entre (Z/mnZ, +) et (Z/mZ, +)x(Z/nZ, +).

    Le problème se pose alors de façon plus algébrique, il suffit de montrer l'injectivité et l'égalité des cardinaux, même si je reconnais qu'on revient au bout du compte aux même idées.
  • kvf300
    kvf300
    Oui exacte merci.

    Je prépare l'oral du CAPES donc je vais laisser de côté le point de vue avec l'isomorphisme ;-)
  • Zo!
    Zo!
    Extrait du programme de l'oral du CAPES, à l'intérieur de 2.I.3.”Structure des ensembles de nombres” :
    "Congruences; anneaux $\Z/n\Z$ , caractérisation des éléments inversibles."
    Je pense donc qu'on peut attendre d'un candidat qu'il sache formuler le théorème des restes chinois en termes d'anneaux $\Z:n\Z$. Tu devrais peut-être t'y intéresser un peu.
  • chris93
    chris93
    Comme l'a dit Zo!, il vaudrait mieux t'y intéresser car il y a des chances que le jury te pose des questions en lien avec les différentes "formes" du théroème chinois.
    L'une d'elle prend la forme que tu as donnée, une autre est que, si $n\wedge m=1$, alors $\mathbb{Z}/mn\mathbb{Z} \simeq \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$, la réciproque étant vraie. Pour démontrer ceci, tu peux étudier l'application $\varphi : \mathbb{Z}/mn\mathbb{Z} \mapsto \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$ qui à $[x]_{mn}$ associe le couple $([x]_n,[x]_m)$ et montrer que c'est un isomorphisme.
    Le jury pourrait te demander de faire le rapport entre ces deux versions, ou de te demander une généralisation...ou de résoudre un système de congruences à 3 équations. Et pourquoi pas te demander ce qu'il peut se passer si $m$ et $n$ ne sont pas premiers...

    Une remarque : dans le cas d'un système de congruence $x_i\equiv a_i \mod{n_i}$ pour $1\leq i\leq r$, une solution particulière du système est donnée par $x=\displaystyle \sum_{i=1}^r \frac{n}{n_i}b_ia_i$ où $n=n_1\dots n_r$ et les $b_i$ tels que $\frac{n}{n_i}b_i\equiv 1 \mod{n_i}$.
  • christophe c
    christophe c
    je vais laisser de côté le point de vue avec l'isomorphisme

    je rejoins les deux conseils précédents, en précisant un soupçon: je ne pense pas que le jury te malmènerait, là n'est pas la question.

    Par contre, il y a un point qui peut conduire à des contre-sens ou poser des problèmes aux gens, surtout en des temps où l'abstrait est, pour cause de préjugés idiots, vilipendé. A force passer aux quotients dans tous les sens, on s'y retrouve plus si on oublie ce qu'est mathématiquement le quotient. Et c'est de ce point de vue qu'un jury de concours peut te chercher des pouls dans la tête car si tu fais comme beaucoup, à savoir si "tu te construis une représentation personnelle" (mot trop à la mode) du quotient, tu oublies ce qu'il est (un ensemble d'ensembles muni d'opérations obtenue naturellement) et tu risques de gérer les choses à l'intuition au plus grand bonheur de gens qui attendront que tu dises des conneries ( " :D " penseront-ils)

    d'où l'utilité du th chinois sous forme "isomorphique" parce que la version que tu as donnée est "concrête" et en quelques sortes "trop plaisante". Par ailleurs, la version isomorphique te permet de'oublier $\Z$ et de parler d'anneaux commutatifs quelconques donc de manifester que "tu comprends" les ingrédients d'une de ses preuves
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • diego
    diego
    Zo! écrivait:
    > 
    Extrait du programme de l'oral du CAPES, à
> l'intérieur de 2.I.3.”Structure des ensembles de
> nombres” :
> "Congruences; anneaux $\Z/n\Z$ , caractérisation
> des éléments inversibles."



    Bonjour,

    As tu un lien vers ce document?
  • christophe c
    christophe c
    Bon si tu veux (comme je galère calculatoirement à chaque fois sur ce genre de chose), je te propose une preuve alternative à la tienne, comme ça t'auras pas à chercher:

    on est dans un anneau commutatif unitaire quelconque $A$. On a deux idéaux "premiers entre eux" ce qui signfie que $1\in I+J$.

    Dans ce cas ta version concrête dit que pour tous $a,b$ il existe $x$ tel que $x-a\in I$ et $x-b\in J$ et que si $y-a\in I$ et $y-b\in J$ alors $x-y\in IJ$.

    C'est exactement dire que l'ensemble $L$ des couples $((u_1,u_2),v)\in (A/I\times A/J) \times A/(IJ)$ tels que $\exists (x,y,z)\in A^3$ tels que $x-z\in I$ et $y-z\in J$ et $(x,y,z)\in u_1\times u_2\times v$ est une bijection allant de $(A/I\times A/J)$ dans $ A/(IJ)$

    Le fait qu'elle soit un isomorphisme (et donc ajouter le mot "morphisme" à "bijection") n'est pas "vraiment" contenu dans ta version concrête, même si ça parait évident.

    En plus, c'est un calcul, ce n'est "si" évident, dans aucun des items:
    0) est-ce que $L$ est bien "une fonction"?
    1) par exemple le fait que $x-y\in I$ et $x-y\in J$ => $x-y\in IJ$ utilise vraiment astucieusement le fait que $1\in I+J$ à travers le calcul $u+v=1$, $u\in I$, $v\in J$, $t\in I\cap J$ => $t=tu+tv \in IJ$
    2) pour la surjectivité: $(ub+va) -a = ub+va -(ua+va) = u(b-a)\in I$, etc
    3) mais pour le côté "morphique", faut vraiment refaire plein de vérifs soigneuses et illustrer si on manie bien ou mal la définition de idéal, quotient par, etc (est-ce que $L$ est bien linéaire, multiplicative, etc)

    Ca te donne une idée des "pièges" possibles. Je ne crois pas que le cas de $\Z$ soit plus simple que le cas général.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • Zo!
    Zo!
    Recherche "programme du CAPES de mathématiques" avec ton outil de recherche préféré, et tu trouveras. C'est ce que j'ai fait, et je n'ai pas gardé le lien.
  • aléa
    aléa
    @Zo: je crois que tu penses à feu le programme du capes

    car

    Épreuves écrites : le programme est constitué de la réunion des programmes de mathématiques du collège, du lycée et des classes post-baccalauréat du lycée (STS et CPGE) en vigueur au titre de l’année scolaire 2011–2012 et de ceux en vigueur au titre de l’année scolaire 2010–2011.

    Épreuves orales : le programme est constitué de la réunion des programmes de mathématiques du collège, du lycée et des sections de techniciens supérieurs en vigueur au titre de l’année scolaire 2011–2012 et de ceux en vigueur au titre de l’année scolaire 2010–2011.

    Le voilà
  • Zo!
    Zo!
    mea culpa, c'est bien un vieux programme sur lequel ma recherche m'a emmené. Reste à voir si on parles de Z/nZ en STS, mais j'en doute.
  • christophe c
    christophe c
    bin d'un autre côté c'est kvf300 lui-même qui a commencé à en parler et si au CAPES, on préfère écrire des trucs compliqués comme
    $x+kmn\equiv n[m]$, ou $x+kn,n \in \Z$ (avec plein de latex high tech) plutôt que $x\in J$, $x\in I+J$, $x\in IJ$, etc, c'est un peu dommage, en plus pour devenir prof de maths, je vois pas trop l'utilité de rester sur de l'hyperconcret dans le concours, puisque les profs devront (le jour où on réparera) essayer d'élever un peu leurs élèves, mais bon..
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • diego
    diego
    On peut toujours avoir la nostalgie de la terminale C.... 
    le plan, clairement structuré, se situe à un niveau différent de celui de l’exposé des épreuves antérieures ;



    Ce qui est demandé est de maîtriser ce qui est enseigné aujourd'hui et pour l'arithmétique c'est assez simple, tout se trouve en TS spé maths (ne pas négliger le collège cependant, beaucoup de candidats auraient sans doute du mal à justifier l'algorithme de la "potence" pour la division euclidienne). Le programme ayant peu évolué, un solide bouquin style Terracher fait l'affaire; En revanche pour l’entretien (quand même 1/2h) il vaut mieux en "avoir sous le pied" et maîtriser "le coté morphique"... Ce n'est évidement qu'un avis et les conseilleurs etc...
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 25

AmadouJLTLirone93guiguichemanuraoul.S +19 Invités