Solveeit Logo
Login

Question

Question: If \(\Phi \left( N \right)\) is the number of integers which are less than \(N\) and prime to it, an...

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

Explanation

Solution

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

Complete step by step answer:
Let us consider the given problem. Suppose that NN is an integer and Φ(N)\Phi \left( N \right) is the number of integers which are less than NN and prime to it. Now we need to show that if xx is prime to N, xΦ(N)−1≡0( mod N).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Φ(n)≡1( mod n)n,\,{{a}^{\Phi \left( n \right)}}\equiv 1\left( \bmod n \right) for any integer aa relatively prime to n.n.
Now, it is just a matter of comparing the question with the above theorem named Euler’s theorem.
So, in our case, n=Nn=N and therefore, Φ(n)=Φ(N)\Phi \left( n \right)=\Phi \left( N \right) and a=x.a=x.
Let us rewrite the Euler’s theorem using the given information.
We will get, for a positive integer N, xΦ(N)≡1( mod N)N,\,{{x}^{\Phi \left( N \right)}}\equiv 1\left( \bmod N \right) for any integer xx relatively prime to N.N. Also, Φ(N)\Phi \left( N \right) is the number of integers less than NN and relatively prime to it.
So, we have  xΦ(N)≡1( mod N).\,{{x}^{\Phi \left( N \right)}}\equiv 1\left( \bmod N \right).
Now, let us add a −1-1 on both the left-hand side and the right-hand side of the above congruence.
We will get  xΦ(N)−1≡(1−1)( mod N).\,{{x}^{\Phi \left( N \right)}}-1\equiv \left( 1-1 \right)\left( \bmod N \right).
Therefore, we will get  xΦ(N)−1≡0( mod N).\,{{x}^{\Phi \left( N \right)}}-1\equiv 0\left( \bmod N \right).
Hence it is proved that  xΦ(N)−1≡0( mod N).\,{{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 pp be a prime. Then ap−1≡1( mod p){{a}^{p-1}}\equiv 1\left( \bmod p \right) for any integer aa not divisible by p.p. This theorem is also as important as Euler's theorem.