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