Difference between revisions of "Chinese Remainder Theorem"

Latest revision as of 13:57, 6 May 2023

The Chinese Remainder Theorem is a number theoretic result.

Theorem

Formally stated, the Chinese Remainder Theorem is as follows:

Let $m$ be relatively prime to $n$ . Then each residue class mod $mn$ is equal to the intersection of a unique residue class mod $m$ and a unique residue class mod $n$ , and the intersection of each residue class mod $m$ with a residue class mod $n$ is a residue class mod $mn$ .

This means that if we have $b \equiv c \pmod {mn}$ we can deduce that $b \equiv c \pmod{m}$ and $b \equiv c \pmod{n}.$

Simply stated:

Suppose you wish to find the least number $x$ which leaves a remainder of:

$\begin{aligned} &y_{1} \text{ when divided by } &d_{1}\\ &y_{2} \text{ when divided by } &d_{2}\\ &\vdots &\vdots\\ &y_{n} \text{ when divided by } & d_{n}\\ \end{aligned}$

such that $d_{1}$ , $d_{2}$ , ... $d_{n}$ are all relatively prime. Let $M = d_{1}d_{2} \cdots d_{n}$ , and $b_{i} = \frac{M}{d_{i}}$ . Now if the numbers $a_{i}$ satisfy:

$a_{i}b_{i} \equiv 1 \pmod {d_{i}}$

for every $1 \leq i \leq n$ , then a solution for $x$ is:

$x = \sum_{i=1}^n a_{i}b_{i}y_{i} \pmod M$

Proof

If $a \equiv b \pmod{mn}$ , then $a$ and $b$ differ by a multiple of $mn$ , so $a \equiv b \pmod{m}$ and $a \equiv b \pmod{n}$ . This is the first part of the theorem. The converse follows because $a$ and $b$ must differ by a multiple of $m$ and $n$ , and $\mbox{lcm}(m,n) = mn$ . This is the second part of the theorem.

Applicability

Much like the Fundamental Theorem of Arithmetic, many people seem to take this theorem for granted before they consciously turn their attention to it. Its ubiquity derives from the fact that many results can be easily proven mod (a power of a prime), and can then be generalized to mod $m$ using the Chinese Remainder Theorem. For instance, Fermat's Little Theorem may be generalized to the Fermat-Euler Theorem in this manner.

General Case: the proof of the general case follows by induction to the above result (k-1) times.

Solving a system of congruences using CRT

In order to solve a system of n congruences, it is typical to solve the first two, then combine that with the third, and so on. So, it suffices to know how solve a system of 2 congruences.

Let the system be (where $m$ and $n$ are relatively coprime):

$x\equiv a \mod m$ $x\equiv b \mod n$

Then if we find one value $k$ such that $x=k$ satisfies the system, then the solution set consists of $x\equiv k \mod mn$ . To find such $k$ , set $x=cm+a=dn+b$ . Then, find $c, d$ that satisfy the equality. This is usually easier than brute forcing for $k$ .

Let's take an example: $x\equiv 1 \mod 2$ $4x\equiv 3 \mod 5$ First simplify the second equation to $x\equiv 3\cdot 4 \equiv 2 \mod 5$ using modular inverses. So we have: $x\equiv 1 \mod 2$ $x\equiv 2 \mod 5$ Then let $x=2a+1=5b+2$ . A clear solution $a,b$ for this is $a=3, b=1$ . Then, $x=7$ is one solution to the system, so $x\equiv 7 \mod 10$ is the set of all solutions.

If $m$ and $n$ are not relatively prime, then let $\gcd(m, n)=g$ . We split the system as follows: $x\equiv a \mod \frac{m}{g}$ $x\equiv a \mod g$ $x\equiv b \mod g$ $x\equiv b \mod \frac{n}{g}$ Then, we must check that $a\equiv b\mod g$ . If so, simply ignore the 3rd congruence. Now, we have: $x\equiv a \mod \frac{m}{g}$ $x\equiv a \mod g$ $x\equiv b \mod \frac{n}{g}$ Now we have a system of 3 congruences, which we can solve for. If $\gcd(\frac{m}{g}, g)$ is not $1$ , then repeat the decomposition. Essentially, decompose until we get a system of pairwise relatively prime congruences. Then solve.

Extended version of the theorem

Suppose one tried to divide a group of fish into $2$ , $3$ and $4$ parts instead and found $1$ , $1$ and $2$ fish left over, respectively. Any number with remainder $1$ mod $2$ must be odd and any number with remainder $2$ mod $4$ must be even. Thus, the number of objects must be odd and even simultaneously, which is a contradiction. Thus, there must be restrictions on the numbers $a_1,\dots,a_n$ to ensure that at least one solution exists. It follows that:

The solution exists if and only if $a_i\equiv a_j\mod \gcd(m_i,m_j)$ for all $i,j$ where $\gcd$ stands for the greatest common divisor. Moreover, in the case when the problem is solvable, any two solutions differ by some common multiple of $m_1,\ldots,m_n$ . (the extended version).

Discussion

Here is an AoPS thread in which the Chinese Remainder Theorem is discussed and implemented.

@@ Line 1: / Line 1: @@
 The '''Chinese Remainder Theorem''' is a [[number theory | number theoretic]] result.
+== Theorem ==
-==History==
+Formally stated, the Chinese Remainder Theorem is as follows:
-When the ancient Chinese army was at its peak, it was said that the emperor developed a way to count the soldiers.  Rather than count his hordes one man at a time, he developed a system.  He would have his soldiers divide into groups of 3, and count the men who didn't have a group.  He would then do groups of 5, etc.  Eventually, using these remainders, he could calculate the size of his army using a technique we now call the Chinese Remainder Theorem.
+Let <math>m</math> be [[relatively prime]] to <math>n</math>.  Then each [[residue class]] mod <math>mn</math> is equal to the [[intersection]] of a unique residue class mod <math>m</math> and a unique residue class mod <math>n</math>, and the intersection of each residue class mod <math>m</math> with a residue class mod <math>n</math> is a residue class mod <math>mn</math>.
+This means that if we have <math>b \equiv c \pmod {mn}</math> we can deduce that <math>b \equiv c \pmod{m}</math> and <math>b \equiv c \pmod{n}.</math>
+Simply stated:
+Suppose you wish to find the least number <math>x</math> which leaves a remainder of:
+<center>
+<math> \begin{aligned} &y_{1} \text{ when divided by } &d_{1}\\
+&y_{2} \text{ when divided by } &d_{2}\\
+&\vdots &\vdots\\
+&y_{n} \text{ when divided by } & d_{n}\\ \end{aligned} </math>
+</center>
+such that <math>d_{1}</math> ,  <math>d_{2}</math> , ... <math>d_{n}</math> are all relatively prime.
+Let <math>M = d_{1}d_{2} \cdots d_{n}</math>, and <math>b_{i} = \frac{M}{d_{i}}</math>.
+Now if the numbers <math>a_{i}</math> satisfy:
+<center>
+<math>a_{i}b_{i} \equiv 1 \pmod {d_{i}} </math>
+</center>
+for every <math>1 \leq i \leq n</math>, then a solution for <math>x</math> is:
+<center>
+<math>x = \sum_{i=1}^n a_{i}b_{i}y_{i} \pmod M</math>
+</center>
 == Proof ==
-If <math>a \equiv b \pmod{mn}</math>, then <math>a</math> and <math>b</math> clearly differ by a multiple of <math>mn</math>, so <math>a \equiv b \pmod{m}</math> and <math>a \equiv b \pmod{n}</math>.  This is the first part of the theorem.  The converse follows because <math>a</math> and <math>b</math> must differ by a multiple of <math>m</math> and <math>n</math>, and <math>\mbox{lcm}(m,n) = mn</math>.  This is the second part of the theorem.
+If <math>a \equiv b \pmod{mn}</math>, then <math>a</math> and <math>b</math> differ by a multiple of <math>mn</math>, so <math>a \equiv b \pmod{m}</math> and <math>a \equiv b \pmod{n}</math>.  This is the first part of the theorem.  The converse follows because <math>a</math> and <math>b</math> must differ by a multiple of <math>m</math> and <math>n</math>, and <math>\mbox{lcm}(m,n) = mn</math>.  This is the second part of the theorem.
 == Applicability ==
-Much like the [[Fundamental Theorem of Arithmetic]], many people seem to take this theorem for granted before they consciously turn their attention to it.  It ubiquity derives from the fact that many results can be easily proven mod (a power of a prime), and can then be generalized to mod <math>m</math> using the Chinese Remainder Theorem.  For intance, [[Fermat's Little Theorem]] may be generalized to the [[Fermat-Euler Theorem]] in this manner.  Its application in [[problem-solving]] is similar.
+Much like the [[Fundamental Theorem of Arithmetic]], many people seem to take this theorem for granted before they consciously turn their attention to it.  Its ubiquity derives from the fact that many results can be easily proven mod (a power of a prime), and can then be generalized to mod <math>m</math> using the Chinese Remainder Theorem.  For instance, [[Fermat's Little Theorem]] may be generalized to the [[Fermat-Euler Theorem]] in this manner.
+'''General Case''': the proof of the general case follows by induction to the above result (k-1) times.
+==Solving a system of congruences using CRT==
+In order to solve a system of n congruences, it is typical to solve the first two, then combine that with the third, and so on. So, it suffices to know how solve a system of 2 congruences.
+Let the system be (where <math>m</math> and <math>n</math> are relatively coprime):
+<cmath>x\equiv a \mod m</cmath>
+<cmath>x\equiv b \mod n</cmath>
+Then if we find one value <math>k</math> such that <math>x=k</math> satisfies the system, then the solution set consists of <math>x\equiv k \mod mn</math>. To find such <math>k</math>, set <math>x=cm+a=dn+b</math>. Then, find <math>c, d</math> that satisfy the equality. This is usually easier than brute forcing for <math>k</math>.
-'''General Case''': the proof of the general case follows by repeatedly applying to above result (k-1) times.
+Let's take an example:
+<cmath>x\equiv 1 \mod 2</cmath>
+<cmath>4x\equiv 3 \mod 5</cmath>
+First simplify the second equation to <math>x\equiv 3\cdot 4 \equiv 2 \mod 5</math> using modular inverses. So we have:
+<cmath>x\equiv 1 \mod 2</cmath>
+<cmath>x\equiv 2 \mod 5</cmath>
+Then let <math>x=2a+1=5b+2</math>. A clear solution <math>a,b</math> for this is <math>a=3, b=1</math>. Then, <math>x=7</math> is one solution to the system, so <math>x\equiv 7 \mod 10</math> is the set of all solutions.
+If <math>m</math> and <math>n</math> are not relatively prime, then let <math>\gcd(m, n)=g</math>. We split the system as follows:
+<cmath>x\equiv a \mod \frac{m}{g}</cmath>
+<cmath>x\equiv a \mod g</cmath>
+<cmath>x\equiv b \mod g</cmath>
+<cmath>x\equiv b \mod \frac{n}{g}</cmath>
+Then, we must check that <math>a\equiv b\mod g</math>. If so, simply ignore the 3rd congruence. Now, we have:
+<cmath>x\equiv a \mod \frac{m}{g}</cmath>
+<cmath>x\equiv a \mod g</cmath>
+<cmath>x\equiv b \mod \frac{n}{g}</cmath>
+Now we have a system of 3 congruences, which we can solve for. If <math>\gcd(\frac{m}{g}, g)</math> is not <math>1</math>, then repeat the decomposition. Essentially, decompose until we get a system of pairwise relatively prime congruences. Then solve.
 ==Extended version of the theorem==
-Suppose one tried to divide a group of objects into <math>2</math>, <math>3</math> and <math>4</math> parts instead and found <math>1</math>, <math>1</math> and <math>2</math> fish left over, respectively. One can show this to be impossible, because any number giving remainder <math>1</math> modulo <math>2</math> must be [[odd integer | odd]] and any number giving remainder <math>2</math> modulo <math>4</math> must be [[even integer | even]]. Thus, the number of objects must be odd and even simultaneously, which is absurd. Thus, there must be some restrictions on the numbers <math>a_1,\dots,a_n</math> to ensure that at least one solution exists.  It turns out (and this is the extended version of the theorem) that
+Suppose one tried to divide a group of fish into <math>2</math>, <math>3</math> and <math>4</math> parts instead and found <math>1</math>, <math>1</math> and <math>2</math> fish left over, respectively. Any number with remainder <math>1</math> mod <math>2</math> must be [[odd integer | odd]] and any number with remainder <math>2</math> mod <math>4</math> must be [[even integer | even]]. Thus, the number of objects must be odd and even simultaneously, which is a contradiction. Thus, there must be restrictions on the numbers <math>a_1,\dots,a_n</math> to ensure that at least one solution exists.  It follows that:
-''The solution exists if and only if <math>a_i\equiv a_j\mod \gcd(m_i,m_j)</math> for all <math>i,j</math> where <math>\gcd</math> stands for the [[greatest common divisor]]. Moreover, in the case when the problem is solvable, any two solutions differ by some [[common multiple]] of <math>m_1,\ldots,m_n</math>.''
+''The solution exists if and only if <math>a_i\equiv a_j\mod \gcd(m_i,m_j)</math> for all <math>i,j</math> where <math>\gcd</math> stands for the [[greatest common divisor]]. Moreover, in the case when the problem is solvable, any two solutions differ by some [[common multiple]] of <math>m_1,\ldots,m_n</math>.'' (the extended version).
+==See Also==
+*[[Modular arithmetic/Introduction]]
+*[[Chicken McNugget Theorem]]
 ==Discussion==
@@ Line 26: / Line 82: @@
 [[Category:Number theory]]
+[[Category:Theorems]]

Page

Toolbox

Search