Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 24-09-2017 12:49:46

Roulanne
Membre
Inscription : 24-09-2017
Messages : 4

Modulos/ thèorème d'Euclide

Bonjour,

j'ai une question au sujet de l'application du théorème des restes chinois et  des calculs d'inverse

En appliquant ce principe à un système d'équations modulaires, on cherche avec le théorème d'Euclide à trouver les coefficients qui permettent de calculer la solution unique.
Exemple plus concret de ce qui me pose problème lors d'une étape de calcul :
Je cherche le coefficient multiplicateur de 77 tel que k*77 soit congru à 1 mod 13; je me retrouve confrontée à un problème de signe. Pour que 1*77 soit congru à 1 mod 13 il faudrait l'égalité suivante : 1=77-6*13. or j'obtiens 1=-77+6*13

Pourtant je décompose bien 77. 77=5*13+12   13= 1*12+1   d'où 1=13-1*12 = 13-(77-5*13)

Je ne vois pas où çà pêche.

Si quelqu'un peut m'apporter une réponse
Merci beaucoup d'avance

Anne

Hors ligne

#2 24-09-2017 15:39:57

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Modulos/ thèorème d'Euclide

Bonjour,

Une idée comme ça :
1=13-(77-5*13) =13-77+5*13 =-77+6*13
C'est bien ce que tu veux, non ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 24-09-2017 17:30:43

Roulanne
Membre
Inscription : 24-09-2017
Messages : 4

Re : Modulos/ thèorème d'Euclide

j'ai dû mal exposer mon problème.
je dois trouver k tel que k77 soit congru à 1 modulo 13 autrement dit k77= q*13+1
pour ce faire je décompose 77 comme je l'ai déja expliqué. Et j'obtiens l' expression suivante -77= 6*13-1 ce qui me gêne car cela ne satisfait pas les conditions énoncés soit q*13+1.

Pour ceux qui connaissent,l'exercice que je dois résoudre est le suivant
trouver x (x compris entre 0 et 1000) tel que
x = 5 mod7
x = 9 mod11
x=11 mod13

la solution unique est x = (5*k1*(11*13) + 9*(7*13)*k2+11*(7*11)*k3 ) mod (7*11*13) d'après le théorème des restes chinois.

On détermine les coefficients k de la manière expliquée plus haut.

De source sûre, je sais que la solution x = 999; or je n'arrive pas à  la retrouver.
je trouve k1 = -2
k2 = 4
k3=-1

d'où x = (-1430+3276-77)mod 1001
x = 1769 mod 1001

je ne vois pas comment obtenir 999.


Anne

Hors ligne

#4 24-09-2017 19:23:55

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Modulos/ thèorème d'Euclide

Bonsoir,

Il y avait un problème de changement de signes, c'est pourquoi je les ai mis en rouge.
J'avais réalisé un petit programme en Python qui le faisait.
Je viens de l'adapter à la nouvelle mouture de Python, voilà ce qui sort :


********************************************************************************
*        Résolution d'équations par le théorème des restes chinois             *
*                                  Voir :                                      *
* http://www.bibmath.net/dico/index.php3?action=affiche&quoi=./c/chinois.html  *
********************************************************************************


De combien d'équations disposez-vous ? 3
Entrer le reste  no 1 : 5
Entrer le modulo no 1 : 7
----------------------
Entrer le reste  no 2 : 9
Entrer le modulo no 2 : 11
----------------------
Entrer le reste  no 3 : 11
Entrer le modulo no 3 : 13
----------------------

                           Votre problème :
          Trouver le plus petit nombre entier naturel x tel que
            x = 5   (modulo 7)
            x = 9   (modulo 11)
            x = 11   (modulo 13)


                           **************
                           * Résolution *
                           **************

Le produit des modulos est : 1001
Produit_partiel n° 1 : 1001/7 =  143     L'inverse, modulo 7, de 143 est :  5
Produit_partiel n° 2 : 1001/11 =  91     L'inverse, modulo 11, de 91 est :  4
Produit_partiel n° 3 : 1001/13 =  77     L'inverse, modulo 13, de 77 est :  12

                         On a alors  :
5*143*5+9*91*4+11*77*12= 17015

                         Et enfin :
               17015 modulo 1001 = 999

Adapté de http://www.bibmath.net/dico/index.php?a … inois.html

Est-ce que ça te va ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 25-09-2017 05:33:57

Roulanne
Membre
Inscription : 24-09-2017
Messages : 4

Re : Modulos/ thèorème d'Euclide

Oui c'est çà.
Merci beaucoup.
Il me reste à comprendre comment obtenir facilement les bons inverses, sans programme ni calculatrice.

Hors ligne

#6 25-09-2017 06:00:55

Roulanne
Membre
Inscription : 24-09-2017
Messages : 4

Re : Modulos/ thèorème d'Euclide

C'est bon , cette fois j'ai compris.
Avec le théorème d'Euclide les coefficients peuvent être multiples.
pour solutionner mon problème de signe je peux additionner 77*13 à l'un des membres et le soustraire à l'autre. ce qui me permet d'obtenir les bons coefficients congru à 1.

1=-77+6*13
1=-77+13*77+6*13-77*13
1=12*77-71*13

inverse de 77 modulo 13 = 12

Merci

Hors ligne

#7 25-09-2017 06:18:15

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 40

Re : Modulos/ thèorème d'Euclide

Bonjour ,

Résoudre ce type d'exercice il suffit d'appliquer le schéma d'OURAGH mon schéma comme suite

13.....11.......2.......7....**......143.....7......3......1
........-1......-5.......0....**........0.....-20....-2.......
.......246....-205....41...**.......-2......41....-2.....1


et de ce tableau  on relève les nombres colorés 246 , -205   et -2.
Ainsi donc la solution est

x=partie décimale de [ (246*11/13)-(205*9)/11-(2*5/7)] mod (13*11*7)= 999 mod 1001 .


--------------------------------------------------------------------------------------------------

[EDIT]@Yoshi Modérateur
Théorème de Pythagore,
Théorème de Thalès,
Algorithme d'Euclide,
sont des appellations contrôlées...
Schéma d'Ouragh, non ! Puisque c'est le tien...
Il serait plus correct de le dire, tu ne crois pas ?...
D'autre part, tu es sur un forum d'entraide et donc, tu es prié de ne faire allusion qu'à des méthodes non exotiques, qui ont l'air de fonctionner, mais que tu n'as jamais justifiées théoriquement
Tu n'es pas ici non plus pour faire de l'auto promotion.

Si tu veux être reconnu par les manuels scolaires, commence par être reconnu par la communauté des mathématiciens reconnus.
Pourquoi n'exposerais-tu pas ton procédé à Cédric Villani, par exemple, qui m'a l'air d'un mathématicien tout à fait ouvert et simple ?
Je ne voudrais pas avoir à te le redire.
Pour tout débat éventuel, ne pollue pas le forum d'entraide, ouvre une nouvelle discussion dans le café mathématique
Merci

Dernière modification par yoshi (25-09-2017 06:40:54)

Hors ligne

#8 25-09-2017 07:11:45

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 40

Re : Modulos/ thèorème d'Euclide

Re, emple

(.................................)
--------------------------------------------------------
[EDIT]@yoshi modérateur
Message supprimé
3e et dernier avertissement.
Ne mêle plus ton schéma au forum d'entraide.
Sais-tu lire ?
La prochaine fois, tu seras banni !

Dernière modification par yoshi (25-09-2017 07:40:25)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de cette opération? 3+7=

Pied de page des forums