Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

calcul d'un inverse modulo p

Posté par
snowyleb
30-12-13 à 19:49

bonsoir

je cherche à calculer l'inverse de 655 modulo 17
d'après le théorème de Fermat, mon inverse est 65515

voici mon calcul :
655 9 mod 17
6552 11 mod 17
6554 2 mod 17
6558 4 mod 17
65516 8 mod 17

15 = 1 + 2 + 4 + 8
donc 65515 = 6551 x 6552 x 6554 x 6558
d'où 65515 9 x 11 x 2 x 4 8 mod 17

or un site en ligne me dit que l'inverse est 2

où est mon erreur?

merci d'avance

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 19:59

C'est ni l'un ni l'autres...
commence par simplifier tout ça !
[655]_{\Z/17\Z}=[9]_{\Z/17\Z}. Maintenant, on vois que [9^2]_{\Z/17\Z}=[9]_{\Z/17\Z}[9]_{\Z/17\Z}=[1]_{\Z/17\/}. je te laisse conclure...

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 20:00

En même temps, je n'ai pas vérifié que [655^{15}]_{\Z/17\Z}=[9]_{\Z/17\Z}, c'est peut-être le cas... mais trop long

Posté par
snowyleb
re : calcul d'un inverse modulo p 30-12-13 à 20:02

si 65515 9 mod 17 le site a affirmé
par contre pour l'inverse...
je ne comprends pas votre simplification...

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 20:02

Bonjour,

une simple erreur de calcul
9² = 81 ne fait pas 11 modulo 17
(et ça ne fait pas 1 non plus d'ailleurs )

Posté par
Cherchell
re : calcul d'un inverse modulo p 30-12-13 à 20:03

Dans l'ordre :
le petit théorème de Fermat dit que sous certaines conditions 655 16 1 (17), il ne dit rien sur les inverses.

655 9 (17) or 2 9 = 18 donc 2 655 2 9 (17) donc 2 est bien l'inverse de 655 modulo 17

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 20:03

Grosse erreur:

C'est \red\text{le texte en ligne} qui a raison.
commence par simplifier tout ça !
[655]_{\Z/17\Z}=[9]_{\Z/17\Z}. Maintenant, on vois que [9\cdot {\red 2}]_{\Z/17\Z}=[9]_{\Z/17\Z}[{\red 2}]_{\Z/17\Z}=[1]_{\Z/17\/}. je te laisse conclure...

En même temps, je n'ai pas vérifié \red\text{si} [655^{15}]_{\Z/17\Z}=[{\red 2}]_{\Z/17\Z} c'est peut-être le cas... mais trop long

Posté par
Cherchell
re : calcul d'un inverse modulo p 30-12-13 à 20:04

j'ai oublié de préciser que 18 est congru à 1 modulo 17 !

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 20:05

décidément:

C'est le texte en ligne qui a raison.
commence par simplifier tout ça !
[655]_{\Z/17\Z}=[9]_{\Z/17\Z}. Maintenant, on vois que [9\cdot 2]_{\Z/17\Z}=[9]_{\Z/17\Z}[ 2]_{\Z/17\Z}=[1]_{\Z/17{\red \Z}}. je te laisse conclure...

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 20:12

si 66516 1 mod 17
c'est que 655 65515 1 mod 17 et donc que l'inverse de 655 est bien 65515

donc la méthode de snowyleb de calculer 65515 est bonne, il suffit juste de ne pas se tromper dans les calculs numériques

même s'il y a effectivement des méthodes plus courtes pour obtenir cet inverse !!

Posté par
snowyleb
re : calcul d'un inverse modulo p 30-12-13 à 20:28

merci mathafou je vois où est mon erreur! 81 13 mod 17 et non pas 11
j'ai refait mes calculs mais je ne trouve toujours pas 2 je trouve 4!
j'ai fait le calcul une 3eme fois j'ai trouvé 6 lol

comment avez vous fait pour trouver l'inverse en une ligne ?

Citation :
655  9 (17) or 2  9 = 18 donc 2  655  2  9 (17) donc 2 est bien l'inverse de 655 modulo 17

Posté par
carpediem
re : calcul d'un inverse modulo p 30-12-13 à 20:34

salut

c'est bien un travail de bourrin bon pour les machines qui est fait là ....

655 = 17 * 38 + 9

donc 655 = 9 mod 17

or 9 et 17 sont premiers entre eux donc vérifient le théorème de Bézout-Bachet

et trivialement 2 * 9 -1 * 17 = 1

don l'inverse de 655 est 2 ....

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 20:45

tu dois avoir de trop gros doigts et taper à côté sur les touches de la calculette
655 mod 17 donne 9
9*9 = 81, mod 17 donne 13
13*13 = 169, mod 17 donne 16 (on remarque aussi que du coup c'est -1 mod 17)
16*16 = 256, mod 17 donne 1 (ou (-1)*(-1) = +1 direct)
et donc 35515 = 9*13*16 = 1872, mod 17 donne 2

pour le calcul en une ligne, ça c'est idm et cherchell qui font ça comme ça (ils ont raison en plus)
on "remarque" (parce qu'on est malin et pas une simple machine à faire des calculs) que dès le départ quand on a obtenu le "9", eh bien comme c'est curieux mais le double de ça c'est précisément 18 qui comme par hasard est 17 + 1 (note)
et hop c'est fini.
on rédige en exprimant juste que 2*9 = 18 et en passant pour un magicien

Note : ce qu'exprime carpediem avec son Bézout d'ailleurs
en fait personne (même les machines) ne calcule l'inverse avec le théorème de Fermat : on utilise l'algorithme d'Euclide pour obtenir une relation de Bézout.

Posté par
snowyleb
re : calcul d'un inverse modulo p 30-12-13 à 21:00

je n'ai pas le droit a la calculatrice je calcule tout à la main lol

je ne suis pas maligne en maths, je suis donc condamnée à faire des calculs jusqu'a m'en meler les pinceaux!

merci a tous en tout cas

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 21:26

eh bien sans calculatrice il vaut mieux éviter ces calculs de puissances de 655 et revenir à Bézout et Euclide !!

c'est d'ailleurs immédiat si on considère que l'équation 655x 1 mod 17 est équivallente à 9x 1 mod 17 (une simple division à la main donc)
et finalement à 9x = 1 - 17y (définition même des congruences), et on cherche x bien sûr
et on ne va pas chercher plus loin que ça et on laisse Fermat tranquille.

l'utilisation de Fermat pour calculer un inverse c'est "du folklore"
le faire en exo "pour voir" pourquoi pas, mais pour faire un calcul pratique, (surtout sans calculette) il vaut mieux éviter...

Posté par
snowyleb
re : calcul d'un inverse modulo p 30-12-13 à 22:08

oui j'avoue c'est pas pratique...
que disent Bézout et Euclide au sujet des inverses? histoire que je puisse l'appliquer sur d'autres exos

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 22:39

Je laisse mathafou conclure sur sa méthode, mais le calcul de la division euclidienne de 655\div 17 ne me parait pas sur humain à la main...

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 22:41


rien de plus que ce que dit Fermat : rien du tout.
(rien sur les inverses)

tu as utilisé le théorème de Fermat (qui ne dit rien sur les inverses) qui affirme uniquement 65516 1 mod 17 pour en déduire, toi, personnellement ce lien entre Fermat et les inverses qui est
65565515 1 mod 17, et donc 65515 est l'inverse de 655

Pour Euclide et Bézout c'est pareil.
ils n'en disent rien
Par contre Bézout affirme qu'il existe x et y (dans Z) tels que 655x + 17y = 1

et ça (qu'on peut traduire en 9x + 17y' = 1 par en fait le début de l'algorithme d'Euclide) nous le traduisons par :
si x est une solution, x est l'inverse de 655

et pour calculer x (et y mais on s'en fiche) on utilise l'algorithme d'Euclide (ou quand c'est évident comme ici le simple bon sens et l'observation)

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 22:44

Citation :
Je laisse mathafou conclure sur sa méthode
ce n'est pas ma méthode, c'est celle de snowyleb, juste pour lui montrer que sa méthode, on peut réellement la poursuivre jusqu'au bout.

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 22:46

je t'avoue ne pas avoir tout lu (juste tes écris), mais je te fais confiance
Bonne soirée, et (un peu anticipé) bonne année

Posté par
mathafou Moderateur
re : calcul d'un inverse modulo p 30-12-13 à 22:47

et aussi la conclusion sur cette méthode, snowyleb l'a donnée implicitement lui-même : il n'arrive jamais à obtenir la même valeur en répètant ses calculs preuve à l'évidence que "c'est inutilement trop compliqué"

Posté par
idm
re : calcul d'un inverse modulo p 30-12-13 à 22:48

surtout sans calculatrice

Posté par
delta-B
re : calcul d'un inverse modulo p 30-12-13 à 23:13

Bonsoir.

Dans ce genre de calcul éviter aussi les restes qui dépassent (p/2)+1 et utiliser leur "complément" à p.
Dans le cas présent, tous les calculs peuvent être faits à la main
9=-8,    10=-7, .....,  13=-4, ...  , 16=-1  [17]
655=9=-8,    655^2=64=3\times 17+13=13=-4,   655^4=(-4)^2=16=-1 donc   655^{4m}=(-1)^m,   2^{m} \times 9^{m}=(2 \times 9)^{m}=18^m=1 [17]



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