C'est ni l'un ni l'autres...
commence par simplifier tout ça !
. Maintenant, on vois que . je te laisse conclure...

En même temps, je n'ai pas vérifié que , c'est peut-être le cas... mais trop long

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

Bonjour,

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

Dans l'ordre :
le petit théorème de Fermat dit que sous certaines conditions 655 ¹⁶ 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

Grosse erreur:

C'est qui a raison.
commence par simplifier tout ça !
. Maintenant, on vois que . je te laisse conclure...

En même temps, je n'ai pas vérifié c'est peut-être le cas... mais trop long

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

décidément:

C'est le texte en ligne qui a raison.
commence par simplifier tout ça !
. Maintenant, on vois que . je te laisse conclure...

si 665¹⁶ 1 mod 17
c'est que 655 655¹⁵ 1 mod 17 et donc que l'inverse de 655 est bien 655¹⁵

donc la méthode de snowyleb de calculer 655¹⁵ 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 !!

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 ?

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 ....

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 355¹⁵ = 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.

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

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...

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

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

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 655¹⁶ 1 mod 17 pour en déduire, toi, personnellement ce lien entre Fermat et les inverses qui est
655655¹⁵ 1 mod 17, et donc 655¹⁵ 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)

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

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é"

surtout sans calculatrice

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
    , .....,  , ...  ,   
,    ,   donc   ,