दो संख्याएँ 252 और 594 हैं।
यूक्लिड विभाजन एल्गोरिथ्म (Euclid’s division algorithm) से HCF निकालना है।
बड़ी संख्या को छोटी से भाग दें। फिर पिछले भाजक (Divisor) को शेषफल (Remainder) से भाग देते जाएँ। शेषफल 0 होने पर अंतिम भाजक ही HCF है।
यूक्लिड विभाजन प्रमेयिका: a = bq + r, जहाँ 0 ≤ r < b। यहाँ a भाज्य, b भाजक, q भागफल और r शेषफल है।
252, 594 में 2 बार जाता है। गुणा करके घटाएँ।
252 × 2 = 504; 594 − 504 = 90
इसलिए 594 = 252 × 2 + 90।
अब पिछले भाजक 252 को शेषफल 90 से भाग देंगे।
90, 252 में 2 बार जाता है। गुणा करके घटाएँ।
90 × 2 = 180; 252 − 180 = 72
इसलिए 252 = 90 × 2 + 72।
अब पिछले भाजक 90 को शेषफल 72 से भाग देंगे।
72, 90 में 1 बार जाता है। गुणा करके घटाएँ।
72 × 1 = 72; 90 − 72 = 18
इसलिए 90 = 72 × 1 + 18।
अब पिछले भाजक 72 को शेषफल 18 से भाग देंगे।
18, 72 में 4 बार जाता है। गुणा करके घटाएँ।
18 × 4 = 72; 72 − 72 = 0
इसलिए 72 = 18 × 4 + 0।
शेषफल शून्य है। यहीं रुकें: आख़िरी भाजक 18 ही HCF है।
HCF = 18।
इन भागों में शेषफल शून्य है।
252 ÷ 18 = 14; 594 ÷ 18 = 33
HCF(252, 594) = 18।