Question

If $\varphi \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^{\varphi \left(N\right)}-1\equiv 0(mod.N)$.

Answer 1

Let $1,a,b,c.....(N-1)$ denote the $\varphi \left(N\right)$ numbers, less than $N$ and prime to it; also let ${}^{\prime }{x}^{\prime }$ represent any one of these numbers then $1x,ax,bx,.....(N-1)x$ are all different and primes to $N.$ there are $\varphi \left(N\right)$ of such products, and it is known that when these products are divided by $N,$ the remainders are all different and all primes to $N;$ thus the $\varphi \left(N\right)$ remainders must be $1,a,b,c.....(N-1)$ Though not necessary in this order.

Hence $x,ax,bx,..........(N-1)$ by a multiple of $N$

$\therefore \{x^{\varphi \left(N\right)}-1\}abc.....(N-1)=M\left(N\right)$

But the product $abc....(N-1)$ is prime to $N$

$\therefore x^{\varphi \left(N\right)}-1\equiv 0(mod.N)$