Exponentiation modulaire

[Anaisdeistres]

Bonjour,

Je cherche à résoudre à la main : = X modulo 35

Merci

[GaBuZoMeu]

Une possibilité : faire l'exponentiation modulo 7 et modulo 5 (c'est vite fait !), puis utiliser les restes chinois (tu as déjà entendu parler de ça) pour avoir l'exponentiation modulo 35.

[mathelot]

bonsoir,
si c'est à la main , il suffit d' utiliser l'algorithme d'exponentiation rapide

on a :
et

l'idée de l'algorithme est de transformer en

on met le résultat R à 1: R=1 (les calculs n'ont pas encore commencé)
on doit calculer , soit le couple

si n est pair, le couple (x;n) devient

si n est impair , le couple (x;n) devient (x;n-1) et le résultat R est multiplié par x.

voilà l'algo:

saisir x et n,
R=1

tant que
si n est pair alors et
sinon (n est impair)


finsi
fin tant que
afficher 'R contient le résultat de l'exponentiation

[mathelot]

j'utilise le résultat de GBZM et j'applique mon algo uniquement au calcul de










d'où

[GaBuZoMeu]

Mouais. L'exponentiation rapide, à la main, c'est nettement plus fatigant que l'approche que je suggère.
Il y a même plus rapide : compter l'ordre du groupe des inversibles modulo 35 (là aussi ça peut se faire avec le théorème chinois) et utiliser le théorème de Lagrange. Ça se fait sans calcul en deux coups de cuillère à pot, mais ça demande un peu plus de matériel.

[mathelot]

ah oui, les inversibles car et

[Anaisdeistres]

Non toujours pas je fais 18^25 modulo 5 et 18^25 modulo 7 mais enfête c'est aussi compliqué pour moi que de faire 18^25 modulo 35 c'est la puissance qui me gêne est-ce que je ne pourrai pas la simplifier svp ?

[GaBuZoMeu]

Hum ... petit théorème de Fermat, ça te dit quelque chose ?

[Anaisdeistres]

Non j'essaye de faire l'exemple que vous avez faite sur 2 lignes mais je n'arrive pas pour le moment

[mathelot]

utilise le petit théorème de Fermat , comme indiqué par GBZM, pour réduire l'exposant 25
de

[Anaisdeistres]

Je viens de lire le théorème de fermat je comprend la décomposition de 18^25 mais je ne vois pas le rapport avec le modulo 35 désormais

[mathelot]

Comme application du petit théorème de Fermat, il vient la congruence suivante:



on écrit la division euclidienne de l'exposant 25 par 6:


en faisant de même avec ] déduis-en le résidu de

[Anaisdeistres]

Non toujours pas il faut que je revois ça

[GaBuZoMeu]

Décomposer 18 ne sert à rien à mon avis. Le 18 n'est pas important dans l'histoire : la seule chose utile est qu'il est premier avec 35. Par contre l'exposant 25 joue un rôle beaucoup plus important.

18 est congru à 3 modulo 5. Ça permet de calculer de tête les premières puissances et de voir que 18^4 est congru à 1 modulo 5. Donc 18^(25) est congru à ? modulo 5.
18 est congru à 4 modulo 7. Ça permet de calculer de tête les premières puissances et de voir que 18^3 est congru à 1 modulo 7. Donc 18^(25) est congru à ? modulo 7.
De ces deux résultats on déduit sans calcul 18^(25) modulo 35.

[mathelot]

bonsoir,
modulo 5:




calculons l'ordre de 3, modulo 5





notons que le petit théorème de Fermat entraine:


pour déterminer le résidu de modulo 5, on effectue la division de l'exposant 25 par 4, il vient:




modulo 7:


déterminons l'ordre de 4 , modulo 7:




notons que le petit théorème de Fermat entraine

on effectue la division de 25 par 3, il vient:

[mathelot]

l'isomorphisme de sur est surjectif.
On va construire un antécédent de (3;4) par ce morphisme.

on détermine deux classes et telles que

et


c'est le même procédé que la recherche des polynômes d'interpolation de Lagrange.

5 et 7 sont deux entiers premiers distincts donc premiers entre eux, écrivons une égalité de Bézout:


modulo 5, on obtient:


d'où
et
d'où



modulo 7, on obtient:


d'où
et
d'où


finalement , un antécédent x de (3;4) par l'isomorphisme vaut:



d'où, l'isomorphisme étant injectif:

[GaBuZoMeu]

Beaucoup d'effort pour rien : puisque et , alors immédiatement .

[tournesol]

2X18=36 donc 2 est l'inverse de 18 modulo 36
2^25=(2^5)^5=32^5=(-3)^5=(-3)^4 X (-3)=11 x (-3) =-33=2 (modulo 35)
comme 18^25 est l'inverse de 2^25 , on a 18^25 = 18 modulo 35

[GaBuZoMeu]

Pratiquement sans calcul : le groupe multiplicatif de a 24 éléments (le nombre d'entiers naturels inférieurs à 35 et premiers avec 35). Le théorème de Lagrange dit alors que pour tout de ce groupe multiplicatif, et donc . Ainsi, pour tout entier premier avec 35, .

[tournesol]

Joli et merci pour la piqure de rappel .