Chinese Remainder Theorem (CRT)

CRT is one of the most handy tools that one can use to crack some complex remainder problems. Let's understand how we can use it.

CRT states that if N is divided by coprimes ‘a’ and ‘b’ and that:

Rem[N/a] = x

Rem[N/b] = y

Then we can arrive at a solution for Rem[N/ab]

We will take 2 examples for understanding this concept. The first example provides an introduction to the second one, which is the kind where we would regularly need to apply CRT.

Example Problem 1: 

Find the lowest integer N which when divided by 5 leaves a remainder of 1, when divided by 7 leaves remainder 4, and when divided by 9 leaves remainder 2.

Soln:
Rem [N/5] = 1

Rem [N/7] = 4

Rem [N/9] = 2

Putting it mathematically, we are looking for N of the following form:

N = 5x + 1 = 7y + 4 = 9z + 2 

Above mathematical representation is the essence of CRT.

By solving (which is much easier by plugging in options whilst in the exam),
we get N = 11 for (x,y,z) = (2,1,1)

• There are greater values of N possible which would yield similar remainders when divided by 5, 7 and 9. 
• These can be found out by adding multiples of LCM(5,7,9) = 315 to 11. For example 11 + 315 = 326 is the next such number. 
• This fact is utilized more extensively in the next example problem, where we are given one such large number to start with but are asked (in a manner) to find out the smallest possible one.

Example Problem 2: 

Find the remainder when 3¹²⁰ is divided by 105

Soln:
105 = 3 * 5 * 7

If we can find the remainders obtained when 3¹²⁰ is divided by 3, 5 and 7 respectively, we can apply CRT to find the overall remainder as below:

Rem [3¹²⁰/3] = 0

Rem [3¹²⁰/5] = Rem[9⁶⁰/5] = Rem[-1⁶⁰/5] = 1

Rem [3¹²⁰/7] = Rem[9⁶⁰/7] = Rem[2⁶⁰/7] = Rem[8²⁰/7] = 1

• R = 3x = 5y + 1 = 7z + 1
• It is important to note that R = 3¹²⁰, for a particular set of (x,y,z). However, this set does not yield the smallest value for R. As we observed earlier, larger values for R are obtained by adding multiples of 105 to the smallest value for R.
• So in finding the smallest possible R of the above given form, we are in essence finding out R = Rem[3¹²⁰/105]

By carefully introspecting the above 3 points, it is not difficult to understand how CRT really works.

By solving, we get R = 36 for (x,y,z) = (12,7,5)

Thus, Rem[3¹²⁰/105] = 36

Note: In the above example and the definition given for CRT in the beginning of the article, the smaller individual divisors are taken to be coprimes to each other. For our objective, this is required for redundancy purposes but need not always be necessarily mandatory while solving using CRT.


-Angadbir