Last updated April 10, 2022

Status: Tags: #archivedCards/macm101/numbertheory Links: Linear Congruences

Chinese Remainder Theorem

Principles

Theorem ?

Steps for CRT ?

• For each x, multiply by other modulo m’s
• Next, try to use that number to satisfy the x’s own modular divison
  • Multiply if needed
• Add the numbers together, mod it by the product of all mod’s

Prove Chinese Remainder Theorem ?

Examples

Without chinese remainder theorem, find the solution of the system of the following congruences:

• x ≡ 2 (mod 3) = $x_1$
• x ≡ 3 (mod 5) = $x_2$
• x ≡ 2 (mod 7) = $x_3$ ?

Backlinks

1

list from Chinese Remainder Theorem AND !outgoing(Chinese Remainder Theorem)

References:

Created:: 2021-12-02 16:03