|
|
|
Viewing Version
3
of
'Chinese remainder theorem'
|
[ view 'Chinese remainder theorem'
|
back to history
]
| Title of object: |
Chinese remainder theorem |
| Canonical Name: |
ChineseRemainderTheorem |
| Type: |
Theorem |
| Created on: |
2001-11-16 00:26:46 |
| Modified on: |
2004-04-08 18:49:06 |
| Classification: |
msc:11D79 |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic} |
Content:
Suppose we have a set of $n$ congruences of the form
\[ \begin{array}{ccc}
x & \equiv & a_1 \pmod{p_1} \\
x & \equiv & a_2 \pmod{p_2} \\
& \vdots &
x & \equiv & a_n \pmod{p_n} \\
\end{array} \]
where $p_1, p_2 \dots p_n$ are relatively prime. Let
$$P = \prod_{i=1}^n p_i$$
and, for all $i \in \mathbb{N}$ ($1 \leq i \leq n$), let $y_i$ be an integer that satisfies
$$y_i\frac{P}{p_i} \equiv 1 \pmod{p_i}$$
Then one solution of these congruences is
$$x_0 = \sum_{i=1}^n a_iy_i\frac{P}{p_i}$$
Any $x \in \mathbb{Z}$ satisfies the set of congruences if and only if it satifies
$$x \equiv x_0 \pmod{P}$$
The Chinese remainder theorem is said to have been used to count the size of the ancient Chinese armies (i.e., the soldiers would split into groups of 3, then 5, then 7, etc, and the ``leftover'' soldiers from each grouping would be counted). |
|
|
|
|
|
