Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 Re : Entraide (collège-lycée) » Modulos/ thèorème d'Euclide » 25-09-2017 07: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
#2 Re : Entraide (collège-lycée) » Modulos/ thèorème d'Euclide » 25-09-2017 06:33:57
Oui c'est çà.
Merci beaucoup.
Il me reste à comprendre comment obtenir facilement les bons inverses, sans programme ni calculatrice.
#3 Re : Entraide (collège-lycée) » Modulos/ thèorème d'Euclide » 24-09-2017 18: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
#4 Entraide (collège-lycée) » Modulos/ thèorème d'Euclide » 24-09-2017 13:49:46
- Roulanne
- Réponses : 7
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
Pages : 1