Modulo Factorization Theorem

Modulo Factorization Theorem

Let $N = n_{1} \dots n_{r}$ be the factorization of N into pair-wise co-prime factors. Then the congruence $x \equiv a (mod N)$ is equivalent to the following system of equations:
$x x x \equiv a (mod n_{1}) \equiv a (mod n_{2}) ⋮ \equiv a (mod n_{r})$

Proof

Since $n_{i} ∣ N$ for $i \in [r]$ and $x \equiv a (mod N) ⟺ N ∣ (x - a)$ , by transitivity, $n_{i} ∣ (x - a) ⟺ x \equiv a (mod d_{i})$ giving us our system of equations:

$x x x \equiv a (mod n_{1}) \equiv a (mod n_{2}) ⋮ \equiv a (mod n_{r})$

Math Matrix

Explorer

Modulo Factorization Theorem

Graph View

Backlinks