यूक्लिडियन विभाजन

17 को 5 के 3 समूहों में बांटा गया है, जिसमें 2 बचे हुए हैं। यहाँ, भाज्य 17 है, भाजक 3 है, भागफल 5 है, और शेषफल 2 है (जो भाजक 3 से सख्ती से छोटा है), या अधिक प्रतीकात्मक रूप से, 17 = (3 × 5) + 2।

अंकगणित में, यूक्लिडियन विभाजन - या शेष के साथ विभाजन - एक पूर्णांक (भाजक) को दूसरे (भाजक) द्वारा विभाजन (गणित) की प्रक्रिया है, जो एक पूर्णांक भागफल और एक प्राकृतिक संख्या का उत्पादन करता है जो निरपेक्ष से सख्ती से छोटा होता है। भाजक का मूल्य। एक मूलभूत संपत्ति यह है कि भागफल और शेष मौजूद हैं और कुछ शर्तों के तहत अद्वितीय हैं। इस विशिष्टता के कारण, "यूक्लिडियन डिवीजन" को अक्सर गणना की किसी भी विधि का उल्लेख किए बिना, और स्पष्ट रूप से भागफल और शेष की गणना किए बिना माना जाता है। संगणना के तरीकों को विभाजन एल्गोरिथ्म कहा जाता है, जिनमें से सबसे अच्छा ज्ञात लॉन्ग डिवीजन है।

यूक्लिडियन विभाजन, और इसकी गणना करने के लिए एल्गोरिदम, पूर्णांकों से संबंधित कई प्रश्नों के लिए मौलिक हैं, जैसे कि दो पूर्णांकों का सबसे बड़ा सामान्य विभाजक खोजने के लिए यूक्लिडियन एल्गोरिथ्म ,^[1] और मॉड्यूलर अंकगणित , जिसके लिए केवल अवशेषों पर विचार किया जाता है।^[2] केवल शेष की गणना करने वाले ऑपरेशन को मॉड्यूल ऑपरेशन कहा जाता है,^[3] और अक्सर गणित और कंप्यूटर विज्ञान दोनों में प्रयोग किया जाता है।

पाई में 9 स्लाइस हैं, इसलिए 4 लोगों में से प्रत्येक को 2 स्लाइस मिलती हैं और 1 बच जाता है।

विभाजन प्रमेय

यूक्लिडियन विभाजन निम्नलिखित परिणाम पर आधारित है, जिसे कभी-कभी यूक्लिड का विभाजन प्रमेयिका कहा जाता है।

दो पूर्णांक दिए गए हैं $a$ और $b$ , साथ $b \neq 0$ , अद्वितीयता परिमाणीकरण पूर्णांक मौजूद हैं $q$ और $r$ ऐसा है कि

a = bq + r

और

0 \leq r < | b |

,

कहां $| b |$ के निरपेक्ष मान को दर्शाता है $b$ .^[4] उपरोक्त प्रमेय में, चार पूर्णांकों में से प्रत्येक का अपना एक नाम है: $a$ कहा जाता है dividend, $b$ कहा जाता है divisor, $q$ कहा जाता है quotient और $r$ कहा जाता है remainder.

भाज्य और भाजक से भागफल और शेषफल की गणना कहलाती है division या - अस्पष्टता के मामले में - Euclidean division. प्रमेय को अक्सर कहा जाता है division algorithm (यद्यपि यह एक प्रमेय है और एल्गोरिथम नहीं है), क्योंकि इसका प्रमाण जैसा कि नीचे दिया गया है, कंप्यूटिंग के लिए एक सरल विभाजन एल्गोरिथ्म के लिए उधार देता है $q$ और $r$ (अधिक के लिए खंड #प्रूफ देखें)।

डिवीजन को उस मामले में परिभाषित नहीं किया गया है जहां $b = 0$ ; विभाजन को शून्य से देखें।

शेष और मॉड्यूलो ऑपरेशन के लिए, इसके अलावा अन्य कन्वेंशन भी हैं $0 \leq r < | b |$ , देखो § Other intervals for the remainder.

इतिहास

हालांकि यूक्लिड ियन डिवीजन का नाम यूक्लिड के नाम पर रखा गया है, ऐसा लगता है कि वह अस्तित्व और अद्वितीयता प्रमेय को नहीं जानता था, और वह एकमात्र गणना विधि जिसे वह जानता था वह थी डिवीजन एल्गोरिथ्म # बार-बार घटाव द्वारा डिवीजन।^{[citation needed]} हिंदू-अरबी अंक प्रणाली की खोज से पहले, जिसे 13 वीं शताब्दी के दौरान फिबोनैकी द्वारा यूरोप में पेश किया गया था, विभाजन बेहद कठिन था, और केवल सर्वश्रेष्ठ गणितज्ञ ही इसे करने में सक्षम थे। वर्तमान में, लंबे विभाजन सहित अधिकांश विभाजन एल्गोरिदम, इस अंकन या इसके रूपों पर आधारित हैं, जैसे बाइनरी अंक। एक उल्लेखनीय अपवाद न्यूटन-रैफसन डिवीजन है, जो किसी भी संख्या प्रणाली से स्वतंत्र है।

यूक्लिडियन डिवीजन शब्द को 20 वीं शताब्दी के दौरान यूक्लिडियन रिंग ्स के विभाजन के लिए शॉर्टहैंड के रूप में पेश किया गया था। इस विभाजन को संख्याओं के अन्य प्रकार के विभाजन (गणित) से अलग करने के लिए गणितज्ञों द्वारा इसे तेजी से अपनाया गया है।^{[citation needed]}

सहज उदाहरण

मान लीजिए कि एक पाई में 9 स्लाइस हैं और उन्हें 4 लोगों में समान रूप से बांटा जाना है। यूक्लिडियन डिवीजन का उपयोग करते हुए, 9 को 4 से विभाजित करने पर 2 शेष बचता है। दूसरे शब्दों में, प्रत्येक व्यक्ति को पाई के 2 स्लाइस मिलते हैं, और 1 स्लाइस बचता है।

गुणा के उपयोग से इसकी पुष्टि की जा सकती है, विभाजन का व्युत्क्रम: यदि 4 लोगों में से प्रत्येक को 2 स्लाइस मिले, तो कुल मिलाकर 4 × 2 = 8 स्लाइस दिए गए। बचे हुए 1 स्लाइस को जोड़ने पर 9 स्लाइस मिलते हैं। संक्षेप में: 9 = 4 × 2 + 1।

सामान्य तौर पर, यदि स्लाइस की संख्या को निरूपित किया जाता है $a$ और लोगों की संख्या को दर्शाया गया है $b$ , तब कोई पाई को लोगों के बीच समान रूप से विभाजित कर सकता है जैसे कि प्रत्येक व्यक्ति को प्राप्त होता है $q$ स्लाइस (भागफल), कुछ संख्या में स्लाइस के साथ $r<b$ बचा हुआ (शेष) होना। किस मामले में, समीकरण $a=bq+r$ रखती है।

यदि 9 स्लाइस को 4 के बजाय 3 लोगों के बीच विभाजित किया गया था, तो प्रत्येक को 3 प्राप्त होंगे और कोई टुकड़ा शेष नहीं रहेगा, जिसका अर्थ है कि शेष शून्य होगा, जिससे यह निष्कर्ष निकलता है कि 3 समान रूप से 9 को विभाजित करता है, या यह कि 3 9 को विभाजित करता है।

यूक्लिडियन विभाजन को समान सूत्र का प्रयोग करके ऋणात्मक भाज्य (या ऋणात्मक भाजक) तक भी बढ़ाया जा सकता है; उदाहरण के लिए −9 = 4 × (−3) + 3, जिसका अर्थ है कि −9 को 4 से विभाजित करने पर शेषफल 3 के साथ −3 है।

उदाहरण

यदि a = 7 और b = 3, तो q = 2 और r = 1, चूँकि 7 = 3 × 2 + 1 है।
यदि a = 7 और b = −3, तो q = −2 और r = 1, क्योंकि 7 = −3 × (−2) + 1.
यदि a = −7 और b = 3, तो q = −3 और r = 2, क्योंकि −7 = 3 × (−3) + 2.
अगर a = −7 और b = −3, तो q = 3 और r = 2, क्योंकि −7 = −3 × 3 + 2.

प्रमाण

विभाजन प्रमेय का निम्नलिखित प्रमाण इस तथ्य पर निर्भर करता है कि गैर-ऋणात्मक पूर्णांकों का घटता क्रम अंततः रुक जाता है। इसे दो भागों में विभाजित किया गया है: एक अस्तित्व के लिए और दूसरा अद्वितीयता के लिए $q$ और $r$ . अन्य प्रमाण तर्क को सरल बनाने के लिए सुव्यवस्थित सिद्धांत का उपयोग करते हैं (अर्थात, यह दावा कि हर गैर-खाली सेट | गैर-नकारात्मक पूर्णांक ों का गैर-खाली सेट | गैर-नकारात्मक पूर्णांक में सबसे छोटा तत्व होता है), लेकिन सीधे प्रदान न करने का नुकसान विभाजन को हल करने के लिए एल्गोरिथम (देखें § Effectiveness अधिक जानकारी के लिए)।^[5]

अस्तित्व

पहले मामले पर गौर कीजिए $b < 0$ . स्थापना $b' = - b$ और $q' = - q$ , समीकरण $a = bq + r$ के रूप में पुनः लिखा जा सकता है $a = b'q' + r$ और असमानता $0 \leq r < | b |$ के रूप में पुनः लिखा जा सकता है $0 \leq r < |b' |$ . यह मामले के लिए अस्तित्व को कम करता है $b < 0$ उस मामले के लिए $b > 0$ .

इसी प्रकार यदि $a < 0$ और $b > 0$ , सेटिंग $a' = - a$ , $q' = - q - 1$ , और $r' = b - r$ , समीकरण $a = bq + r$ के रूप में पुनः लिखा जा सकता है $a' = bq' + r'$ , और असमानता $0 \leq r < | b |$ के रूप में फिर से लिखा जा सकता है $0 \leq r' < | b |$ . इस प्रकार अस्तित्व का प्रमाण मामले में कम हो जाता है $a \geq 0$ और $b > 0$ - जो सबूत के शेष में माना जाएगा।

होने देना $q 1 = 0$ और $r 1 = a$ , तो ये ऐसी गैर-ऋणात्मक संख्याएँ हैं $a = bq 1 + r 1$ . यदि $r 1 < b$ तो विभाजन पूरा हो गया है, तो मान लीजिए $r 1 \geq b$ . फिर परिभाषित करना $q 2 = q 1 + 1$ और $r 2 = r 1 - b$ , किसी के पास $a = bq 2 + r 2$ साथ $0 \leq r 2 < r 1$ . जैसे ही होते हैं $r 1$ गैर-ऋणात्मक पूर्णांक से कम $r 1$ , किसी को केवल इस प्रक्रिया को ज्यादा से ज्यादा दोहराने की जरूरत है $r 1$ अंतिम भागफल और शेष तक पहुंचने का समय। यानी एक प्राकृतिक संख्या मौजूद है $k \leq r 1$ ऐसा है कि $a = bq k + r k$ और $0 \leq r k < | b |$ .

यह अस्तित्व को सिद्ध करता है और भागफल और शेष की गणना के लिए एक सरल विभाजन एल्गोरिथ्म भी देता है। हालाँकि, यह एल्गोरिथम कुशल नहीं है, क्योंकि इसके चरणों की संख्या क्रम की है $a / b$ .

विशिष्टता

पूर्णांकों का जोड़ा $r$ और $q$ ऐसा है कि $a = bq + r$ अद्वितीय है, इस अर्थ में कि यूक्लिडियन डिवीजन प्रमेय में समान स्थिति को पूरा करने वाले पूर्णांकों की कोई अन्य जोड़ी नहीं हो सकती है। दूसरे शब्दों में, यदि हमारे पास एक और विभाजन है $a$ द्वारा $b$ , कहो $a = bq' + r'$ साथ $0 \leq r' < | b |$ , तो हमारे पास वह होना चाहिए

q' = q and r' = r

.

इस कथन को सिद्ध करने के लिए हम सर्वप्रथम पूर्वधारणाओं से प्रारंभ करते हैं

0 \leq r < | b |

0 \leq r' < | b |

a = bq + r

a = bq' + r'

दो समीकरणों को घटाने पर प्राप्त होता है

b (q - q') = r' - r

.

इसलिए $b$ का भाजक है $r' - r$ . जैसा

| r' - r | < | b |

उपरोक्त असमानताओं से, एक प्राप्त होता है

r' - r = 0

,

और

b (q - q') = 0

.

तब से $b \neq 0$ , हमें वह मिलता है $r = r'$ और $q = q'$ , जो यूक्लिडियन डिवीजन प्रमेय की विशिष्टता को साबित करता है।

प्रभावशीलता

सामान्य तौर पर, एक अस्तित्व प्रमाण मौजूदा भागफल और शेष की गणना के लिए एक एल्गोरिथ्म प्रदान नहीं करता है, लेकिन उपरोक्त प्रमाण तुरंत एक एल्गोरिथ्म प्रदान करता है (डिवीजन एल्गोरिथम # बार-बार घटाव द्वारा विभाजन देखें), भले ही यह बहुत कुशल नहीं है क्योंकि यह भागफल के आकार के रूप में कई चरणों की आवश्यकता होती है। यह इस तथ्य से संबंधित है कि यह केवल पूर्णांकों के जोड़, घटाव और तुलना का उपयोग करता है, बिना गुणन को शामिल किए, न ही पूर्णांकों के किसी विशेष प्रतिनिधित्व जैसे कि दशमलव संकेतन।

दशमलव संकेतन के संदर्भ में, यूक्लिडियन डिवीजनों को हल करने के लिए लंबा डिवीजन एक अधिक कुशल एल्गोरिदम प्रदान करता है। बाइनरी संख्या और हेक्साडेसिमल नोटेशन के लिए इसका सामान्यीकरण कंप्यूटर कार्यान्वयन के लिए और अधिक लचीलापन और संभावना प्रदान करता है। हालांकि, बड़े इनपुट के लिए, एल्गोरिदम जो विभाजन को गुणा करने के लिए कम करते हैं, जैसे डिवीजन एल्गोरिदम#न्यूटन-राफसन डिवीजन|न्यूटन-राफसन, आमतौर पर पसंद किए जाते हैं, क्योंकि उन्हें केवल उस समय की आवश्यकता होती है जो गुणन के समय के अनुपात में होता है। परिणाम—उपयोग किए जाने वाले गुणन एल्गोरिद्म से स्वतंत्र (अधिक जानकारी के लिए, डिवीजन एल्गोरिथम#फास्ट डिवीजन विधियां देखें)।

वेरिएंट

यूक्लिडियन डिवीजन कई प्रकारों को स्वीकार करता है, जिनमें से कुछ नीचे सूचीबद्ध हैं।

शेष के लिए अन्य अंतराल

यूक्लिडियन डिवीजन में $d$ विभाजक के रूप में, शेष को अंतराल (गणित) से संबंधित माना जाता है $[0, d)$ लंबाई का $| d |$ . समान लंबाई के किसी अन्य अंतराल का उपयोग किया जा सकता है। अधिक सटीक, दिए गए पूर्णांक $m$ , $a$ , $d$ साथ $m>0$ , अद्वितीय पूर्णांक मौजूद हैं $q$ और $r$ साथ $d\leq r<m+d$ ऐसा है कि $a=mq+r$ .

विशेष रूप से, अगर $d=-\left\lfloor {\frac {m}{2}}\right\rfloor$ तब $-\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor$ . इस विभाजन को केन्द्रित विभाजन और इसके शेष भाग कहा जाता है $r$ केन्द्रित शेषफल या न्यूनतम निरपेक्ष शेषफल कहा जाता है।

इसका उपयोग वास्तविक संख्या ओं का अनुमान लगाने के लिए किया जाता है: यूक्लिडियन डिवीजन काट-छांट को परिभाषित करता है, और केंद्रित डिवीजन गोलाई को परिभाषित करता है।

मोंटगोमरी डिवीजन

दिए गए पूर्णांक $a$ , $m$ और $R,$ साथ $m>0$ और $\gcd(R,m)=1,$ होने देना $R^{-1}$ का मॉड्यूलर गुणक व्युत्क्रम हो $R$ (अर्थात।, $0<R^{-1}<m$ साथ $R^{-1}R-1$ का गुणक होना $m$ ), तो अद्वितीय पूर्णांक मौजूद हैं $q$ और $r$ साथ $0\leq r<m$ ऐसा है कि $a=mq+R^{-1}\cdot r$ . यह परिणाम हेंसल के विषम विभाजन (1900) का सामान्यीकरण करता है।^[6] महत्व $r$ है $N$ मोंटगोमरी कमी में परिभाषित अवशेष।

यूक्लिडियन डोमेन में

यूक्लिडियन डोमेन (यूक्लिडियन रिंग के रूप में भी जाना जाता है)^[7] अभिन्न डोमेन के रूप में परिभाषित किया गया है जो यूक्लिडियन डिवीजन के निम्नलिखित सामान्यीकरण का समर्थन करता है:

एक तत्व दिया

a

और एक गैर-शून्य तत्व

b

एक यूक्लिडियन डोमेन में

R

यूक्लिडियन फ़ंक्शन से लैस

d

(यूक्लिडियन वैल्यूएशन के रूप में भी जाना जाता है^[8] या डिग्री समारोह^[7]), वहां है

q

और

r

में

R

ऐसा है कि

a = bq + r

और या तो

r = 0

या

d (r) < d (b)

.

की विशिष्टता $q$ और $r$ आवश्यक नहीं।^[1]यह केवल असाधारण मामलों में होता है, आमतौर पर अविभाजित बहुपदों के लिए, और पूर्णांकों के लिए, यदि आगे की स्थिति होती है $r \geq 0$ जोड़ दिया गया है।

यूक्लिडियन डोमेन के उदाहरणों में क्षेत्र (गणित) शामिल हैं, एक क्षेत्र पर एक चर में बहुपद के छल्ले, और गॉसियन पूर्णांक । बहुपदों का यूक्लिडियन विभाजन विशिष्ट विकास का उद्देश्य रहा है।

यह भी देखें

यूक्लिड की लेम्मा
यूक्लिडियन एल्गोरिथ्म

↑ ^1.0 ^1.1 "Division and Euclidean algorithms". www-groups.mcs.st-andrews.ac.uk. Retrieved 2019-11-15.
↑ "What is modular arithmetic?". Khan Academy. Retrieved 2019-11-15.
↑ "Fun With Modular Arithmetic – BetterExplained". betterexplained.com. Retrieved 2019-11-15.
↑ Burton, David M. (2010). Elementary Number Theory. McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9.
↑ Durbin, John R. (1992). Modern Algebra : an Introduction (3rd ed.). New York: Wiley. p. 63. ISBN 0-471-51001-7.
↑ Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtaining More Karatsuba-Like Formulae over the Binary Field". IET Information Security. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. doi:10.1049/iet-ifs.2010.0114.
↑ ^7.0 ^7.1 Rotman 2006, p. 267
↑ Fraleigh 1993, p. 376

संदर्भ

Fraleigh, John B. (1993), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, ISBN 978-0-201-53467-2
Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8श्रेणी:डिवीजन (गणित)

[:1-1] 1.0 ^1.1 "Division and Euclidean algorithms". www-groups.mcs.st-andrews.ac.uk. Retrieved 2019-11-15.

[2] "What is modular arithmetic?". Khan Academy. Retrieved 2019-11-15.

[3] "Fun With Modular Arithmetic – BetterExplained". betterexplained.com. Retrieved 2019-11-15.

[4] Burton, David M. (2010). Elementary Number Theory. McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9.

[5] Durbin, John R. (1992). Modern Algebra : an Introduction (3rd ed.). New York: Wiley. p. 63. ISBN 0-471-51001-7.

[6] Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtaining More Karatsuba-Like Formulae over the Binary Field". IET Information Security. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. doi:10.1049/iet-ifs.2010.0114.

[Rot06-7] 7.0 ^7.1 Rotman 2006, p. 267

[8] Fraleigh 1993, p. 376

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]