यूक्लिड विभाजन प्रमेयिका तथा विभाजन एल्गोरिथ्म

यूक्लिड विभाजन प्रमेयिका — भाग की मूल अवधारणा

आप प्राथमिक कक्षा से ही संख्याओं को विभाजित करते आ रहे हैं। जब आप 17 को 5 से भाग देते हैं, तो भागफल 3 और शेषफल 2 कहते हैं। यूक्लिड ने इसी परिचित तथ्य को एक सटीक कथन के रूप में लिखा।

यूक्लिड विभाजन प्रमेयिका: दो धनात्मक पूर्णांक $a$ और $b$ दिए होने पर, अद्वितीय पूर्ण संख्याएँ $q$ और $r$ इस प्रकार विद्यमान होती हैं कि $$a = bq + r, \quad 0 \le r < b$$

यहाँ $a$ भाज्य, $b$ भाजक, $q$ भागफल, और $r$ शेषफल है।

मुख्य शर्त $0 \le r < b$ है — शेषफल कभी ऋणात्मक नहीं होता और सदैव भाजक से छोटा होता है। हमारे उदाहरण $17 = 5 \times 3 + 2$ के लिए: $a=17$, $b=5$, $q=3$, $r=2$, और वास्तव में $0 \le 2 < 5$।

मुख्य बिंदु: शब्द 'प्रमेयिका' (lemma) का अर्थ है एक छोटा सिद्ध कथन जिसे हम बड़े परिणाम सिद्ध करने के लिए सीढ़ी के रूप में उपयोग करते हैं। 'अद्वितीय' का अर्थ है कि प्रत्येक $a$ और $b$ के लिए केवल एक ही संभव युग्म $(q, r)$ होता है।

[बोर्ड के लिए महत्वपूर्ण] एक सामान्य भूल है शेषफल को भाजक के बराबर या उससे बड़ा लिख देना। सदैव $0 \le r < b$ तक घटाते रहें।

यूक्लिड विभाजन एल्गोरिथ्म — म.स. ज्ञात करना

प्रमेयिका की असली शक्ति यह है कि यह हमें दो धनात्मक पूर्णांकों का म.स. (HCF / महत्तम समापवर्तक) ज्ञात करने की एक विश्वसनीय, दोहराने योग्य विधि देती है। यह चरणबद्ध प्रक्रिया यूक्लिड विभाजन एल्गोरिथ्म कहलाती है।

चरण

दो धनात्मक पूर्णांकों $a$ और $b$ ($a > b$) का म.स. ज्ञात करने के लिए:

1. विभाजन प्रमेयिका लगाएँ: $a = bq + r$ लिखें।
2. यदि $r = 0$, तो म.स. $b$ है — रुक जाएँ।
3. यदि $r \neq 0$, तो प्रमेयिका को $b$ और $r$ पर पुनः लगाएँ (पुराना भाजक नया भाज्य बनता है, शेषफल नया भाजक)।
4. शेषफल 0 होने तक दोहराते रहें। उस अंतिम चरण का भाजक ही म.स. है।

यह क्यों काम करता है: प्रत्येक चरण पर दोनों संख्याओं के उभयनिष्ठ गुणनखंड बिल्कुल वही रहते हैं। अतः अंतिम अशून्य शेषफल मूल युग्म के सभी उभयनिष्ठ गुणनखंडों को समाहित करता है — वही उनका म.स. है।

हल किया गया उदाहरण — 455 और 42 का म.स.

• $455 = 42 \times 10 + 35$
• $42 = 35 \times 1 + 7$
• $35 = 7 \times 5 + 0$ ← शेषफल 0

अंतिम भाजक $7$ है, अतः $\text{म.स.}(455, 42) = 7$।

[बोर्ड के लिए महत्वपूर्ण] परीक्षा में एल्गोरिथ्म की प्रत्येक पंक्ति दिखाएँ। अंक केवल अंतिम उत्तर पर नहीं, बल्कि प्रत्येक सही भाग चरण पर मिलते हैं।

प्रमेयिका द्वारा धनात्मक पूर्णांकों के गुणधर्म

यूक्लिड की प्रमेयिका पूर्णांकों के रूप के बारे में सामान्य कथन सिद्ध करने का भी एक सुंदर उपकरण है। तरकीब यह है कि भाजक $b$ को एक निश्चित छोटी संख्या लें और संभव शेषफलों की सूची बनाएँ।

प्रत्येक पूर्णांक एक निश्चित रूप का होता है

$b = 2$ लें। प्रमेयिका द्वारा किसी भी पूर्णांक $a$ को $a = 2q + r$ लिखा जा सकता है जहाँ $r = 0$ या $r = 1$। अतः प्रत्येक पूर्णांक या तो सम ($2q$) है या विषम ($2q+1$) — कोई तीसरा विकल्प नहीं।

इसी प्रकार, $b = 3$ लेने पर प्रत्येक पूर्णांक $3q$, $3q+1$, या $3q+2$ रूप का होता है।

एक प्रसिद्ध परिणाम

दावा: प्रत्येक धनात्मक विषम पूर्णांक $4q + 1$ या $4q + 3$ रूप का होता है।

तर्क: $b = 4$ लें। कोई भी पूर्णांक $4q$, $4q+1$, $4q+2$, या $4q+3$ है। रूप $4q$ और $4q+2$ सम हैं। अतः कोई विषम पूर्णांक $4q+1$ या $4q+3$ ही होना चाहिए।

परीक्षा सुझाव: ये 'पूर्णांक का रूप' संबंधी उपपत्तियाँ पसंदीदा दीर्घ-उत्तरीय प्रश्न हैं। विधि सदैव वही है: सही भाजक $b$ चुनें, शेषफल के मामले सूचीबद्ध करें, और जो फिट न हों उन्हें हटा दें।

CBSE बनाम राज्य बोर्ड विद्यार्थियों के लिए एक नोट

यदि आप नवीनतम युक्तिसंगत (rationalised) CBSE पाठ्यक्रम का अनुसरण कर रहे हैं, तो यूक्लिड विभाजन प्रमेयिका कक्षा 10 की निर्धारित पाठ्यपुस्तक से हटा दी गई है — CBSE अब म.स. और ल.स. मुख्यतः अभाज्य गुणनखंडन (अगले खंड में) से ज्ञात करता है।

हालाँकि, कई राज्य बोर्ड अब भी यूक्लिड विभाजन एल्गोरिथ्म को सम्मिलित रखते हैं, और यह एक सुरुचिपूर्ण, परीक्षा-अनुकूल विधि बनी हुई है। यह वास्तव में उपयोगी भी है और मजबूत संख्या-बोध विकसित करती है।

मुख्य बिंदु: आपके पाठ्यक्रम में हो या न हो, इस विधि को सीखने में बहुत कम लागत आती है और लाभ बहुत — यह भाग और म.स. की समझ को गहरा करती है। CBSE विद्यार्थी इसे संवर्धन (enrichment) मान सकते हैं; राज्य बोर्ड विद्यार्थियों को इसे मूल विषय-वस्तु के रूप में महारत हासिल करनी चाहिए।

[बोर्ड के लिए महत्वपूर्ण] म.स. के लिए दोनों विधियाँ जानें — यूक्लिड एल्गोरिथ्म (यह खंड) तथा अभाज्य गुणनखंडन (अगला खंड)। परीक्षक किसी विशिष्ट विधि के लिए पूछ सकते हैं।

हल किए गए उदाहरण

उदाहरण 1: विभाजन प्रमेयिका लगाना

$a = 91$ और $b = 8$ के लिए, $a = bq + r$ में $q$ और $r$ ज्ञात कीजिए।

हल:

1. 91 को 8 से भाग दें: $8 \times 11 = 88$, शेष $91 - 88 = 3$।
2. अतः $q = 11$, $r = 3$।
3. शर्त की जाँच: $0 \le 3 < 8$। ✓

अंतिम उत्तर: $91 = 8 \times 11 + 3$।

सार: सदैव $0 \le r < b$ की पुष्टि करें — यह सुनिश्चित करता है कि आपने पूरा भाग दे दिया है।

उदाहरण 2: यूक्लिड एल्गोरिथ्म द्वारा म.स.

यूक्लिड विभाजन एल्गोरिथ्म द्वारा 135 और 225 का म.स. ज्ञात कीजिए।

हल:

1. यहाँ $225 > 135$, अतः $225 = 135 \times 1 + 90$।
2. अब 135 और 90 पर लगाएँ: $135 = 90 \times 1 + 45$।
3. अब 90 और 45 पर लगाएँ: $90 = 45 \times 2 + 0$।
4. शेषफल 0; अंतिम भाजक $45$।

अंतिम उत्तर: $\text{म.स.}(135, 225) = 45$।

सार: प्रत्येक चरण पिछले भाजक और शेषफल को नए युग्म के रूप में उपयोग करता है।

उदाहरण 3: 196 और 38220 का म.स.

196 और 38220 का म.स. ज्ञात कीजिए।

हल:

1. $38220 = 196 \times 195 + 0$ (क्योंकि $196 \times 195 = 38220$)।
2. पहले ही चरण में शेषफल 0 है, अतः भाजक 196 ही म.स. है।

अंतिम उत्तर: $\text{म.स.}(196, 38220) = 196$।

सार: यदि छोटी संख्या बड़ी संख्या को पूर्णतः विभाजित कर दे, तो वही म.स. होती है।

उदाहरण 4: 867 और 255 का म.स.

यूक्लिड एल्गोरिथ्म से $\text{म.स.}(867, 255)$ ज्ञात कीजिए।

हल:

1. $867 = 255 \times 3 + 102$।
2. $255 = 102 \times 2 + 51$।
3. $102 = 51 \times 2 + 0$।
4. अंतिम भाजक = 51।

अंतिम उत्तर: $\text{म.स.}(867, 255) = 51$।

सार: शेषफल ठीक 0 होने तक चलते रहें — कभी जल्दी न रुकें।

उदाहरण 5: दिए गए शेषफलों के साथ विभाजित करने वाली सबसे बड़ी संख्या

वह सबसे बड़ी संख्या ज्ञात कीजिए जो 245 और 1029 को विभाजित करने पर प्रत्येक में शेषफल 5 छोड़ती है।

हल:

1. यदि शेषफल 5 है, तो वह संख्या $245 - 5 = 240$ और $1029 - 5 = 1024$ को पूर्णतः विभाजित करती है।
2. अतः अभीष्ट संख्या $\text{म.स.}(240, 1024)$ है।
3. $1024 = 240 \times 4 + 64$; $240 = 64 \times 3 + 48$; $64 = 48 \times 1 + 16$; $48 = 16 \times 3 + 0$।
4. म.स. $= 16$।

अंतिम उत्तर: अभीष्ट सबसे बड़ी संख्या $16$ है।

सार: 'शेषफल r छोड़ती है' का अर्थ है पहले r घटाएँ, फिर घटी हुई संख्याओं का म.स. लें।

उदाहरण 6: पूर्णांक का रूप

दिखाइए कि कोई भी धनात्मक विषम पूर्णांक $6q + 1$, $6q + 3$, या $6q + 5$ रूप का होता है, जहाँ $q$ कोई पूर्णांक है।

हल:

1. $b = 6$ के साथ विभाजन प्रमेयिका द्वारा, कोई भी पूर्णांक $a$ इनमें से एक है: $6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5$।
2. रूप $6q$, $6q+2$, $6q+4$ सभी सम हैं (प्रत्येक 2 का गुणज)।
3. अतः कोई विषम पूर्णांक शेष रूपों में से एक होना चाहिए: $6q+1$, $6q+3$, या $6q+5$।

अंतिम उत्तर: प्रत्येक धनात्मक विषम पूर्णांक $6q+1$, $6q+3$, या $6q+5$ है।

सार: सभी शेषफल मामले सूचीबद्ध करें, फिर शर्त (यहाँ सम होने) का खंडन करने वालों को हटा दें।

उदाहरण 7: परेड के लिए अधिकतम स्तंभ

616 सदस्यों की एक सेना टुकड़ी को 32 सदस्यों के एक सेना बैंड के पीछे मार्च करना है। दोनों समूहों को समान संख्या में स्तंभों में मार्च करना है। वे अधिकतम कितने स्तंभों में मार्च कर सकते हैं?

हल:

1. दोनों समूहों के लिए उभयनिष्ठ अधिकतम स्तंभों की संख्या $\text{म.स.}(616, 32)$ है।
2. $616 = 32 \times 19 + 8$।
3. $32 = 8 \times 4 + 0$।
4. अंतिम भाजक = 8।

अंतिम उत्तर: वे अधिकतम $8$ स्तंभों में मार्च कर सकते हैं।

सार: 'दो राशियों से अधिकतम समान समूह' सदैव एक म.स. की समस्या है।

उदाहरण 8: भिन्न को सरल करने में म.स. का उपयोग

भिन्न $\dfrac{1023}{1219}$ को निम्नतम पदों में बदलिए।

हल:

1. $\text{म.स.}(1219, 1023)$ ज्ञात करें: $1219 = 1023 \times 1 + 196$।
2. $1023 = 196 \times 5 + 43$।
3. $196 = 43 \times 4 + 24$; $43 = 24 \times 1 + 19$; $24 = 19 \times 1 + 5$; $19 = 5 \times 3 + 4$; $5 = 4 \times 1 + 1$; $4 = 1 \times 4 + 0$।
4. म.स. $= 1$, अतः भिन्न पहले से ही निम्नतम पदों में है।

अंतिम उत्तर: $\dfrac{1023}{1219}$ पहले से ही निम्नतम पदों में है (संख्याएँ सहअभाज्य हैं)।

सार: म.स. 1 वाली दो संख्याएँ सहअभाज्य होती हैं; उनकी भिन्न को और सरल नहीं किया जा सकता।

उदाहरण 9: दो लंबाइयाँ मापने वाला सबसे बड़ा टेप

वह सबसे लंबा मापने वाला टेप ज्ञात कीजिए जो 825 सेमी और 675 सेमी की विमाओं को पूर्ण संख्या में बार माप सके।

हल:

1. ऐसा सबसे लंबा टेप $\text{म.स.}(825, 675)$ है।
2. $825 = 675 \times 1 + 150$।
3. $675 = 150 \times 4 + 75$।
4. $150 = 75 \times 2 + 0$। म.स. $= 75$।

अंतिम उत्तर: सबसे लंबा टेप $75$ सेमी है।

सार: 'सबसे लंबी लंबाई जो दोनों को पूर्णतः मापे' = दोनों लंबाइयों का म.स.।

उदाहरण 10: विषम पूर्णांक का वर्ग

विभाजन प्रमेयिका का उपयोग कर दिखाइए कि किसी धनात्मक विषम पूर्णांक का वर्ग किसी पूर्णांक $m$ के लिए $8m + 1$ रूप का होता है।

हल:

1. किसी भी विषम पूर्णांक को $a = 4q + 1$ या $a = 4q + 3$ लिखा जा सकता है ($b = 4$, विषम मामले)।
2. स्थिति 1: $a = 4q+1 \Rightarrow a^2 = 16q^2 + 8q + 1 = 8(2q^2 + q) + 1 = 8m + 1$।
3. स्थिति 2: $a = 4q+3 \Rightarrow a^2 = 16q^2 + 24q + 9 = 8(2q^2 + 3q + 1) + 1 = 8m + 1$।
4. दोनों स्थितियों में $a^2 = 8m + 1$।

अंतिम उत्तर: किसी धनात्मक विषम पूर्णांक का वर्ग $8m + 1$ रूप का होता है।

सार: संभव विषम रूपों में बाँटें, प्रत्येक का वर्ग करें, और उभयनिष्ठ गुणज बाहर निकालकर अभीष्ट पैटर्न प्रकट करें।