Chinese remainder theorem

Imagine having a system of congruence equations, for example x\equiv 3 mod 5, x\equiv 0 mod 6 and x\equiv 1 mod 7. We wonder whether such system always has a solution. If so, what is the smallest of them? Do the solutions have something in common? The Chinese remainder theorem (CRT) – a tool for answering such questions, has been known to mankind for a very long time.

Sources:

Theory:

Let R and S be two rings. Recall that a map f:R\to S is a ring homomorphism, if for all x,y\in R it holds that:

  • f(x+y)=f(x)+f(y);
  • f(x\cdot y)=f(x)\cdot f(y);
  • f(1)=1.

Bijective homomorphism is called an isomorphism.

General lemma: f:R\to S is a ring isomorphism if and only if f is a ring homomorphism and there exists another ring homomorphism g:S\to R, such that f\circ g=id_S and g\circ f=id_R. Note that the assumption of f to be a homomorphism can be left out.

Lemma: If d|n, then a formula a\mapsto(a mod d) yields a homomorphism of \mathbb{Z}_n\to \mathbb{Z}_d.

Chinese remainder theorem: Let n\in\mathbb{N} and write n=n_1\cdot...\cdot n_r, where n_1,...,n_r\in\mathbb{N} are pairwise coprime. A map \varphi: \mathbb{Z}_n\to\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times...\times...\mathbb{Z}_{n_r} given by a\mapsto (a mod n_1, a mod n_2,...,a mod n_r) is a ring isomorphism. Moreover, a map \psi:\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\times...\times...\mathbb{Z}_{n_r}\to\mathbb{Z}_n; \psi(a_1,a_2,...,a_r)=\sum_{i=1}^{r}a_i\cdot k_i\cdot m_i, where m_i=\frac{n}{n_i}=n_1\cdot n_2\cdot...\cdot n_{i-1}\cdot n_{i+1}\cdot...\cdot n_r, and k_1,...,k_r\in\mathbb{Z} are some integers satisfying an equation \sum_{i=1}^{r}k_i\cdot m_i=1, is an inverse isomorphism.

Consequences

  • Let 2\leq n\in\mathbb{N} and let n=p_1^{e_1}\cdot...\cdot p_r^{e_r} be a prime decomposition. Then \mathbb{Z}_n\cong\mathbb{Z}_{p_1^{e_1}}\times...\times\mathbb{Z}_{p_r^{e_r}}.
  • Suppose \varphi yields a ring isomorphism of R and R_1\times...\times R_k. Then the restriction of \varphi to R^* yields a group isomorphism of R^* and R_1^*\times...\times R_k^*.
  • Let n\in\mathbb{N}, n=n_1\cdot...\cdot n_r, where n_1,...,n_r\in\mathbb{N} are pairwise coprime. Then \mathbb{Z}_n^*\cong \mathbb{Z}_{n_1}^*\times\mathbb{Z}_{n_2}^*\times...\times...\mathbb{Z}_{n_r}^*. Since |\mathbb{Z}_n^*=\varphi(n)|, we immediately receive that \varphi(n)=\varphi(n_1)\cdot...\cdot\varphi(n_r).

Examples

Example 1:

A general sent 1000 soldiers to fight for him in a great battle. After the battle, he wanted to know how many of them survived. He told them to form groups of 11, and one guy was left out. Then he told them to form groups of 12, and then 3 guys were left out. Finally, he told them to form groups of 13 and 4 soldiers were left out this time. Can you determine how many soldiers survived?      

Solution:

We need to rewrite the story in terms of congruences. Let x denote the number of soldiers who survived. We receive:

  • x\equiv 1 mod 11;
  • x\equiv 3 mod 12;
  • x\equiv 4 mod 13.

From the first equation we see that x=11\cdot k+1. Let’s plug this expression into the second equation. We get that 11\cdot k+1\equiv 3 mod 12, what is equivalent to 11\cdot k\equiv 2 mod 12, and that is equivalent to k\equiv 10 mod 12, so k=12\cdot l+10. Hence, x=11\cdot(12\cdot l+10)+1=132\cdot l+111. Plugging this into the last equation gives us 132\cdot l+111\equiv 4 mod 13\iff 2l\equiv 10 mod 13\iff l\equiv 5 mod 13. Therefore, l=13\cdot m+5, and finally, x=132\cdot(13\cdot m+5)+111, so x=1716\cdot m+771. Since there were 1000 soldiers before the battle, there are 771 soldiers who survivied.

Note:

The main idea of Chinese remainder theorem is the following: if the modules n_1,...,n_r are pairwise coprime, then for any system of congruences x\equiv a_1 mod n_1,…,x\equiv a_r mod n_r there exists a unique solution x\in\{0,...,n_1\cdot...\cdot n_r-1\}. But what happens if n_1,...,n_r are not pairwise coprime? Does the theorem still holds? Are there more or less solutions? The following example demonstrates one possible case.

Example 2:

Solve the following system of congruence equations:

  • x\equiv 2 mod 4;
  • x\equiv 5 mod 6;
  • x\equiv 1 mod 7.

Solution:

There are several ways of solving this system. Perhaps the simpliest is this: from the first equation we see that x=4\cdot k+2, and hence, x is even. However, the second equation implies x=6\cdot l+5, so it must be odd, a contradiction. Therefore, the system has no solution.

Example 3:

What is \mathbb{Z}_6^* isomorphic to?

Solution:

Using the first and the second consequences of CRT we immediately get that

    \[\mathbb{Z}_6^*\cong \mathbb{Z}_2^*\times\mathbb{Z}_3^*\cong\mathbb{Z}_1\times\mathbb{Z}_2\cong\mathbb{Z}_2.\]


Problems:

Problem 1:

A group of 19 pirates stole a chest full of gold coins. They tried to share it equally and divided them into 19 equal parts, but there were 16 coins left. So they started to fight for those and one pirate got killed. So they tried to divide the coins equally again, but there 14 coins left this time. Another fight, another pirate down. So, the rest of the pirates tried to split the coins equally once more, and it worked. The question is: what is the least possible number of coins that pirates may have stolen?

Problem 2:

Solve the following system of equations:

  • x\equiv 18 mod 19;
  • x\equiv 20 mod 21;
  • x\equiv 21 mod 22;
  • x\equiv 22 mod 23.

Problem 3:

What is \mathbb{Z}_{12}^* isomorphic to?

Leave a Reply

Your email address will not be published. Required fields are marked *