Congruences maths expertes

[Vandazo]

Bonjour,
J'ai un devoir à faire en mathématiques expertes et je ne comprends pas du tout comment faut il faire
J'ai beau essayer je n'y arrives décidemment pas
Si quelqu'un pouvait m'aider sur les deux questions suivantes s'il vous plaît :

Le nombre 7^12 est congru modulo 13 à : ?
Le nombre 11^46 est congru modulo 23 à : ?

Merci d'avance pour l'aide !

[mathelot]

Bonsoir,
cet exercice est une application immédiate du petit théorème de Fermat

si p est un entier premieret a un entier et si p ne divise pas a alors



https://fr.wikipedia.org/wiki/Petit_th% ... 0ce%20test.

[Vandazo]

Je ne connaissais pas du tout ce théorème merci pour l'information je vais aller regarder comment tout cela se démontre si je peux y comprendre bien sur

Merci encore !

[mathelot]

bonsoir,

le petit théorème de Fermat donne directement:

avec p=13 et a=7

une méthode sans théorème de Fermat est donnée par l'algorithme d'exponentiation rapide:
si l'exposant est pair, disons 2n, alors

pour avancer dans le calcul, on divise l'exposant par 2
et on élève la base au carré. Si l'exposant est impair, on écrit un facteur de côté:



Application
pour calculer on écrit l'exposant 12 en base 2:

il vient


on remplace 49 par son reste modulo 13: 10


on remplace 100 par son reste modulo 13:9


on remplace 81 par son reste modulo 13:3


on remplace 27 par son reste modulo 13:1


d'où

[mathelot]

Pour la seconde congruence, le petit théorème de Fermat donne:

[mathelot]

sans le petit théorème de Fermat:

on écrit l'exposant 46 en base 2



or, modulo 23:

on élève au carré

on élève au carré

on élève au carré

on élève au carré


d'où



d'où