Алгоритм Евкліда пошуку найбільшого спільного дільника можна сформулювати таким чином. Нехай {a_n} — така послідовність елементів евклідового кільця (наприклад, множини цілих чисел або множини многочленів), у якій a_n + 1 — остача від ділення a_n – 1 на a_n при n = 2, 3, … При цьому евклідова норма (відповідно абсолютна величина цілого числа або степінь многочлена) членів послідовності спадає і набуває натуральних значень. Через це існує таке натуральне k, при якому a_k відмінне від 0, a_k + 1 = 0. Тоді найбільші спільні дільники (НСД) пар сусідніх членів такої послідовності збігаються з a_k, що є дільником усіх членів послідовності.
      Відомо, що НСД(a, b), можна подати сумою ax + by, що має найменшу евклідову норму. З означеннями й доведеннями відповідних тверджень можна ознайомитися, наприклад, за таким посібником: Олександр Рудик. Початки алгебри, аналізу, аналітичної геометрії і теорії ймовірностей. — Тернопіль, Навчальна книга – Богдан, 2005, 416 с. Цей посібник є викладом теоретичних основ відповідних розділів шкільного курсу математики, адаптованим для учнів класів з поглибленим вивченням математики.
      Зробимо зауваження щодо способу знаходження коефіцієнтів x та y у поданні найбільшого спільного дільника лінійною сумою. Нехай у послідовності, побудованій згідно з алгоритмом Евкліда, справджуються такі рівності:

      Позначимо через q_n частку від ділення a_{n – 1} на a_n . Для справдження такої рівності:

зі зліченої множини розв'язків можна вибрати:

      Зауважимо, що і первісний, і розширений алгоритми Евкліда можна застосовувати і до цілих чисел, і до многочленів. Пропонуємо розглянути приклади програм мовами Pascal і С++, що використовують описаний алгоритм для невід'ємних цілих чисел.