0
$\begingroup$

Does the following variation of Fermat Little Theorem hold? How do you prove it?

Let $p$ be a prime number greater than $3$. Then there exist a natural non-prime $m > 1$ such that $$p^{\phi(m)} \equiv p \quad (\mathrm{mod}(m)),$$ where $\phi$ is Euler's function.

$\endgroup$
  • 1
    $\begingroup$ What's the motivation for that variation? $\endgroup$ – lhf Feb 5 '16 at 11:51
2
$\begingroup$

As stated, this is quite easy: just take $m=p-1$. Then $\gcd(m,p)=1$ and $p^{\phi(m)}\equiv 1 \equiv p \bmod m$.

$\endgroup$
1
$\begingroup$

Hint: let $m=2p{}{}{}{}{}{}{}$.

$\endgroup$
1
$\begingroup$

This is a strange question. For any m, the Euler totient Phi(m) is the order of the group (Z/m Z)* of invertible elements of the ring Z/m Z. For any p (not necessarily a prime) which is co-prime with m, p mod m is invertible (Bézout), hence, when raised to the power Phi(m), it becomes $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy