Алгоритм Евкліда

Для однозначно визначені числа такі, що . – частка, – остачі, .

Будемо говорити, що ділиться на (націло) або ділить (позначається ), якщо .

Найбільший спільний дільник – . Означимо .

Числа та взаємно прості, якщо .

Алгоритм знаходження , :

1. , , .

1. Ділимо на і отримуємо .
2. Якщо , то прийняти і перейти на крок 2. Інакше .

Вправа. Довести збіжність за скінченну кількість кроків .

Твердження. Для кожної пари взаємно простих та можна знайти такі числа та , що .

Доведення. За умови, що на передостанньому кроці алгоритму Евкліда . Нехай ця рівність виконується для -ого кроку:

Враховуючи, що , отримуємо твердження.

Розширений алгоритм Евкліда:

1. Покласти , , , , .

1. 
2. Обчислити ,
3. Якщо , то прийняти і перейти на крок 2. Інакше

Твердження. , , де – кількість ітерацій.

Доведення. При , при . Допустимо, що виконується на -ому кроці. Тоді . Отже твердження виконується для всіх .

Вправа. Довести, що рівний найменшому додатному числу вигляду , де та – цілі.