Home » Blog » Cyclicity of Remainders for CAT Exam

Cyclicity of Remainders for CAT Exam

Monday, July 13th, 2020

---

Cyclicity of Remainders

In this post I would like to discuss some of the really fundamental ideas that can be used to solve questions based on remainders. If you have just started your preparation for CAT Exam, you might find this article helpful.

First of all,

What I am trying to say above is that if you divide a^n by d, the remainder can be any value from 0 to d-1.

Not only that, if you keep on increasing the value of ‘n’, you would notice that the remainders are cyclical in nature. What I am trying to say is that the pattern of remainders would repeat. Let me try to clarify this with an example:

4^1 divided by 9, leaves a remainder of 4.

4^2 divided by 9, leaves a remainder of 7. {Rem(16/9) = 7}

4^3 divided by 9, leaves a remainder of 1. {Rem (64/9) = 1}

4^4 divided by 9, leaves a remainder of 4. {Rem (256/9) = 4}

4^5 divided by 9, leaves a remainder of 4. {Rem (1024/9) = 7}

4^6 divided by 9, leaves a remainder of 4. {Rem (4096/9) = 1}

4^(3k+1) leaves a remainder of 4

4^(3k+2) leaves a remainder of 7

4^3k leaves a remainder of 1

As you can see from above that the remainder when 4^n is divided by 9 is cyclical in nature i.e. the remainders obtained are 4,7,1, 4,7,1, 4,7,1 … and so on. They will always follow the same pattern.

 

Funda 1: a^n when divided by d, will always give remainders which will have a pattern and will move in cycles of ‘r’ such that r is less than or equal to d.

 With the help of the above idea, you can solve a large number of remainder questions. All you need to do is to figure out the cycle / pattern in which the remainders are moving, and it will lead you to the answer.

Let us look at an example to illustrate the above idea.

Eg: What will be the remainder when 4^143 is divided by 9.

From the calculations that I did in the beginning of the post, I know that:

Remainders of 4^n when divided by 9, move in a cycle of 3.

So, I need to express 143 = 3k + x and that would lead to the answer.

I know that 143 = 141 + 2 {141 is divisible by 3}

So, my answer would be the 2^nd value in the list, which is 7.

n the questions where you have to find out the remainder of a^n by d, as a rule you can follow this process:

Step 1: Find out the cycle of remainders when a^n is divided by d and make a list of those values.

Step 2: Find out the cyclicity, say ‘r’

Step 3: Find out the remainder when the power is divided by the cyclicity i.e. Rem[n/r] = p

Step 4: The answer would be the p^th value in the list. {If p = 0, it would be the last value in the list}

 

Funda 2: While trying to find the cycle / pattern of remainders when a^n is divided by d, just multiply the previous remainder with ‘a’ to get the next value.

If you notice in the example mentioned in the beginning of this post, I have calculated 4^5 and 4^6 and then found out the remainder. As you might have realized by now that it is a long and tedious process. But the good part is – you can avoid that tedious process by just multiplying the previous remainder. In that example instead of calculating 4^5 and then dividing by 9, I could have just multiplied the previous remainder, which was 4 with 4 to get 16, which would have directly given me a remainder of 7.

Got confused? Well, let us look at a new example.

Eg: Find out the cyclicity of remainders when 3^n is divided by 11.

Let us try and solve a slightly more complicated problem with this idea.

Eg: Find out the remainder when  is divided by 7.

 

Step 1: Find out the cycle / pattern of remainders when 4^n is divided by 7.

Rem [4^1 / 7 ] = 4

Rem [4^2 / 7 ] = 2

Rem [4^3 / 7 ] = 1

So, the cycle/pattern is 4,2,1.

 Step 2: The cyclicity is 3.

Step 3: Rem [Power/Cyclicity]  = Rem [32^32 / 3] = (-1)^32 = 1

Step 4: The answer is the 1^st value in the list, which is 4.

I hope you found this post useful. Suggestions for future posts are more than welcome.

---