icone-challenge-math-OS

Solution pour le challenge 28


Soit x\in\mathbb{N}, non multiple de p. On sait, d’après le petit théorème de Fermat, que :

    \[ x^{p-1}\equiv1\pmod{p}\]

En effectuant la division euclidienne de x par p-1 :

    \[ x=\left(p-1\right)q+r\]

avec 0\leqslant r<p-1.

On voit ainsi que :

    \[ x^{x}\equiv x^{r}\pmod{p}\]

Il suffirait donc que x vérifie la double condition :

    \[ \left\{\begin{array}{cccc} x & \equiv & 1 & \pmod{p-1}\\ x & \equiv & a & \pmod{p} \end{array}\right.\qquad\left(\star\right)\]

pour conclure que x^{x}\equiv a\pmod{p}.

Or, l’existence d’un x\in\mathbb{\mathbb{N}} vérifiant \left(\star\right) est conséquence immédiate du théorème des restes chinois, puisque (p-1)\wedge p=1.


Pour consulter l’énoncé, c’est ici

Partager cet article

Laisser un commentaire