Solving x = r₁ mod m₁, x = r₂ mod m₂, … x = rₙ mod mₙ using the Chinese Remainder Theorem

Suppose we have an unknown number of objects. When counted in threes, 2 are left over, when counted in fives, 3 are left over, and when counted in sevens, 2 are left over. How many objects are there?

Sunzi Suanjing, 3rd to 5th century CE

I coded up a PowerShell implementation of the Chinese Remainder Theorem which solves sets of simultaneous modular equations like this. The above story problem can be translated as:

Find x that satisfies the following modular equations:

  • x = 2 mod 3
  • x = 3 mod 5
  • x = 2 mod 7

The answer it comes up with is 23:

> .\chinese-remainder-theorem.ps1 -moduli (3, 5, 7) -remainders (2, 3, 2)
23

Checking, this does indeed meet the criteria:

  • 23 = 3(7) + 2 = 2 mod 3
  • 23 = 5(4) + 3 = 3 mod 5
  • 23 = 7(3) + 2 = 2 mod 7

Actually, combining the equations only tells us that x = 23 mod 105. There are infinitely many such x, in particular 23, 128, 233, 338, …. The general term is 23 + 105n.

One thought on “Solving x = r₁ mod m₁, x = r₂ mod m₂, … x = rₙ mod mₙ using the Chinese Remainder Theorem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s