Énigme : Le logarithme discret
Bonsoir à tous,
Pour qui serait intéressé, voici une petite énigme :
Il se fait que tout entier compris entre $1$ et $5038$ peut s'écrire sous la forme d'une puissance $k$ de $13$ modulo $5039$, pour $k=$ un entier compris entre $1$ et $5038$, car $13$ est une racine primitive modulo $5039$.
Ainsi, par exemple, $1=13^{5038}$ (modulo $5039$), $2=13^{4192}$ (modulo $5039$), $3=13^{1104}$ (modulo $5039$), $4=13^{3346}$ (modulo $5039$), $5=13^{2800}$ (modulo $5039$), ...et ainsi de suite jusqu'à $5038=13^{2519}$ (modulo $5039$).
Saurez-vous proposer un calcul mathématique qui, dans la minute, conduit à la valeur de l'$x$ tel que $288=13^{x}$ (modulo $5039$) ?
Bon divertissement.
Pour qui serait intéressé, voici une petite énigme :
Il se fait que tout entier compris entre $1$ et $5038$ peut s'écrire sous la forme d'une puissance $k$ de $13$ modulo $5039$, pour $k=$ un entier compris entre $1$ et $5038$, car $13$ est une racine primitive modulo $5039$.
Ainsi, par exemple, $1=13^{5038}$ (modulo $5039$), $2=13^{4192}$ (modulo $5039$), $3=13^{1104}$ (modulo $5039$), $4=13^{3346}$ (modulo $5039$), $5=13^{2800}$ (modulo $5039$), ...et ainsi de suite jusqu'à $5038=13^{2519}$ (modulo $5039$).
Saurez-vous proposer un calcul mathématique qui, dans la minute, conduit à la valeur de l'$x$ tel que $288=13^{x}$ (modulo $5039$) ?
Bon divertissement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
pas en une minute, mais avec ce que vous donnez :
le reste de la division euclidienne de $5\times 4192+2\times1104$ par $5039$ est $3016$.
Donc $3016$.
S
En moins de $1$ minute (sans taper ce message) et sans machine : $x=2 \times 1104 + 5\times 4192 = 23168$ et comme $4\times 5039=20156$ on a $x=3012 \, [5039].$ Je calcule mieux que @samok :-P.
S
S
S
S
As-tu fait le calcul sans machine pour écrire $13^{3012} = 1051 \,[5039]$ ?
Bon, en tout cas je ne comprends pas mon erreur... sais-tu me l'expliquer aussi bien que tu calcules ?
Le calcul auquel je pensais était bien $(5\cdot 4192+2\cdot 1104)$ (modulo $5038$)
Pourquoi $5038$ et pas $5039$ ? Parce que le nombre d'entiers que génère l'expression $13^k$ (modulo $5039$) quand $k$ parcourt $\mathbb{N}$ est égal à $5038$.
Encore une fois merci à tous.
Si on a un entier naturel $d\in\N^\ast$ tel que $a^d=1[n]$, alors la suite des puissances de $a$ modulo $n$ est périodique de période $d$. En particulier, si on veut calculer $a^s$ pour $s\in\N$, il suffit d'écrire la division euclidienne $s=dq+r$ de $s$ par $d$ et d'utiliser $a^s=a^r[n]$. Autrement dit, on prend l'exposant modulo $d$.