Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Ensemble et application Partie II
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Calcul d'inverse modulo p
Posté par snowyleb
Bonjour a tous
je ne comprends pas une notion dans un exercice fait en TD
on cherche l'inverse de 5 modulo 23
la formule du cours nous dit que cet inverse est 521
jusque ici tout va bien
vient alors le calcul de 521
on utilise la "méthode égyptienne" des carrés
5
5 mod 23 1 mod 23
5225 mod 23 1 mod 23
54244 mod 23
584216 mod 23-7 mod 23
516(-7)2493 mod 23
on s'arrete ici car le suivant est 532 et 32 est plus grand que 21
jusque la tout va bien
mais le prof a écrit :
on a donc 21 = 16 + 4 + 1
donc 521 5[sup ]16[/sup] x 54 x 513 x 4 x 5 60 mod 23 14 mod 23
donc l'inverse de 5 est 14 mod 23
je ne comprends pas pourquoi 21 = 16 + 4 + 1 et non pas autre chose?
help svp
encore une fois, de quelle autre manière voudrais-tu l'écrire ? ça devrait répondre à ta question ....
d'accord donc faut que je pioche dans ma liste d'exposants donc entre 1,2,4,8,16,...
mon nombre sera t-il toujours découpé en 3 parties?
salut
vu ce qui est écrit en dessous de la phrase "on utilise la méthode égyptienne des carrés" il est normal que tu ne comprennes pas puisque les trois premières sont fausses ....
écrire mon nombre en base 2?
21 en base 2 s'écrit 10101 je ne vois pas le lien
en quoi les 3 premières sont fausses??
10101 en base deux signifie très exactement .... c'est exactement ce qu'on a fait, relis ma toute première intervention !
aaah ok donc a chaque fois je devrai écrire mon nombre en base 2 et le retranscrire en puissances de 2
merci beaucoup!
ah oui la 2eme c'est une faute de frappe c'est congru a 2
Bonsoir.
>> snowyleb
Quel est l'exercice?
Trouver l'inverse de 5 modulo 23 ou l'inverse de 5^{21} modulo 23.
salut
à mon avis tu ne comprends pas trop ce que tu fais
certes le petit théorème de Fermat te dit que 521 est l'inverse de 5 mod 23
donc toute la suite consiste à trouver la classe de congruence de 521
quelle est alors l'idée ::
calculer les puissances 2k de 5 car
5 = 5
52 = 2
54 = 22 =
....
donc tout revient à écrire 21 en base 2 et ensuite appliquer la propriétés :::
a = b mod 23
c = d mod 23
==> ac = bd mod 23
mais bon comme dit dans l'autre topic c'est sans intérêt ....
puisque le théorème de Bézout suffit amplement à résoudre le pb en 2 lignes ....
certes ton procédé est mécanique et ne consiste qu'à calculer et donne la réponse de façon algorithmique :: on applique une recette sans aucune difficulté
le pb de Bézout c'est qu'il faut chercher (et trouver) puisqu'on veut trouver deux nombres a et b tels que 5a + 23b = 1 et alors a est l'inverse de 5
maintenant l'algorithme d'Euclide fournit aussi une réponse mécanique et permet de donner a
chercher les nombres a et b tels que 5a + 23b = 1 c'est
chercher les nombres a et b tels que 5(a + 4b) + 3b = 1 c'est
on pourrait continuer mais là on voit que
a + 4b = 2
b = -3
convient
soit encore
a = 14
b = -3
et donc c'est fini ....
Bonsoir.
@ snowyleb
Le même problème d'énoncé que celui de l'autre topic.
Vu la rédaction, la 1ère partie va donner l'inverse de 5 modulo 23, cet inverse est modulo
. Pourquoi en déterminer un autre et aller jusqu'à
. Ne serait pas l'inverse? On cherche l'inverse de 5 modulo 23 pour trouver l'inverse de
modulo 23.
si je comprends bien, c'est leur prof qui les fait travailler sur cette méthode :
l'inverse de 5 modulo 23 peut s'écrire en utilisant le petit théorème de Fermat, et ensuite méthode dite égyptienne pour calculer
sans trop de multiplications, en ne calculant de proche en proche que des carrés, et en décomposant 21 en base 2.
toutes les égalités sont modulo 23 :
donc ou
(et non, 14 n'est pas congru à -7 modulo 23...)
c'est un peu bourrin, mais ça marche, avec finalement pas tant d'opérations que ça, moins que les 23 multiplications 5 fois ... = ? permettant de tomber à coup sûr sur modulo 23.....