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