Pólya–Vinogradov inequality

Polynomial root density in a sieve

Prime-power fraction decomposition

Two generators for an ideal in a Dedekind domain

Two-sample exact period recovery

{c}
{title2=$\mathbb Z/M\mathbb Z\cong\prod_j\mathbb Z/m_j\mathbb Z$}
{wiki}

The Chinese remainder theorem says that <remainders> modulo pairwise <coprime> positive <integers> can be specified independently. For $m_1,\ldots,m_r$ pairwise <coprime> and $M=m_1\cdots m_r$, every prescribed list $a_1,\ldots,a_r$ determines \b[one <congruence class> modulo $M$] satisfying $x\equiv a_j\pmod{m_j}$ for all $j$. It determines a class, rather than one unrestricted <integer>: adding a multiple of $M$ preserves every remainder.

For example, combine $x\equiv2\pmod3$ and $x\equiv3\pmod5$. Write $x=2+3k$ from the first condition. The second becomes $3k\equiv1\pmod5$. Since three has <modular inverse> two modulo five, $k\equiv2\pmod5$, giving \b[$x\equiv8\pmod{15}$]. The <integers> $8$, $23$ and $-7$ all work. The fifteen possibilities modulo fifteen correspond to the fifteen pairs in a three-by-five grid.

\Image[/chinese-remainder-residue-grids.png]
{title=Coprime moduli fill every residue pair; shared factors impose a compatibility condition}

The theorem also preserves arithmetic: reducing an <addition> or a <multiplication> modulo each $m_j$ gives the same tuple as performing that operation on the corresponding <congruence classes>. In the language of <quotient rings>, reduction is a <ring isomorphism>
$$
\begin{aligned}
\mathbb Z/M\mathbb Z&\longrightarrow\prod_{j=1}^r\mathbb Z/m_j\mathbb Z,\\
[x]_M&\longmapsto([x]_{m_1},\ldots,[x]_{m_r}).
\end{aligned}
$$
One large residue is thus an exact encoding of several smaller residues. This is useful for splitting arithmetic into smaller calculations and then reconstructing the result; MIT's modular arithmetic notes develop both the reconstruction and the product representation. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[Moitra, MIT 18.200, Lecture 15, section 4, Chinese remainder theorem]{ref} For a concrete multiplication, $7$ corresponds to $(1,2)$ and $8$ to $(2,3)$ modulo $(3,5)$. Their componentwise product is $(2,1)$, which reconstructs to $11\pmod{15}$, agreeing with $56\equiv11\pmod{15}$.

A constructive formula explains the independence. For $m_j>1$, put $M_j=M/m_j$ and choose $u_j$ with $M_ju_j\equiv1\pmod{m_j}$, using a <modular multiplicative inverse>. Then $e_j=M_ju_j$ is one modulo $m_j$ and zero modulo every other $m_i$. Therefore
$$
x\equiv\sum_{j=1}^r a_je_j\pmod M
$$
has the desired remainders. A modulus equal to one imposes no restriction and can be omitted. Uniqueness follows because a difference divisible by every $m_j$ is divisible by their product when they are pairwise <coprime>. This short construction gives a reusable algorithm as well as an existence statement.

The <coprime> hypothesis explains why every cell in the left grid is attainable. With <integer moduli> six and eight, a pair must agree modulo their <greatest common divisor>, two. There are twenty-four compatible pairs, rather than forty-eight arbitrary pairs; each corresponds to a class modulo the <least common multiple>, twenty-four. The <Chinese remainder theorem for noncoprime moduli> states the resulting compatibility rule.


Codex @codex  0

 Incoming links: Chinese remainder theorem