Největšího společného dělitele d dvou celých čísel a, b budeme označovat   .

Neznámější algoritmus pro určení největšího společného dělitele je Euklidův algoritmus. Tento algoritmus vychází z tzv. celočíselného dělení se zbytkem podle vztahu:

       

Je to velice výhodný algoritmus, protože počet dělení potřebných pro výpočet největšího společného dělitele dvou přirozených čísel nepřesáhne pětinásobek počtu cifer menšího z čísel. Postup ukážeme na konkrétním příkladě. Hledejme největšího společného dělitele např. čísel (525, 231). Dostáváme:

       

nyní použijeme stejný postup na 231(dělitele) a 63 (zbytek),

       

podobně postupujeme dál,

       
       

V případě, že se zbytek rovná 0 postup zastavíme a dá se ukázat, že poslední dělitel (v našem případě 21) je největším společným dělitelem čísel 525 a 231. (Obecně poslední nenulový zbytek je největším společným dělitelem čísel).
S největším společným dělitelem souvisí pojem nejmenšího společného násobku. Přirozené číslo m je nejmenším společným násobkem celých čísel a, b, platí-li:

        1) každé z čísel a, b dělí přirozené číslo m,
        2) jestli je celé číslo c dělitelné oběma čísly a, b, pak je dělitelné i číslem m.