How to find remainder – 1 – Euler’s theorem
To find the remainder when a number having a big power is divided by another number may seem to be a difficult, probably impossible, task but if you know certain sequential method to solve it you will find that these problems will become sitters for you.
There are certain theorem’s which will help us in solving these types of problems. We just need to find, which theorem will be applicable in a certain problem directly. Even if the theorem is not applicable directly we can modify it to certain form on which these theorem’s will be directly applicable.
The main theorem’s which will help us to solve these types of problems are:
1. Euler’s Theorem 2. Fermat’s Little Theorem 3. Wilson’s Theorem 4. Chinese Remiander Theorem.
So lets discuss Euler’s theorem in this article and how it will help to find remainders easily.
Euler’s theorem states that if n and X are coprime positive integers, then
- X^(φ(N)) ≡ 1 (mod N)
where φ(N) is Euler’s totient function and φ(N) = N(1-1/a)(1-1/b)(1-1/c) (where N = a^p x b ^q x c ^d)
and “… ≡ … (mod n)” denotes congruence modulo n.
Now Lets see how does this theorem helps us in finding remainders.
Q. Find the remainder when 7^97 is divided by 45.
Ans: so here we can see HCF(7,15) = 1 and hence 7 and 15 are co-prime numbers, so we can apply Euler’s theorem here.
45 = 3^3 x 5.
φ(45) = 45(1-1/3)(1-1/5) = 45 x 2/3 x 4/5 = 24.
so remainder [ 7^96 / 45] = remainder [ 7^24 x 7^24 x 7^24 x 7^24 /45] = 1
so remainder [ 7^97 / 45] = remainder [ 7^96 x 7 / 45] =7.
Q. Find the last 3 digits of 51^1202.
Ans: The easiest way of solving such problem in which we need to find last 3 digits is to divide the number by 1000 and find the number.
So, Last 3 digits of 51^1202 = remainder of 51^1202 divided by 1000.
Here we can see 51 and 1000 are co-prime to each other.
Now 1000 = 2^3 x 5^3.
φ(1000) = 1000 x (1-1/2)(1-1/5) = 1000 x 1/2 x 4/5 = 400
So by euler’s theorem, remainder [51^1202/1000] = remainder [{(51^400)^3 x 51^2}/1000] = remainder [51^2/1000] = 601.
In the next article we will discuss how Fermat’s little theorem will help us in solving similar remainder problems.
Meanwhile if you have any remainder problems, you can post it in the forum http://mba.webmaggu.com/groups/quantitative-ability/forum/topic/remainder-problems/
If you have articles on Quant/DI/Verbal/LR/CR/SC which could be published on our top page feel free to send it to us at [email protected], we will publish it with your name FB/G+/TW/WM id and your pic :). The article should be original & compiled by you and not fully copied from other websites.
