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

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

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

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

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

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

हम विभाजन एल्गोरिथम को जानते हैं; लाभांश $=$ भाजक $\times$ भागफल $+$ शेषफल । यह और कुछ नहीं वरन् यूक्लिड विभाजन प्रमेयिका का अन्य नाम है ।

उदाहरण

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

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

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

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

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

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

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

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

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

चरण 1

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

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

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

चरण 2

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

$135=5\times 27+0$

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

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

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

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

$a=b(q_{1})+r_{1}$ ( जहां $q_{1},q_{2},q_{3},.....q_{n}$ और $r_{1},r_{2},r_{3},.....r_{n}$ क्रमशः भागफल तथा शेषफल है। )

$b=r_{1}(q_{2})+r_{2}$

$r_{1}=r_{2}(q_{3})+r_{3}$

इसी तरह अंतिम दो चरण लिखने पर ;

$r_{n-2}=r_{n-1}(q_{n})+r_{n}$

$r_{n-1}=r_{n}(q_{n+1})+0$

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

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

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

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

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