✳flâneur — a map of the web's best reading

Number Theory - The Chinese Remainder Theorem

crypto.stanford.edu · 861 words · saved by 1 readers

for 𝑥 . If we have a solution 𝑦 , then 𝑦 + 35 is also a solution. So we only need to look for solutions modulo 35 . By brute force, we find the only solution is 𝑥 = 17 ( mod 35 ) . For any system of equations like this, the Chinese Remainder Theorem tells us there is always a unique solution up to a certain modulus, and describes how to find the solution efficiently. Theorem: Let 𝑝 , 𝑞 be coprime. Then the system of equations has a unique solution for 𝑥 modulo 𝑝 𝑞 . The reverse direction is trivial: given 𝑥 ∈ 𝑍 𝑝 𝑞 , we can reduce 𝑥 modulo 𝑝 and 𝑥 modulo 𝑞 to obtain two equations of the above form. Proof: Let 𝑝 1 = 𝑝 − 1 ( mod 𝑞 ) and 𝑞 1 = 𝑞 − 1 ( mod 𝑝 ) . These must exist since 𝑝 , 𝑞 are coprime. Then we claim that if 𝑦 is an integer such that then 𝑦 satisfies both equations: Modulo 𝑝 , we have 𝑦 = 𝑎 𝑞 𝑞 1 = 𝑎 ( mod 𝑝 ) since 𝑞 𝑞 1 = 1 ( mod 𝑝 ) . Similarly 𝑦 = 𝑏 ( mod 𝑞 ) . Thus 𝑦 is a solution for 𝑥 . I

Number Theory - The Chinese Remainder Theorem Number Theory Modular Arithmetic Euclid’s Algorithm Division Chinese Remainder Polynomial Roots Units & Totients Exponentiation Order of a Unit Miller-Rabin Test Generators Cyclic Groups Quadratic Residues Gauss' Lemma Quadratic Recip. Carmichael Multiplicative Möbius Inversion Generators II Cyclotomic Heptadecagon Eisenstein Gaussian Periods Roots of Unity Quadratic Forms Notes Ben Lynn ⏴ Division Polynomial Roots ⏵ Contents The Chinese Remainder Theorem Suppose we wish to solve \[ x = 2 \pmod{5} \] \[ x = 3 \pmod{7} \] for \(x\)

Explore this link on the map →

saved by

related reading