How to find remainder – 2 : Fermat’s little theorem

So continuing discussion from our last post How to find remainder – 1 – Euler’s theorem, now we will discuss Fermat’s little theorem which can be easily used in questions where the divisor is a prime number or it can be reduced to a prime number by cancelling some common term from dividend and divisor.

 

So let’s discuss Fermat’s little theorem in this article and how it will help us to find remainder.

 

Fermat’s little theorem: If p is a prime number, then for any integer a, a^p − a will be evenly divisible by p. This can be expressed in the notation of modular arithmetic as follows:

a^p === a (mod p)

A variant of this theorem is stated in the following form: if p is a prime and a is an integer coprime to p, then a ^p−1 − 1 will be evenly divisible by p. In the notation of modular arithmetic:

a^(p-1) === 1 (mod p)

Basically if N in Euler’s theorem is a prime number then φ(N) = N(1-1/N) = N-1.

So, remainder [{a^(N-1)}/N] = 1.

Now Lets see how does this theorem helps us in finding remainders.

 

Q. Find the remainder when 72^40 is divided by 41.

Answer: So here we see that 41 is a prime number, so we will target Fermat’s little theorem instead of Euler’s theorem.

Again 72 and 41 are co-prime. so we can apply our little theorem in this problem easily.

–> remainder [72^40/41] = 1

If the question is find the remainder when 72^41 is divided by 41. So, remainder [72^41/41] = remainder [72/41] = 31.

 

Facts about number 41: 41 is the 13th smallest prime number. The next is 43, with which it comprises a twin prime. It is also the sum of the first six prime numbers (2 + 3 + 5 + 7 + 11 + 13), and the sum of three primes (11 + 13 + 17).

Q. Find the remainder when 82^40 is divided by 41.

Answer: Here we see that 41 is a prime number. But 82 and 41 are not co-prime, i.e. 82 is divisible by 41. and hence  82^40 is divisible by 41.

so remainder = 0.

Hence checking if the divisor and dividend are co-prime or not is very important and should not be forgotten in exam. 🙂

 

In the next article we will discuss how Wilson’s theorem will help us in solving similar remainder problems.

Meanwhile if you have any remainder problems, you can post it in the forumhttp://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.

 

 

Deals of the day from DealMaggu

No items