Question

If $\Phi \left( N \right)$ is the number of integers which are less than $N$ and prime to it, and if $x$ is prime to $N,$ show that: ${{x}^{\Phi \left( N \right)}}-1\equiv 0\left( \bmod N \right).$

Answer 1

Hint: We will use the Euler’s theorem to prove the given congruence. Euler’s theorem states that for a positive integer $n,\,{{a}^{\Phi \left( n \right)}}\equiv 1\left( \bmod n \right)$ for any integer $a$ relatively prime to $n.$ We will apply this theorem in the given situation.

Complete step by step answer:
Let us consider the given problem. Suppose that $N$ is an integer and $\Phi \left( N \right)$ is the number of integers which are less than $N$ and prime to it. Now we need to show that if $x$ is prime to $N,\,{{x}^{\Phi \left( N \right)}}-1\equiv 0\left( \bmod N \right).$
Here, we have a theorem called Euler’s theorem which states that for a positive integer $n,\,{{a}^{\Phi \left( n \right)}}\equiv 1\left( \bmod n \right)$ for any integer $a$ relatively prime to $n.$
Now, it is just a matter of comparing the question with the above theorem named Euler’s theorem.
So, in our case, $n=N$ and therefore, $\Phi \left( n \right)=\Phi \left( N \right)$ and $a=x.$
Let us rewrite the Euler’s theorem using the given information.
We will get, for a positive integer $N,\,{{x}^{\Phi \left( N \right)}}\equiv 1\left( \bmod N \right)$ for any integer $x$ relatively prime to $N.$ Also, $\Phi \left( N \right)$ is the number of integers less than $N$ and relatively prime to it.
So, we have $\,{{x}^{\Phi \left( N \right)}}\equiv 1\left( \bmod N \right).$
Now, let us add a $-1$ on both the left-hand side and the right-hand side of the above congruence.
We will get $\,{{x}^{\Phi \left( N \right)}}-1\equiv \left( 1-1 \right)\left( \bmod N \right).$
Therefore, we will get $\,{{x}^{\Phi \left( N \right)}}-1\equiv 0\left( \bmod N \right).$
Hence it is proved that $\,{{x}^{\Phi \left( N \right)}}-1\equiv 0\left( \bmod N \right).$

Note: Let us recall the Fermat’s Little theorem for we need it very often. It states as follows: Let $p$ be a prime. Then ${{a}^{p-1}}\equiv 1\left( \bmod p \right)$ for any integer $a$ not divisible by $p.$ This theorem is also as important as Euler's theorem.