Consider the following statements:
$S_1$: For any integer $n>1$, $a^{\phi(n)}\equiv 1\ (\text{mod }n)$ for all $a\in Z_n^*$, where $\phi(n)$ is Euler's phi function.
$S_2$: If $p$ is prime, then $a^p\equiv 1\ (\text{mod }p)$ for all $a\in Z_p^*$.
Which one of the following is/are correct?
Statement $S_1$ is true by Euler's theorem.
If $a\in Z_n^*$, then $a$ and $n$ are relatively prime.
So,
$a^{\phi(n)}\equiv 1\ (\text{mod }n)$
Now consider $S_2$.
For prime $p$, Fermat's theorem gives
$a^{p-1}\equiv 1\ (\text{mod }p)$
for $a\in Z_p^*$.
But $S_2$ says
$a^p\equiv 1\ (\text{mod }p)$
This is not generally true.
Actually,
$a^p\equiv a\ (\text{mod }p)$
So, $S_2$ is false.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.