Chinese Remainder Theorem (CRT): if n₁,...,nₖ are pairwise coprime, the system x≡a₁(mod n₁),...,x≡aₖ(mod nₖ) has a unique solution mod N=n₁·...·nₖ. Solution: x = Σaᵢ·Nᵢ·yᵢ (mod N) where Nᵢ=N/nᵢ and yᵢ=Nᵢ⁻¹(mod nᵢ).
How to Use
Enter congruences:
- a, n: Each x ≡ a (mod n)
- Solution: Unique x mod N
- Steps: CRT computation
Algorithm
1. Verify pairwise coprimality. 2. Compute N=Πnᵢ. 3. For each i: Nᵢ=N/nᵢ, find yᵢ=Nᵢ⁻¹(mod nᵢ). 4. x = Σaᵢ·Nᵢ·yᵢ (mod N).
Applications
- RSA encryption (combining mod p, mod q)
- Fast Fourier Transform (NTT)
- Calendar computations
- Parallel computation
Step-by-Step Instructions
- 1Enter equations.
- 2Check coprimality.
- 3Compute solution.
- 4Verify all congruences.
- 5See steps.