What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, , ,

Newbie at Number Theory (Part 8): The Chinese Remainder Theorem

Published by

Valt

on

Do you remember when you were asked to solve a system of equations back in algebra class? In the case that you don’t here’s a brief reminder. The goal of these types of questions were to have you find a value of x and/or y that satisfied two equations at the same time. For example, x=2 satisfies 5x + 2 = 12 and 23x - 10 = 36. Or, x=2 and y=3 satisfy y= 5x + 2 and 2y-3x=18 simultaneously.

We are about to do something similar with modular congruences. Modular congruence is the fancy mathy way to say that we are going to find solutions (values of x) that satisfy congruences like ax\equiv b \pmod{n}.

Let’s get started!

Solving A Linear Congruence

Theorem: (Solvability of Linear Congruences) Let a, b, and n be integers and denote d = \gcd{(a,n)}. Then, the linear congruence ax\equiv b \pmod{n} has a solution if and only if d\mid b.

Proof: It’s usually helpful to break up “if and only if” proofs into two parts. So let’s do that:

Forward: If there is a solution to ax\equiv b \pmod{n}, then d\mid b.

This proof mimics proofs that we saw back in Newbie at Number Theory (Part 3): ax+by = 1. Let x_0 be a solution to the linear congruence ax\equiv b \pmod{n}. By definition of congruence we deduce,

ax_0- b=nk, for some integer k.

Solving for b,

b = ax-nk.

Recall d = \gcd{(a,n)}, so that d\mid(ax-nk), and therefore d\mid b.

Backward: If d\mid b then, there is a solution to ax\equiv b \pmod{n}.

Let d\mid b and hence b = dt for some integer t. We aim to show that there is a solution to ax\equiv b \pmod{n}. Since d = \gcd{(a,n)}, we deduce using Bézout’s Identity that there are integers x' and y' such that,

ax' - ny' = d.

Multiplying through by t gives,

a(x't) - n(y't) = dt = b.

Letting x = x't we have found our desired solution, since the above equation is equivalent to : ax\equiv b \pmod{n}.

\square

Now that we know when there is a solution, we’d like to find a general form of the solution. For this we’ll need something that we’ve seen before, but cast in a new light.

Theorem (Solution to ax - ny= b): Let a, b, and n be integers and denote d = \gcd{(a,n)}. Then, the Diophantine equation ax- ny = b has a solution if and only if d\mid b. Moreover, there are infinitely many solutions of the form:

x = x_0 +\left(\frac{n}{d}\right) k and y=y_0 - \left(\frac{a}{d}\right) k

For this one I will refer you to the section Back to The Proof of Zero or Infinite? in the post about the equation ax+ by = 1. We’ve done the work before so why do it again?

Corollary (Solution Form): Let a, b, and n be integers and denote d = \gcd{(a,n)}. If d\mid b then, the linear congruence ax\equiv b \pmod{n} has a solution set:

x=x_0 + k\left(\frac{n}{d}\right).

Where x_0 is the solution guaranteed by Theorem: (Solvability of Linear Congruences) and k is an integer.

Proof: Observe that ax\equiv b \pmod{n} is equivalent to ax - ny= b. Therefore, they have the same solution set. (See the proof of Theorem: (Number of Solutions of Linear Congruences) for more details.)

\square

Back to Linear Congruences

Not so bad huh? Well, as long as you are comfortable with Bézout’s Identity! Our new goal is to determine how many solutions there are. This might sound like a strange question since if x is a solution then for every integer k we also have x + k\left(\frac{n}{d}\right) as a solution by he above corollary. To see it explicitly observe,

a\left((x+k\left(\frac{n}{d}\right)\right)\equiv ax + k\underbrace{\left(\frac{a}{d}\right)}_{\mathrm{Integer}}n \equiv ax \equiv b \pmod{n}

So we have infinitely many solutions, one for each k. So, we’re done right? There are infinitely many solutions.

Well, yes this is true, however, when we are working (mod n), we don’t really think of x and x + kn as different solutions since x\equiv x +nk\pmod{n} for all integers k. What I should have asked is, how many different solutions are there (mod n)? In other words, we only count solutions x_1 and x_2 as distinct if they are incongruent (mod n) ie x_1\not\equiv x_2\pmod{n}.

Theorem: (Number of Solutions of Linear Congruences) Let a, b, and n be integers and denote d = \gcd{(a,n)}. If d\mid b, then there are d incongruent solutions (mod n) to the linear congruence ax\equiv b \pmod{n}.

Proof: Let a, b, and n be integers and denote d = \gcd{(a,n)}. By our first theorem we know that a solution exists, we just have to show that there are d incongruent solutions (mod n). To that end, let x_0 be such a solution. Then Corollary (Solution Form) we know the form of the solution is

x=x_0 + k\left(\frac{n}{d}\right).

We therefore make the claim that the family of incongruent solutions (mod n) is given by:

x_0\;,\;x_0 + \frac{n}{d}\;,\;x_0 + 2\left(\frac{n}{d}\right)\cdots ,\;x_0 + (d-1)\left(\frac{n}{d}\right).

So we need to show that (i) every one of the integers above is a solution, (ii) that they are incongruent solutions (mod n), (iii) and that any of the infinitely many solutions to ax\equiv b \pmod{n} is be congruent to one of the solutions above (mod n).

NOTE: Since we know there is a solution, we are letting x_0 be one of them for the rest of the proof.

(i) Every integer of the form x_0 + k\left(\frac{n}{d}\right) is a solution to ax\equiv b \pmod{n}.

We’ll use that x_0 is a solution to see that x_0 + k\left(\frac{n}{d}\right) is a solution too,

a\Big(x_0 + k\left(\frac{n}{d}\right)\Big)\equiv ax_0 + k\left(\frac{an}{d}\right) \pmod{n}\\ \textit{ }\qquad\qquad\;\;\;\;\;\;\;\equiv ax_0 + k\left(\frac{an}{d}\right) \pmod{n}\\\textit{ }\qquad\qquad\;\;\;\;\;\;\; \equiv b +nk\left(\frac{a}{d}\right)\;\;\;\,\pmod{n} \\ \textit{ }\qquad\qquad\;\;\;\;\;\;\; \equiv b\qquad\qquad\;\;\;\;\, \pmod{n}

Where we used that d\mid a implies that \frac{a}{d} is an integer. So, we see that every x_0 + k\left(\frac{n}{d}\right) is a solution.

(ii) They are all incongruent (mod n).

Let x_0 + k\left(\frac{n}{d}\right) and x_0 + t\left(\frac{n}{d}\right) be two solutions from our set such that 0\leq k\leq t\leq d-1 and

x_0 + k\left(\frac{n}{d}\right) \equiv x_0 + t\left(\frac{n}{d}\right) \pmod{n}.

With a little rearranging we deduce the following,

t\left(\frac{n}{d}\right) \equiv k\left(\frac{n}{d}\right) \pmod{n}\\ t\left(\frac{n}{d}\right) - k\left(\frac{n}{d}\right) =ns

Where s \geq 0 and is an integer. Canceling the n and moving the d over to the right,

t - k =ds.

Since we chose 0\leq k\leq t\leq d-1 it must be that 0\leq t - k \leq d-1. Or, that 0\leq ds < d. This implies that t - k =ds = 0 since s\geq 0 and is an integer. Therefore t = k and hence our two solutions where really the same solution.

(iii) Every solution (mod n) is in our family of solutions.

Let X be a solutions to ax\equiv b \pmod{n}. By our Corollary (Solution Form), it’s of the form:

X=x_0 + t\left(\frac{n}{d}\right).

If 0\leq t \leq d-1 then X is in our solution set, so let’s assume that t is outside of this interval. By the division algorithm we write t = qd +r for 0\leq r< d. Thus,

X=x_0 + (qd+r)\left(\frac{n}{d}\right)\\ \textit{ }\;\;=x_0 + qn +r\left(\frac{n}{d}\right)\\ \textit{ }\;\; \equiv x_0 + r\left(\frac{n}{d}\right)\pmod{n}.

And since 0\leq r< d, we conclude that X is in our solution set.

\square

We’re ready for the pièce de résistance.

The Chinese Remainder Theorem

Theorem: (The Chinese Remainder Theorem) Let n_1,n_2,\cdots, n_k be positive intergers that are pairwise relatively prime (ie \gcd{(n_i,n_j)}=1 when i\neq j). Then the system of linear congruences:

x\equiv a_1 \pmod{n_1}

x\equiv a_2 \pmod{n_2}

\vdots

x\equiv a_k \pmod{n_k}

has a unique soltion \pmod{N} where N:=n_1n_2\cdots n_k.

Proof: We’ll not only show that there is such a solution, we will also construct an expression for the solution!

Let N_t:=\frac{n_1n_2\cdots n_k}{n_t}=\frac{N}{n_t} for 1\leq t\leq k. Observe that \gcd{(N_t,n_i)}=1 for all i\neq t. Therefore, by our first theorem there is a solution to the linear congruence,

N_tx\equiv 1 \pmod{n_t}

for all 1\leq t\leq k. Denote this solution x_t. We claim that,

X = a_1N_1x_1 + a_2N_2x_2 + \cdots a_kN_kx_k

is our solution to the system of congruences. To see this, observe that,

X=a_1N_1x_1 + a_2N_2x_2 + \cdots a_iN_ix_i \cdots a_kN_kx_k\\\textit{ }\;\; \equiv 0 + 0 + \cdots + \cdots +a_iN_ix_i +\cdots+ 0 \\\textit{ }\;\; \equiv a_iN_ix_i \pmod{n_i}

Recall we already showed that \gcd{(N_t,n_i)}=1 for all i\neq t, so that N_t\equiv 0 \pmod{n_i} for i\neq t.

We chose x_i so that N_ix_i\equiv 1 \pmod{n_i}. Thus,

X\equiv a_iN_ix_i\equiv a_i \pmod{n_i}

This is true for all i and therefore X is our desired solution.

All we have left to do is show that X is unique \pmod{N}. To this end, let \overline{X} be another solution to the set of congruences. Then, for any i

X\equiv a_i\equiv \overline{X} \pmod{n_i}

Therefore, X- \overline{X}=n_i m for all i. Recall that all the n_1,n_2,\cdots, n_k are pairwise relatively prime so that \gcd{(n_i,n_j)}=1 when i\neq j. Let’s look at when i=1 and i=2. Then,

X\equiv a_1\equiv \overline{X} \pmod{n_1} implying X- \overline{X}=n_1 m_1

X\equiv a_2\equiv \overline{X} \pmod{n_2}

The second line implies that n_2\mid (X- \overline{X}) or n_2\mid n_1m_1 from the first line. And by Euler’s Lemma (see footnote1) n_2\mid m_1. Thus, m_1 = n_2m_2. But we can apply this again with n_3 to get n_3\mid (X- \overline{X}) implying both n_3\mid n_1n_2m_2 and n_3\mid m_2 by Euler’s Lemma. Thus, m_2 = n_3m_3 and X- \overline{X}=n_1n_2n_3 m_3. We’ll do this for all n_i and get,

X- \overline{X}=n_1n_2n_3 \cdots n_k m_k = Nm_k.

Hence,

X\equiv \overline{X}\pmod{N}

as we set out to show.

\square

Closing Remarks

The Chinese Remainder theorem is a beautiful result that has been known for thousands of years! See Harvard’s: Historical development of the Chinese remainder theorem and Britannica: Chinese Remainder Theorem. I hope you had as much fun as I did!

Next time we will do an example of a problem that requires The Chinese Remainder theorem.

Footnote:

  1. Euler’s Lemma: Let a , b, and c be integers. If c\mid ab and \gcd{(a,c)}=1 . Then, c\mid b . ↩︎

Leave a comment