chinese remainder theorem

Work in Progress

Concept

Chinese remainder theorem

Chinese remainder theorem. For pairwise coprime , every system has exactly one solution modulo .

  • layman explanation: compatible remainders for coprime moduli combine into one number, unique across one full product-sized cycle.

Proof. Put . Since , choose with and define

For fixed , every term with is divisible by , while , so

If solve the system, then for every . Pairwise coprimality gives

Application

Pohlig-Hellman computes for , then the constructive formula above recovers the unique discrete logarithm .