Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Prepa (autre)
Partager :

Théorème des restes chinois

Posté par
matheux14 25-11-21 à 00:06

Bonsoir,

Merci d'avance.

Soient N1 ; N2  ; ... ; Nk des entiers strictement positifs et premiers entre eux.
a1 ; a2 ; ... ; ak des entiers quelconques.

Alors le système \begin{cases} x \equiv a_1 [N_1] \\ x \equiv a_2 [N_2]\\ \dots  \\ x \equiv a_k [N_k]  \end{cases} \iff x \equiv a [N_1 N_2 \dots N_k]

Démonstration

Alors on prouve le théorème pour k = 2 et ensuite on généralise par récurrence.

On veut résoudre le système : \begin{cases} x \equiv a_1 [N_1]~ (1) \\ x \equiv a_2 [N_2]~(2) \end{cases}

Soit u \in \Z

D'après (1)~: ~x \equiv a_1 +u N_1

Alors (2) ~: ~a_1 +u N_1 \equiv  a_2 [N_2]

Donc u \equiv (a_2-a_1) N'_1 [N_2] avec N'_1 \equiv N^{-1} _1 [N_2] j'ai pas compris.. pour quelle condition ce N'1 existe ?

On pose a= a_1 +(a_2 -a_1) N'_1 N1

Donc x \equiv a [N_1 N_2]

Les deux dernières lignes non plus..

Posté par
carpediemre : Théorème des restes chinois 25-11-21 à 09:37

salut

N'1 existe parce que N1 et N2 sont premiers entre eux ...

donc théorème de Bézout ...

Posté par
carpediemre : Théorème des restes chinois 25-11-21 à 09:52

avec tous ces indices c'est difficile à lire et pas clair ...

on veut résoudre le système :

x =a [m]
x = b [n]

avec (m, n) = 1

(m, n) = 1 => il existe u et v tels que mu + nv = 1

donc x = mux + nvx

d'uatre x = a + pm = b +qn

donc mu(b + qn) + nv(a + pm) = x <=> x = mub + nva + (uq + vp)mn

donc x = mub + nva |mn]

...

Posté par
matheux14re : Théorème des restes chinois 25-11-21 à 19:25

carpediem @ 25-11-2021 à 09:37

salut

N'1 existe parce que N1 et N2 sont premiers entre eux ...

donc théorème de Bézout ...


Comment çà ?

Si N1 est un entier alors N-11  n'est pas un entier non ?

Posté par
carpediemre : Théorème des restes chinois 25-11-21 à 19:35

ce n'est pas ce qui est dit dans le corrigé ...

si mu + nv = 1 alors mu \equiv 1  [n] \iff u \equiv m^{-1}  [n]

2 est l'inverse de 4 (et réciproquement) modulo 7 car 2 * 4 = 8 = 1 [7]

Posté par
matheux14re : Théorème des restes chinois 26-11-21 à 08:12

Je vois.

Pour la généralisation, est ce que la récurrence est la bonne méthode ?

Posté par
carpediemre : Théorème des restes chinois 26-11-21 à 19:34

on 'a montré pour deux équations :

\left\lbrace\begin{matrix} x\equiv a  [m]\\x \equiv b  [n] \end{matrix}\right. \iff x \equiv c  [mn]

pour un certain entier c ... qui vaut mub + nva ...

ben maintenant tu peux effectivement recommencer avec \left\lbrace\begin{matrix} x\equiv c  [mn]\\x \equiv d  [p] \end{matrix}\right.

puisque les entiers mn et p sont premiers entre eux ...

Posté par
matheux14re : Théorème des restes chinois 27-11-21 à 12:36

Oui donc je peux conclure avec cette démo ?

Posté par
carpediemre : Théorème des restes chinois 27-11-21 à 13:44

voir à 19h34 ...

Posté par
matheux14re : Théorème des restes chinois 28-11-21 à 01:27

\left\lbrace\begin{matrix} x\equiv c  [mn]~ (1)\\x \equiv d  [p] ~(2)\end{matrix}\right

On suppose que mn ^ p = 1

Alors \exists (i ; j) \in \Z² ; i mn + j p =1

i x mn + jx p = x

D'après (1) : x = c +k(mn)

D'après (2) : x=d+k'p

Donc x = i(d+k'p) mn + i(c+k mn)p

x = i d mn+jc p +(k'jk)mnp

x \equiv  i d mn+jc p [mnp]

\left\lbrace\begin{matrix} x\equiv c  [mn]\\x \equiv d  [p] ~\end{matrix}\right \iff x \equiv c' [mnp]

Conclusion : N1 ; N2  ; ... ; Nk des entiers strictement positifs et premiers entre eux.
a1 ; a2 ; ... ; ak des entiers quelconques.

Alors il existe un entier a tel que le système \begin{cases} x \equiv a_1 [N_1] \\ x \equiv a_2 [N_2]\\ \dots  \\ x \equiv a_k [N_k]  \end{cases} \iff x \equiv a [N_1 N_2 \dots N_k].

Posté par
carpediemre : Théorème des restes chinois 28-11-21 à 09:27

il était inutile de refaire la même démonstration que j'avais déjà faite

une fois qu'on la faite pour deux équations :
x = a_1  [n_1]
x = a_2  [n_2]

on "récite" le raisonnement récurrence :

supposons qu'on ait démontré le résultat pour les k premières équations alors ... blablabla

sans oublier l'hypothèse fondamentale qui se résume par le théorème : si a est premier avec b et c alors a est premier avec bc

qu'on généralise aussi par récurrence ...


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !