Solution pour le challenge n° 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\qquad\text{avec }0\leqslant r<p-1$

on voit donc 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$ et $p$ sont premiers entre eux.

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

Partager cet article

Laisser un commentaire Annuler la réponse