Solution pour le challenge 28
Soit 
non multiple de 
On sait, d’après le petit théorème de Fermat, que :
![\[ x^{p-1}\equiv1\pmod{p}\]](https://math-os.com/wp-content/ql-cache/quicklatex.com-59d34d60342abf4974bea17c3f6ff515_l3.png "Rendered by QuickLaTeX.com")
En effectuant la division euclidienne de 
par 
:
![\[ x=\left(p-1\right)q+r\]](https://math-os.com/wp-content/ql-cache/quicklatex.com-1ff2bb75311ff5639f1422610d6f6af4_l3.png "Rendered by QuickLaTeX.com")
.
On voit ainsi que :
![\[ x^{x}\equiv x^{r}\pmod{p}\]](https://math-os.com/wp-content/ql-cache/quicklatex.com-70d6e9cd78c37c009ea10e7db0ff592a_l3.png "Rendered by QuickLaTeX.com")
Il suffirait donc que 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)\]](https://math-os.com/wp-content/ql-cache/quicklatex.com-d59a83ca3962fe117c7417f7390dda8a_l3.png "Rendered by QuickLaTeX.com")
Or, l’existence d’un 
vérifiant 
est conséquence immédiate du théorème des restes chinois, puisque 
.
Pour consulter l’énoncé, c’est ici