यूक्लिड की विभाजन एल्गोरिथ्म का प्रयोग करते हुए, ऐसी सबसे बड़ी संख्या ज्ञात कीजिए, जिससे 1251, 9377 और 15628 को भाग देने पर शेषफल क्रमशः 1, 2 और 3 प्राप्त हो ।

Explanation

दिए गए शेषफलों को संख्याओं से घटाने पर प्राप्त संख्याएँ
`1251-1=1250`
`9377-2=9375`
`"और "15628-3=15625`
यहाँ `1250 lt 9375` है। 1250 और 9375 पर यूक्लिड प्रमेयिका का प्रयोग करने पर,
`9375=1250xx7+625`
चूँकि शेषफल शून्य नहीं है, तब पुनः
`1250=625xx2+0`
यहाँ शेषफल शून्य प्राप्त हो गया है।
अब `1250 lt 15625`
`therefore 1250` और 15625 पर यूक्लिड प्रमेयिका का प्रयोग करने पर,
`15625=1250xx12+625`
यहाँ शेषफल 625 प्राप्त हुआ ।
`1250=625xx2+0`
अतः शेषफल शून्य प्राप्त हो गया है। दोनों ही स्थितियों में भाजक 625 प्राप्त हुआ है।
अतः बड़ी से बड़ी संख्या 625 है।