चीनी शेषफल प्रमेय

चीनी शेषफल प्रमेय (Chinese remainder theorem) को निम्नलिखित शब्दों में व्यक्त किया जा सकता है-

यदि n_i युग्मशः अभाज्य (pairwise coprime) हों यदि a₁, ..., a_k कोई पूर्णांक हैं , तो एक पूर्णांक x ऐसा होगा कि,

${\displaystyle {\begin{aligned}x\equiv a_{1}&{\pmod {n_{1}}}\\\quad \vdots \\x\equiv a_{k}&{\pmod {n_{k}}}\end{aligned}},}$

तथा कोई भी दो ऐसे पूर्णांक x, सर्वसम मॉड्युलो N होंगे।^[1]

उदाहरण

ऐसा पूर्णांक ${\displaystyle x}$ प्राप्त कीजिये जो निम्नलिखित शर्तों को सन्तुष्ट करती हो-

x ≡ 3 (mod.5)

x ≡ 5 (mod.13)

x ≡ 7 (mod.29)

x ≡ 1 (mod.41)

X = 3.13.29.41.x1 + 5.5.29.41.x2 + 7.5.13.41.x3 + 1.5.13.29.x4

x₁.13.29.41≡1(mod.5) → x₁.(-2)(-1)(1)≡x₁.2≡1(mod.5)

x₁≡3(mod.5)

x₂.5.29.41≡1(mod.13) → x₂.5.3.2≡1(mod.13)→ x₂.4≡1(mod.13)

x₂≡10(mod. 13)

x₃.5.13.41≡1(mod.29) →x₃.5.13.17≡1(mod.29)&rarr x₃.3≡1(mod.29)

x₃≡-10(mod.29)

x₄.5.13.29≡1(mod.41) →x₄.5.13.(-12) ≡1(mod.41)→x₄.(-1) ≡1(mod.41)

x₄≡-1(mod.41)

X=3.13.29.41.3 + 5.5.29.41.10 + 7.5.13.41.(-10) + 1.5.13.29.(-1)

X=139113 + 297250 – 186550 -1885

X=247928

x≡X≡247928(mod.5.13.29.41) → x≡16073(mod.77285)