Number System: Cyclicity of Remainders

Number system is the most fundamental topic in mathematics. Questions from this topic are seen in almost every entrance exam. It is a vast topic which mainly includes concept of HCF and LCM, concept of unit digit, concept of factors, concept of cyclicity, concept of factorials, etc.

Cyclicity of remainders is an important concept which can be used to solve questions based on remainders. This concept utilizes the fact that remainders repeat themselves after a certain interval when divided by a number.

First of all, we know that Remainder = 0 to d – 1; where d= number by which the divisor is divided.
If we divide aⁿ by d, the remainder can be any value from 0 to d-1. If we keep on increasing the value of n, the remainders are cyclical in nature. The pattern of the remainders would repeat. Let us understand the concept of repetition with the help of an example.

Example 1: 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 above, the remainder when 4n is divided by 9 is cyclical in nature. The remainders obtained are 4, 7, 1, 4, 7, 1, 4, 7, 1 and so on. They will always follow the same pattern.

aⁿ 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.
Let us apply this concept to some examples to getter a better understanding of it.

Example 1: What will be the remainder when 41^43 is divided by 9?

Solution:
Step 1: We know that 41ˆ1 when divided by 9 gives a remainder= 5.
41ˆ2 when divided by 9 gives a remainder= 7.
41ˆ3 when divided by 9 gives a remainder= 8.
41ˆ4 when divided by 9 gives a remainder= 0.
41ˆ5 when divided by 9 gives a remainder=2.
41ˆ6 when divided by 9 gives a remainder= 1.

So, the cycle/pattern is 5,7,8,0, 2, and 1.

Step 2: The cyclicity is 6.
Step 3: 43 when divided by 6 is 1
Step 4: The answer is the 1st value in the cyclic pattern i.e. 5
Answer is 5.

Alternatively, we can solve this question using the divisibility of 9.

Example 2: Find out the remainder when 32ˆ32ˆ32 is divided by 7.

Solution: Step 1: We know that 32ˆ1 when divided by 7 gives a remainder= 4
32ˆ2 when divided by 7 gives a remainder= 2.
32ˆ3 when divided by 7 gives a remainder= 1.
32ˆ4 when divided by 7 gives a remainder= 4.
32ˆ5 when divided by 7 gives a remainder= 2.
32ˆ6 when divided by 7 gives a remainder= 1.

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

Step 2: The cyclicity is 3.
Step 3: 32ˆ32 when divided by 3 is 1
Step 4: The answer is the 1st value in the cyclic pattern of 4, 2, and 1 i.e. 4.
Answer is 4.

Question 1: Find the remainder when 10ˆ20ˆ30 is divided by 3.
Question 2: Find the remainder when 47ˆ45 is divided by 4.
Question 3: Find the remainder when 52ˆ28 is divided by 6.