चीनी शेषफल प्रमेय
चीनी शेषफल प्रमेय (Chinese remainder theorem) को निम्नलिखित शब्दों में व्यक्त किया जा सकता है-
यदि ni युग्मशः अभाज्य (pairwise coprime) हों यदि a1, ..., ak कोई पूर्णांक हैं , तो एक पूर्णांक x ऐसा होगा कि,
तथा कोई भी दो ऐसे पूर्णांक x, सर्वसम मॉड्युलो N होंगे।[1]
- उदाहरण
ऐसा पूर्णांक प्राप्त कीजिये जो निम्नलिखित शर्तों को सन्तुष्ट करती हो-
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
x1.13.29.41≡1(mod.5) → x1.(-2)(-1)(1)≡x1.2≡1(mod.5)
x1≡3(mod.5)
x2.5.29.41≡1(mod.13) → x2.5.3.2≡1(mod.13)→ x2.4≡1(mod.13)
x2≡10(mod. 13)
x3.5.13.41≡1(mod.29) →x3.5.13.17≡1(mod.29)&rarr x3.3≡1(mod.29)
x3≡-10(mod.29)
x4.5.13.29≡1(mod.41) →x4.5.13.(-12) ≡1(mod.41)→x4.(-1) ≡1(mod.41)
x4≡-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)
इतिहास
[संपादित करें]चीन के निवासी सुन्जी सुआनजिंग ने तीसरी शताब्दी में कुछ संख्याओं के माध्यम से इस प्रमेय का कथन किया है। किन्तु सुन जी के कार्य में न तो उपपत्ति दी गयी है और न ही पूर्ण अल्गोरिद्म। इसका सम्पूर्ण अल्गोरिद्म ५वीं शताब्दी के भारतीय गणितज्य आर्यभट ने दिया है। [2]
सन्दर्भ
[संपादित करें]- ↑ Ireland & Rosen 1990
- ↑ "Kak 1986". मूल से 29 अप्रैल 2017 को पुरालेखित. अभिगमन तिथि 12 मई 2017.