Remainder Theorem
-
If a, b, c are the prime factors of N such that N= $$a^p$$ * $$b^q$$ * $$c^r$$
then the number of numbers less than N and co-prime to N $$ \phi (N) $$= N (1-1/a) (1 - 1/b) (1 - 1/c). This function is known as the Euler's totient function.
Euler's theorem
- If M and N are co-prime to each other then remainder when $$M ^ {\phi (N)} $$ is divided by N is 1.
