Chinese remainder theorem

For pairwise coprime positive integers

m_{1}, \dots, m_{r}

, reduction induces a ring isomorphism

Z / (m_{1} \dots m_{r}) Z ≅ \prod_{j = 1}^{r} Z / m_{j} Z .

Equivalently, every list of residue classes modulo the

m_{j}

has a unique simultaneous residue class modulo their product.

Table of contents

Prime-power fraction decomposition ( $a / b = n + \sum_{i} q_{i} / p_{i}^{n_{i}}$ )

For a positive integer

b = \prod_{i} p_{i}^{n_{i}}

, every rational number

a / b

has a unique representation

a / b = n + \sum_{i} q_{i} / p_{i}^{n_{i}}

with

n \in Z

and

0 \leq q_{i} < p_{i}^{n_{i}}

. With

B_{i} = b / p_{i}^{n_{i}}

, the coefficients satisfy

q_{i} \equiv a B_{i}^{- 1} (mod p_{i}^{n_{i}})

. Their existence and uniqueness use modular multiplicative inverses and the Chinese remainder theorem.

Lagrange theorem for polynomial congruences

A nonzero polynomial of degree

d

over a field has at most

d

roots. In particular, if a polynomial congruence

f (x) \equiv 0 (mod p)

has degree

d

and not all coefficients are divisible by the prime

p

, it has at most

d

incongruent solutions modulo

p

.

Chinese remainder theorem for unit groups

m, n

, reduction gives

(Z / mn Z)^{\times} ≅ (Z / m Z)^{\times} \times (Z / n Z)^{\times}

.

Multiplicative order under the Chinese remainder theorem

The order of a unit modulo a product of coprime moduli is the least common multiple of the orders of its components.

 Ancestors (2)

 Incoming links (111)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Chinese remainder theorem by

Wikipedia Bot  1

The Chinese Remainder Theorem (CRT) is a result in number theory that provides a way to solve systems of simultaneous congruences with different moduli. It states that if you have several congruences with pairwise coprime moduli, there exists a unique solution modulo the product of those moduli. ### Formulation If \( n_1, n_2, \ldots, n_k \) are pairwise coprime integers (i.e.

 Read the full article

  See all articles in the same topic Create my own version