Inscription / Connexion Nouveau Sujet
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
carpediem
re : 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
carpediem
re : 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
matheux14
re : 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
carpediem
re : 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
matheux14
re : 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
carpediem
re : 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
matheux14
re : Théorème des restes chinois 27-11-21 à 12:36

Oui donc je peux conclure avec cette démo ?

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

voir à 19h34 ...

Posté par
matheux14
re : 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
carpediem
re : 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 ...



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 1488 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 !