a और b दो धनात्मक पूर्णांक दिए रहने पर ऐसी अद्वितीय अऋणात्मक पूर्णांक (पूर्ण संख्याएँ) q और r उपस्थित है कि
a=bq+r , जहाँ 0 ≤ r＜b
यूक्लिड विभाजन एल्गोरिथ्म इसी प्रमेयिका पर आधारित है और दो दत्त धनात्मक संख्याओं के म० स०(H.C.F) ज्ञात करने की एक तकनीक(Technique)हैं।
हम जानते है कि दो धनात्मक संख्याओं a और b का म० स०(H.C.F)वह महत्तम धनात्मक पूर्ण संख्या d है जिससे a और b दोनों विभाज्य है।अब हम एक उदहारण द्वारा यह दर्शाते हैं कि यूक्लिड विभाजन एल्गोरिथ्म के अनुप्रयोग से दो धनात्मक संख्याओं के म० स० किस प्रकार ज्ञात किया जा सकता हैं।
माना कि हमें 480 और 75 म० स०(H.C.F) ज्ञात करना है।
यहाँ a =480 ,b =75 (a >b)
यूक्लिड प्रमेयिका से ,
a=bq+r , जहाँ 0 ≤ r＜b
480 =75×6+30
अब हम भजाक 30 और शेष 15 पर विचार करते हैं।
विभाजन प्रमेयिका से ,हम पाते हैं की
30 =15×2 +0
अब शेष 0 है और इसीलिए हम आगे नहीं जा सकते हैं।अतः हम यहाँ रुक जाते हैं।हम 480 और 75 को अभाज्य गुणनखंडों में गुणनखंड करने पर देखते हैं कि 480 और 75 का HCF भाजक 15 है।
