Finding remainders using Euler's theorem

This method is very useful when the divisor and dividend are relatively prime numbers...

step 1: To calculate euler's no. of a divisor.

euler's no. can be practically taken as cyclicity in remainders by a divisor..

to find euler's no, express the divisor in terms of prime factors...

100 = 2^2 x 5^2.

powers of the prime nos. have no significance...its jus the prime no. that matters...

euler's no (e for convenience) = divisor x (1-1/first prime factor) x (1-1/second prime factor) x ... (1-1/last prime factor)

so, for 100, e = 100 x (1-1/2) x (1-1/5) = 100 x 1/2 x 4/5

= 40.

that means e for 100 = 40. or, in other words, 100 divisor will definetly show a cylicity of 40 in the remainders.

whenever the power of a relatively prime no. will be a multiple of 40, the expression wud show a remainder 1 with 100.

e.g. 3^120 % 100 = ?

we know e for 100 = 40.
3 n 100 are relatively prime nos.
hence, 3^40 % 100 = 1.

hence 3^120 % 100 = (3^40)^3 % 100 = 1^3 = 1.



7^100 % 45 = ?

45 = 3x3x5

e for 45 = 45 x (1-1/3) x (1-1/5) = 24


hence, 7^24 % 45 = 1

hence, 7^100 % 45 = 1^4 x 7^4 % 45

= 2401 % 45

= 16, the required answer...

Finding remainders using cyclicicty with remainders:

This approach is useful when the divisor is small or at times when it is a factor of 100.

3^327%7 = ?

3^1 % 7 = 3
3^2 % 7 = 2
3^3 % 7 = 6
3^4 % 7 = 4
3^5 % 7 = 4x3 % 7 = 5
3^6 % 7 = 5 x 3 % 7 = 1
3^7 % 7 = 1 x 3 % 7 = 3

remainder with first power is same as remainder with 7th power...hence v can say that cyclicity in remainders is 7-1 = 6.

so, 327 % 6 = 3, 

hence, effectively, the remainder is 3^3 % 7 = 6

For Example:

3003^9000%(9*1000)

3003^9000%9 = 0 -----> 9k1

3003^9000%125*8
3^9000%125 = 0 ----> 125a
3^9000%8 = 0 -------> 8b -----------> 1000k2

1000k2 = 9k1 ---> 9000%9000 = 0 
so rem = 0