Chinese Remainder Theorem with Python

Chinese Remainder Theorem

Background Story:

back in the Han dynasty, there is a famous General Han Xin. In order to prevent the spy in the army to detect the number of his soldiers, he used an advanced Counting System (韩信点兵).
Instead off directly counting from 1 to n, he asked his soldiers to number off from 3 times. First time 1 to 3, then 1 to 5 and finally 1 to 7.

What is the number x ?

x mod 3≡ 2
x mod 5≡ 3
x mod 7≡ 2

By doing this Han Xin Counting Off Algorithm, he is pretty confident the spies could not figure out the accurate number of total soldiers, Unless the spy knew Number Theory or have a python program 😝 .

The solution to the Han Xin Counting Algorithm was written in a poem:

3 friends walk for 70 miles.
5 plum tree with 21 blossom flowers.
7 kids party in the full moon(15).
Mod 105 you would know!

三人同行七十稀, 五树梅花廿一枝, 七子团圆正半月, 除百零五便得知!

Solutions:

Direction Solution From the Poem:

#1. Multiply the Residue of according equation.
2*70 + 3*21 + 2*15=233
#2. Mod the Least Common Multiple of (3,5,7)
233 mod 105= 23

Note: The solution is NOT unique any multiple of 105 can be added to the solution and still satisfy the condition, such as 128, 233, 338 ….

The solution from Python Code:

from functools import reduce
def chinese_remainder(n, a):
    sum=0
    prod=reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n,a):
        p=prod//n_i /*for large p*/
        sum += a_i* mul_inv(p, n_i)*p
    return sum % prod
def mul_inv(a, b):
    b0= b
    x0, x1= 0,1
    if b== 1: return 1
    while a>1 :
        q=a// b
        a, b= b, a%b
        x0, x1=x1 -q *x0, x0
    if x1<0 : x1+= b0
    return x1
n=[3,5,7]
a=[2,3,2]
print(chinese_remainder(n,a))
23.0

General Solution:

How do we find a general solution for Chinese Remainder Theorem Problems?

Step1.Find the numbers for 1≡ Mod(ni, nj) for pairwised coprime n1… nm

Step2.Multiply the residue to each corresponding number in 1.

Step3. Add all the number in Step2 and mod N=n1*n2..*nm

n mod3 =2
n mod5 =3
n mod7 =2
Step1.
# Find remainder 1 for mod 3 
5*7=35 mod 3= 2
5*7*2=70 mod 3 =1 *
# Find remainder 1 for mod 5
3*7 mod 5 =1 *
# Find remainder 1 for mod 7
3*5 mod 7 =1 *
Step 2. Add the Residue* number in Step 1
2*70 + 3*21+ 2*15=233
Step 3. Find remainder mod 3*5*7
233 mod 105 =23

Why this Algorithm works? Now introduce the famous Chinese Remainder Theorem:

Chinese Remainder Theorem :

if the ni are pairwise coprime, and if a1, …, ak are integers such that 0 ≤ ai < ni for every i, then there is one and only one integer x, such that 0 ≤ x < N and the remainder of the Euclidean division of x by ni is ai for every i.

Summary:

The solution of the Chinese Remainder Theorem problem is relatively easy to find as long as the problem satisfies the pairwise co-prime assumption, however, the idea and concept of Ring Isomorphism behind the theorem are complicated and took a long time for me to really understand.

Note: I really loved the Chinese Remainder theorem when I was in school, not only because that’s probably the only thing in Math book that’s from China, but also the interesting story behinds it. I still doubt if Han Xin really used the Chinese Remainder Theorem as Soldier Counting System, because how would he know if he has 23 or 105 or 233 soldiers…
p.s. my friend used to joke it is Tibetan Remainder Theorem

Happy Studying!🐵

Reference :https://en.wikipedia.org/wiki/Chinese_remainder_theorem