Imagine having a system of congruence equations, for example mod , mod and mod . 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 and be two rings. Recall that a map is a ring **homomorphism**, if for all it holds that:

- ;
- ;
- .

Bijective homomorphism is called an **isomorphism**.

**General lemma:** is a ring isomorphism if and only if is a ring homomorphism and there exists another ring homomorphism , such that and . Note that the assumption of to be a homomorphism can be left out.

**Lemma:** If , then a formula mod yields a homomorphism of

**Chinese remainder theorem:** Let and write , where are pairwise coprime. A map given by mod mod mod is a ring isomorphism. Moreover, a map where and are some integers satisfying an equation , is an inverse isomorphism.

## Consequences

- Let and let be a prime decomposition. Then
- Suppose yields a ring isomorphism of and . Then the restriction of to yields a group isomorphism of and .
- Let , where are pairwise coprime. Then Since , we immediately receive that

## Examples

### Example 1:

A general sent 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 , and one guy was left out. Then he told them to form groups of , and then guys were left out. Finally, he told them to form groups of and 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 denote the number of soldiers who survived. We receive:

- mod ;
- mod ;
- mod .

From the first equation we see that . Let’s plug this expression into the second equation. We get that mod , what is equivalent to mod , and that is equivalent to mod , so . Hence, . Plugging this into the last equation gives us mod mod mod . Therefore, , and finally, , so . Since there were soldiers before the battle, there are soldiers who survivied.

### Note:

The main idea of Chinese remainder theorem is the following: if the modules are pairwise coprime, then for any system of congruences mod ,…, mod there exists a unique solution . But what happens if 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:

- mod ;
- mod ;
- mod .

### Solution:

There are several ways of solving this system. Perhaps the simpliest is this: from the first equation we see that , and hence, is even. However, the second equation implies , so it must be odd, a contradiction. Therefore, the system has no solution.

### Example 3:

What is isomorphic to?

### Solution:

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

## Problems:

### Problem 1:

A group of pirates stole a chest full of gold coins. They tried to share it equally and divided them into equal parts, but there were 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 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:

- mod ;
- mod ;
- mod ;
- mod .

### Problem 3:

What is isomorphic to?