Le mystère du logarithme discret
dans Arithmétique
Bonjour
Je profite des vacances pour proposer à tout qui serait intéressé une deuxième énigme. Après, je vous laisserai tranquilles.
Voici cette énigme, à résoudre sans l'aide des machines.
Par quel raisonnement peut-on trouver la plus petite valeur positive de $x$ dans l'expression $33^{x}\equiv 297 \pmod{2018}$, si l'on sait que :
1) $1009$ est un nombre premier,
2) $33$ est d'ordre $1008$ modulo $2018$,
3) $33^{545}\equiv 55\pmod{2018}$,
4) $33^{820}\equiv 15\pmod{2018}$.
Merci d'avance.
Je profite des vacances pour proposer à tout qui serait intéressé une deuxième énigme. Après, je vous laisserai tranquilles.
Voici cette énigme, à résoudre sans l'aide des machines.
Par quel raisonnement peut-on trouver la plus petite valeur positive de $x$ dans l'expression $33^{x}\equiv 297 \pmod{2018}$, si l'on sait que :
1) $1009$ est un nombre premier,
2) $33$ est d'ordre $1008$ modulo $2018$,
3) $33^{545}\equiv 55\pmod{2018}$,
4) $33^{820}\equiv 15\pmod{2018}$.
Merci d'avance.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$33^{ 1365}=33^{ 545+820}=55\times 15= 33 \times 25;$
$33^{ 1640}=33^{ 820+820}=15\times 15=9\times 25;$
$\displaystyle 33^{ 275}=33^{ 1640-1365}=\frac{9}{33}=\frac{9\times 33}{33^2}=\frac{297}{33^2},$
d'où $\quad x=277$
Cordialement
Paul
(En plus, ta notation est plus pratique que la mienne).
Cela dit, il n'est peut-être pas inutile (?) de souligner que :
1) ces calculs ne sont possibles que parce que les nombres considérés ici, comme $33$ et $25$, ont un inverse, modulo $2018=2\cdot 1009$.
2) la solution trouvée $x=277$ est bien la plus petite solution positive qui soit car, $33$ étant d'ordre $1008$ (donc $33$ étant une racine primitive modulo $2018$), l'ensemble des exposants $m$ de $33$ tels que $33^m\equiv 297\pmod{2018}$ est de la forme $m=277+1008k$ (avec $k\in\mathbb{Z}$).
En ajoutant cela, est-ce que je fais de l'excès de zèle ?
Cordialement
Paul