В помощь в понимании алгоритма Евклида 1

Рассмотрим рис. 1.

На нем изображен прямоугольник, поделенный на q секций, каждая из которых имеет площадь, равную натуральному числу b, и  осталась одна секция с площадью, равной натуральному числу r, причем r < b. Из рисунка 1 также видно, что общий прямоугольник (площадь которого обозначим через a), прямоугольники секций с площадью b и прямоугольник с площадью r, имеют  вертикальную сторону с одной и той же длиной с.  Тогда мы можем представить площади так: 

b = c * m;

 r = c * n. 

Все, что отличает прямоугольники b и r - это ширина другой стороны (n < m). Тогда a = bq + r=cmq + cn=c(mq+n). То есть, площадь a составляется из q площадей b и площади r. В свою очередь, площадь b  это произведение стороны с длинами c и m, а площадь r - это произведение длин сторон c и n. Это довольно хорошо видно на рисунке, что длина общего прямоугольника площади a равна mq+n. Число c тут может быть от 1 до бесконечности. Для случая 0 и отрицательных чисел все развивается из этих же понятий. Ограничимся натуральными числами.

Таким образом, числа вроде a можно получать из чисел m и n (пусть даже взаимно простых), складывая несколько (q) чисел m и одно число n, при этом предварительно умножая сумму из q чисел m и число n на число c (натуральное).