दो रस्सियाँ हैं: 252 cm और 594 cm। सबसे लंबा टुकड़ा कौन-सा है, जिससे दोनों को बिना कुछ बचाए काटा जा सके?
यही सबसे बड़ा समापवर्तक (HCF — Highest Common Factor) है।
दो संख्याओं का HCF: यूक्लिड एल्गोरिथ्म (HCF of Two Numbers) से जुड़े प्रश्न स्वयं हल करना।
यूक्लिड एल्गोरिथ्म में बड़ी संख्या को छोटी से भाग देते हैं। फिर पिछले भाजक को शेषफल से भाग देते हैं। शेषफल 0 होने पर अंतिम गैर-शून्य भाजक ही HCF होता है।
594 बड़ी संख्या है, इसलिए पहले इसे 252 से भाग देंगे। 252 इसमें 2 बार जाता है। 252 को 2 से गुणा करने पर 504 मिलता है।
252 × 2 = 504
अब 594 में से 504 घटाइए। 90 बचता है। यही शेषफल है।
594 − 504 = 90
इसलिए, 594 = 252 × 2 + 90
अभी 90 बचा है। अब पिछले भाजक 252 को इस शेषफल 90 से भाग देंगे।
90, 252 में 2 बार जाता है। 90 को 2 से गुणा करने पर 180 मिलता है।
90 × 2 = 180
252 में से 180 घटाइए। इस बार 72 बचता है, इसलिए शेषफल 72 है।
252 − 180 = 72
इसलिए, 252 = 90 × 2 + 72
अब पिछले भाजक 90 को बचे हुए 72 से भाग देंगे।
72, 90 में 1 बार जाता है। 72 को 1 से गुणा करने पर 72 ही मिलता है।
72 × 1 = 72
90 में से 72 घटाने पर 18 बचता है। अब शेषफल 18 है।
90 − 72 = 18
इसलिए, 90 = 72 × 1 + 18
अब पिछले भाजक 72 को बचे हुए 18 से भाग देंगे।
18, 72 में 4 बार जाता है। 18 को 4 से गुणा करने पर पूरे 72 मिल जाते हैं।
18 × 4 = 72
72 में से 72 घटाने पर कुछ नहीं बचता। यानी शेषफल 0 है।
72 − 72 = 0
इसलिए, 72 = 18 × 4 + 0
अब कुछ नहीं बचा, इसलिए यहीं रुकते हैं।
252 को 18 से भाग देने पर 14 मिलता है और कुछ नहीं बचता।
252 ÷ 18 = 14
594 को 18 से भाग देने पर 33 मिलता है और कुछ नहीं बचता।
594 ÷ 18 = 33
HCF (252, 594) = 18
यूक्लिड एल्गोरिथ्म में बड़ी संख्या को छोटी से भाग देते हैं। फिर पिछले भाजक को शेषफल से भाग देते हैं। शेषफल 0 होने पर अंतिम गैर-शून्य भाजक ही HCF होता है।
255, 867 में 3 बार जाता है। 255 को 3 से गुणा करके 867 में से घटाएँ।
255 × 3 = 765
867 में से 765 घटाने पर 102 बचता है। यही शेषफल है।
867 − 765 = 102
इसलिए, 867 = 255 × 3 + 102
अब पिछले भाजक 255 को शेषफल 102 से भाग देंगे।
102, 255 में 2 बार जाता है। 102 को 2 से गुणा करके 255 में से घटाएँ।
102 × 2 = 204
255 में से 204 घटाने पर 51 बचता है। यही शेषफल है।
255 − 204 = 51
इसलिए, 255 = 102 × 2 + 51
अब पिछले भाजक 102 को शेषफल 51 से भाग देंगे।
51, 102 में 2 बार जाता है। 51 को 2 से गुणा करके 102 में से घटाएँ।
51 × 2 = 102
102 में से 102 घटाने पर 0 बचता है। यही शेषफल है।
102 − 102 = 0
इसलिए, 102 = 51 × 2 + 0
शेषफल शून्य है, इसलिए रुकें। आख़िरी भाजक 51 ही HCF है।
867 को 51 से भाग देने पर कुछ नहीं बचता।
867 ÷ 51 = 17
255 भी 51 से पूरा-पूरा बँटता है।
255 ÷ 51 = 5
HCF = 51
पहले विकल्प चुनें। फिर उत्तर और उसका कारण देखें। यह समझ की जाँच है।