Euler’s Theorem on Remainders

Say, a positive integer N has prime factors a, b, c, d, ….

       Then, E(N) = N*(1-1/a)*(1-1/b)*(1-1/c)*…., where E(N) is the Euler’s totient function that denotes the number of positive integer that are co prime to and less than a certain positive integer ‘n’.

       Euler’s theorem states that if p and n are positive co-prime integers, then :

Rem[p^E(n)/n]=1 or p^E(n) mod n =1.

In other words,

Euler totient of N is defined as the number of positive integers less than or equal to N that are relatively prime to N.

Let E = a^x * b^y * c^z. (a,b,c are prime numbers)
Euler(N)= N * ( 1-1/a )  *  ( 1-1/b ) * ( 1-1/c )
Euler(prime number) = prime number - 1.

This theorem leads to the fact that if n and a are coprime positive integers, then, a^(E(n)) = 1(mod n)
Where, E(n) = Euler(n).

In case N is prime, a^(N-1) = 1(mod n)

Example: 

Find remainder of 9^101/125.

      E [125] = 100. Since, 100 and 125 are co-prime, Rem[9^100/125] = 1. Therefore, Rem[9^101/125]=1*Rem[9/125]=9 (answer).

Find remainder of 17^ (5600^67) mod 7.

      Here n = 7. E(7) = 6.

Now let’s concentrate on the exponent of 17.

5600^67 mod 6 = 2^67 mod 6 = 2*2^66 mod 6 = 2*64^11 mod 6 = 2*4^11 mod 6

=2*4*16^5 mod 6 = 8*2^5 mod 6 = 2*32 mod 6 = 4.

Thus, we have to find 17^4 mod 7 = 289^2 mod 7 = 2^2 mod 7 = 4 (answer).

Find remainder of 38^ (178^62) mod 104.

      Here n = 104. E(104) = 103.

Now let’s concentrate on the exponent of 38.

178^62 mod 103 = 75^62 mod 103 = 5625^31 mod 103 = 63^31 mod 103

= 63*63^30 mod 103 = 63*3969^15 mod 103 = 63*55^15 mod 103

= 63*55^14*55 mod 103 = 63*55*3025^7 mod 103 = 63*55*38^7 mod 103

= 63*55*38*38^6 mod 103 = 63*55*38*1444^3 mod 103 = 63*55*38*2^3 mod 103

= (63*38)*(55*8) mod 103 = 25*28 mod 103 = 82

Now we have to find 38^82 mod 104

38^82 mod 104 = (1444)^41 mod 104 = 92^41 mod 104 = 92*8464^20 mod 104

= 92*40^20 mod 104 = 92*1600^10 mod 104 = 92*40^10 mod 104

= 92*1600^5 mod 104 = 92*40^5 mod 104 = 92*40*40^4 mod 104 = 92*40*1600^2 mod 104

=92*40*40*40 mod 104 = 92*40*1600 mod 104 = 92*40*40 mod 104 = 92*1600 mod 104

= 92*40 mod 104 = 40 (answer).