2-анықтама: Бірнеше сандардың бәрін бөлетін санды осы сандардың ортақ бөлгіші, ортақ бөлгіштердің ең үлкенін ең үлкен ортақ бөлгіш (ЕҮОБ) деп атайды, m және n сандарының ең үлкен ортақ бөлгішін ЕҮОБ(m,n) не (m,n) деп белгілейді.
ЕҮОБ-ті табу алгоритмі: Берілген сандарды жай көбейткіштерге жіктейміз.
Барлық сандарға ортақ көбейткіштерді тауып көбейтіндісін аламыз.
3-анықтама: Өзара жай сандар деп ЕҮОБ-і 1-ге тең сандарды айтамыз.
4-анықтама: Бірнеше сандардың бәріне де бөлінетін ең кіші санды сол сандардың ең кіші ортақ еселігі (ЕКОЕ) дейді, m және n сандарының ең кіші ортақ еселігін ЕКОЕ(m,n) не [m,n] деп белгілейді.
ЕКОЕ-ті табу алгоритмі: Берілген сандарды жай көбейткіштерге жіктейміз.
Алғашқы санның барлық көбейткіші мен келесі сандардың алғашқы санға кірмеген көбейткіштерінің көбейтіндісін аламыз.
ЕҮОБ-ті табудың Евклид алгоритмі төмендегі теоремаға негізделеді.
2-теорема: а және в сандарының кез келген ортақ бөлгіші a – b санының бөлгіші болады.
Дәлелдеме: a ⁞ с, b⁞с болса a =mc , b =nc болады да
a - b =mc-nc=(m-n)c.
3-теорема: a санын в санына бөлгенде бөлінді - q, қалдық -r болса, онда
ЕҮОБ (a, b)=ЕҮОБ (b, r) . (1)
3-теореманы пайдаланып a, b сандарының ЕҮОБ-ін қалай табуға болатынын қарастырайық. Қалдықпен бөлуді тізбектей орындау арқылы шектеулі қадамнан соң 0 қалдық алатынымыз түсінікті. Себебі әр қалдық өзінің алдындағы қалдықтан кем және одан кем емес болатындықтан шектеусіз жалғасуы мүмкін емес. Демек, қалдық нольге тең болғанда 3-теорема бойынша ЕҮОБ соңғы 0-ге тең емес қалдыққа тең болады. Бұл тәсілді Евклид алгоритмі деп атайды.
4-теорема: Екі оң бүтін санға Евклид алгоритмін қолданғанда алғашқы нөлге тең қалдықтың алдындағы қалдық бұл сандардың ЕҮОБ-і болады.
