Алгоритм Евкліда. Найбільший спільний дільник і найменше спільне кратне

Має місце теорема про ділення з остачею:

Процес послідовного ділення числа на число , потім числа на остачу, отриману при першому діленні, потім остачу на остачу, отриману при другому діленні і т.д. називають алгоритмом Евкліда, застосованим до чисел і .

Найбільше натуральне число, на яке діляться числа і , називається найбільшим спільним дільником цих чисел.

Найменше натуральне число, яке ділиться на числа і називається найменшим спільним кратним цих чисел.

Найбільший спільний дільник чисел і позначають через або НСД , а найменше спільне кратне - або НСК .

При застосуванні алгоритму Евкліда до чисел і остання відмінна від нуля остача дорівнює найбільшому спільному дільнику цих чисел.

Мають місце теореми: