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

यूक्लिड विभाजन प्रमेयिका ( Euclid's division lemma ) प्राचीन यूनानी गणितज्ञ यूक्लिड द्वारा प्रस्तावित मौलिक प्रमेयों में से एक है। यूक्लिड डिवीजन प्रमेयिका की मदद से एक एल्गोरिदम ( algorithm) परिभाषित किया गया है यानी, यूक्लिड डिवीजन एल्गोरिदम जिसका उपयोग किन्हीं दो संख्याओं के को खोजने के लिए किया जाता है। इस एल्गोरिदम में, दो संख्याओं का महत्तम समापवर्तक या म. स. ( HCF) प्राप्त करने के लिए यूक्लिड डिवीजन लेम्मा बार-बार प्रयोग किया जाता है । यूक्लिड के डिवीजन एल्गोरिदम को समझने के लिए ; हमें सबसे पहले यूक्लिड के डिवीजन प्रमेयिका को समझना होगा। प्रमेयिका एक प्रमेय की तरह है और हम इस इकाई में यूक्लिड के विभाजन प्रमेयिका , यूक्लिड के डिवीजन एल्गोरिदम और उनके उपयोग से महत्तम समापवर्तक या म. स. ( HCF) को ज्ञात करना सीखेंगे ।

यूक्लिड विभाजन प्रमेयिका

यूक्लिड विभाजन प्रमेयिका का कथन- यूक्लिड का विभाजन प्रमेयिका विभाजन के विभिन्न घटकों के बीच संबंध बताता है। यह बताता है कि, किन्हीं दो धनात्मक पूर्णांकों a और b के लिए दो अद्वितीय पूर्णांक q और r होते हैं, जिन्हें हम a = b ×q + r के रूप में प्रदर्शित कर सकते हैं ।

इस विधि में, हम q को भाग का भागफल कहते हैं, और r ( 0 ≤r<b) को भाग का शेषफल है।

हम विभाजन एल्गोरिथम को जानते हैं - लाभांश = भाजक × भागफल + शेषफल ( Dividend = Divisor × Quotient + Remainder)

यह और कुछ नहीं वरन् यूक्लिड विभाजन प्रमेयिका का अन्य नाम है।

उदाहरण -

आइए, बेहतर समझ के लिए यूक्लिड विभाजन प्रमेयिका के एक उदाहरण पर विचार करें।

यहां, दी गई संख्याएं हैं, 43(=a) और 6(=b), हम इसे a = b ×q + r रूप में लिख सकते हैं ।

43 = 6×7 + 1 जहां, भागफल (q) 7 है और शेषफल (r) 1 है ।

यूक्लिड का विभाजन एल्गोरिथम क्या है?

यूक्लिड विभाजन प्रमेयिका का उपयोग करके दो संख्याओं का महत्तम समापवर्तक या म. स. ( HCF) खोजने की प्रक्रिया को "यूक्लिड विभाजन एल्गोरिदम" कहा जाता है। इस प्रक्रिया में, दो संख्याओं का महत्तम समापवर्तक या म. स. (HCF) ज्ञात करने के लिए यूक्लिड विभाजन प्रमेयिका का उपयोग क्रमिक रूप से कई बार किया जाता है।

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

यूक्लिड विभाजन एल्गोरिथम के प्रयोग से महत्तम समापवर्तक म. स. (HCF) ज्ञात करने की विधि

हम दो संख्याओं, 135 और 275 का महत्तम समापवर्तक म. स. (HCF) यूक्लिड विभाजन एल्गोरिथम का उपयोग कर निकाल सकते हैं ।

महत्तम समापवर्तक म. स. (HCF) ज्ञात करने के लिए निम्नलिखित चरणों का पालन करें।

चरण 1: 135 और 275 पर यूक्लिड विभाजन एल्गोरिथम का उपयोग करे।

275 = 135(2) + 5 जहां, भागफल (q) 135 है और शेषफल (r) 5 है ।

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

चरण 2: यूक्लिड विभाजन प्रेमिका के पुनः उपयोग पर,

135 = 5(27) + 0

अतः अब शेषफल शून्य (0) है, तो अंतिम से दूसरे चरण में प्राप्त शेषफल (5) ही हमारा महत्तम समापवर्तक है।

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

मान लें, कि हमें दो यादृच्छिक संख्याओं a और b का महत्तम समापवर्तक ज्ञात करना है, तो उनका महत्तम समापवर्तक यूक्लिड विभाजन प्रेमिका का अनेक बार उपयोग करके ज्ञात किया जा सकता है, जब तक कि प्राप्त शेषफल शून्य (0) न हो जाए।

सामान्यीकृत रूप-

a = b(q₁) + r₁

b= r₁(q₂) + r₂

r1 = r₂(q₃) + r₃

⋮

r_n−2 = r_n−1(q_n) + r_n

r_n−1 = r_n(q_n+1) + 0

अतः , a और b का महत्तम समापवर्तक दूसरे अंतिम चरण में प्राप्त शेषफल है, अर्थात, महत्तम समापवर्तक HCF (a, b) = r_n

अभ्यास प्रश्न

1. यूक्लिड विभाजन एल्गोरिदम का उपयोग करके 73 को 9 से विभाजित किया जाता है, भागफल और शेषफल ज्ञात करें।

  2. यूक्लिड विभाजन एल्गोरिदम का उपयोग करके 315 को 17 से विभाजित किया जाता है , भागफल और शेषफल ज्ञात करें ।

3. 867 और 255 का महत्तम समापवर्तक ज्ञात करने के लिए यूक्लिड विभाजन एल्गोरिदम का उपयोग करें ।