एक मिठाई विक्रेता के पास 420 काजू की बर्फियाँ और 130 बादाम की बर्फ़िया हैं। वह इनकी ऐसी ढेरियां बनाना चाहता है कि प्रत्येक ढेरी में बर्फियों कि संख्या समान रहे तथा ये ढेरियाँ बर्फी की परात में न्यूनतम स्थान घेरे । इस काम के लिए , प्रत्येक ढेरी में कितनी बर्फियाँ रखी जा सकती हैं?

Explanation

हम 420 तथा 130 का H.C.F. ज्ञात करते हैं। इस H.C.F. से प्रत्येक ढेरी में रखी जा सकने वाली बर्फियों की अधिकतम संख्या ज्ञात होती है, जिससे ढेरियाँ की संख्या न्यूनतम होगी और परात में ये ढेरियाँ न्यूनतम स्थान घेरेंगी ।
यूक्लिड एल्गोरिथ्म का प्रयोग करके 420 तथा 130 का H.C.F. ज्ञात करते हैं।
`420=130xx3+30`
`130=30xx4+10`
`30=10xx3+0`
अतः 420 तथा 130 का H.C.F. 10 है।
इस प्रकार मिठाई विक्रेता दस-दस की ढेरी बना सकता है।