icone-challenge-math-OS

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

Fermer le menu