Modulos/ thèorème d'Euclide

Roulanne · 24-09-2017 14:49:46

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

yoshi · 24-09-2017 17:39:57

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 ?

@+

Roulanne · 24-09-2017 19:30:43

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

yoshi · 24-09-2017 21:23:55

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 ?

@+

Roulanne · 25-09-2017 07:33:57

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

Roulanne · 25-09-2017 08:00:55

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

hgaruo1951 · 25-09-2017 08:18:15

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 08:40:54)

hgaruo1951 · 25-09-2017 09:11:45

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 09:40:25)

Forum de mathématiques - Bibm@th.net

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

Modulos/ thèorème d'Euclide

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Pied de page des forums