Bonjour,
Existe t il une propriété connue des modulos permettant de calculer aisément :
a^b mod m sachant que : b=b'mod m (avec a, b, m, b' entiers et a << b )
Il me semble qu'on ne peut pas écrire :
a^b mod m = a^b' mod m
mais alors comment procéder ?
Cordialement
Anthony
J'ai oublié de préciser que :
b est divisible par (a-1)^k avec k entier
cela s'appelle de l'arithmétique modulaire,
essaie de jetter un coup d'oeuil à http://fr.wikipedia.org/wiki/Th%C3%A..._%28nombres%29
si cela n'est pas suffisant j'essaierai de détailler
J'ai brièvement pensé à l'indicatrice d'Euler mais j'y ai renoncé sachant que :Envoyé par keb83
cela s'appelle de l'arithmétique modulaire,
essaie de jetter un coup d'oeuil à http://fr.wikipedia.org/wiki/Th%C3%A..._%28nombres%29
si cela n'est pas suffisant j'essaierai de détailler
phi(m) << b et très différent ce qui n'arrangeait rien du tout.
Je vais donner un exemple concret :
****************************
6^(5^262144) = ... mod 53
En essayant de procéder avec l'indicatrice d'Euler on aboutit à :
phi(53) = 52
6^52= 1 mod 53
Ensuite j'essaie de trouver du facteur 52 dans 5^262144 sachant que 52 = 2^2*13 mais la ça bloque !
Cordialement
Anthony
Montrons par récurrence que pour tout n appartenant à IN*, 5^(4^n)=52k+1 avec k appartenant à IN
Initialisation :
Vérifions cette propriété pour n=1
5^4=12*52+1
La propriété est vraie au rang 1
Caractère héréditaire :
Supposons que 5^(4^n)=52k+1 avec n appartenant à IN*
On a alors 5^(4^(n+1))
=5^(4^(n)*4)=(52k+1)^4
=(52k)^4+4(52k)³+6(52k)²+4(52k )+1
=52[k(52k)³+4k(52k)²+6k(52k)+4k]+1
=52k'+1
La propriété est donc vraie au rang n+1
Conclusion :
Pour tout n appartenant à IN*, il existe un entier k tel que 5^(4^n)=52k+1
Il en résulte qu'il existe un entier naturel k tel que 5^(4^9)=52k+1
D'où 6^(5^(4^9))=6^(52k+1)=6^(52k)* 6
Or 6^52 est congru 1 modulo 53 puisque 53 est premier et 6 n'est pas un multiple de 53
Il en résulte que 6^(5^(4^9)) est congru 6 modulo 53
J'ai oublié de préciser qu'il s'agissait du petit théorème de Fermat
D'accord avec cette démo par contre comment peut on démarrer avec cette relation :
Il fallait le voir que 5^(4^n) pourrait être égal à 52k+1Montrons par récurrence que pour tout n appartenant à IN*, 5^(4^n)=52k+1 avec k appartenant à IN
Comment l'as tu pressentis ?
Cordialement
Anthony
Je ne l'ai pas pressenti en fait j'ai commencé par cherché le plus petit entier n tel que 5^n est congru 1 podulo 52
Bonjour, ravi de voir une solution sur un exemple concrêt.
Avant de m'avancer, je tien si vous le permettez à préciser mon degré d'experience en arithmétique modulaire: dans le cadre d'un cours d'algorithmique, j'avais raté les deux derniers cours/td et hier j'ai vu que ces deux cours concernent ce domaine.
Pour quelques techniques intéressantes, je me permets de conseiller le classique de T.H. Cormen. C'est un gros pavé courant en bibliothèques.
Ceci étant dit, je propose une solution qui n'utilise pas de récurrence:
En appliquant la procédure utilisant la fonction d'Euler, pour résoudre l'équation
6^(5^262144)=b[53] ...(1)
on se retrouve à vouloir prouver que 5^262144 s'écrit sous forme de k*52+r
une solution possible consiste simplement à appliquer encore une fois la même procédure:
comme 52=(2^2)*13
phi(52)= (2^1)*1*1*12 = 24
on cherche alors à écrire 262144 sous forme k2*24+r2
un calcul simple nous donne que k2=10922 et r2=16
alors 5^262144 = ((5^24)^10922)*(5^16)
et comme pgcd(5,52)=1 il est valide de dire que 5^24 est congu 1 modulo 52 et donc 5^262144 est congu 5^16 modulo 52
à ce point on est arrivé au maximum de simplification apportée par la méthode utilisant le petit théorème de Fermat, une façon de faire pour continuer est d'étudier les puissance de 5 avec un exposant qui est diviseur de 16
5^2 est trop petit pour être intéressant,
par contre
5^4 = 625 est congru 1 modulo 52 et donc (5^4)^4 est congu à 1 modulo 52
de cela on tire que 5^262144 est congru à 1 modulo 52
et alors il existe un k tel que 6^(5^262144)= ((6^52)^k)*(6^1)
ce qui nous permet de dire enfin, puisque pgcd(6,53)=1, que
6^(5^262144) est congru à 6 modulo 53
Vos feedback sur cette proposition de solution me seraient précieux,
Cordialement,
Merci pour cette deuxième démo qui aboutit fort heureusement au même résultat que la précédente ;o)
Ta démonstration est assez intéressante, bien vu
Par contre c'est vrai que je n'avais pas trop les moyens de la faire. En TS on ne voit pas la fonction phi d'Euler.
En tout cas belle démo, cela simplifie le raisonnement
Je suis repartis sur quelques exos qui m'avaient posé problème, en essayant cette fois d'appliquer un truc "à la hhh86" et c'est cool!
m'enfin, ça me rassure un peu de voir que mon retard était rattrapable sans prof ^^
bonne continuation et bon courage!
ps: si l'un de vous révise pour des exams des choses dans le genre, on pourrait s'échanger des exo ou autres...
Sans phi, alors
D'une part,.
D'autre part ;
il est clair que
il vient donc manifestement que :
Ainsi,
d'où le résultat.
belle démo aussi thorin
