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

Алгоритм Евклида для нахождения наибольшего общего делителя. Даны два отрезка - и надо найти наибольший отрезок, которому кратны оба данных отрезка. Алгоритм Евклида - это большее делим на меньшее, а потом меньшее на остаток. Сначала больший отрезок делим на меньший.
Замеряю меньший отрезок и откладываю меньший на большем - получается один целый кусочек и остаток.
150 / 96 = 1 ост 54
Замеряю остаток и откладываю на меньшем отрезке. Получается опять один целый кусочек и остаток.
96 / 54 = 1 ост 42
Замеряю остаток и откладываю на предыдущем остатке. Получается опять один целый кусочек и остаток.
54 / 42 = 1 ост 12
Замеряю остаток и откладываю на предыдушем остатке. Получается три целых кусочка и остаток.
42 / 12 = 3 ост 6
Замеряю остаток и откладываю на предыдущем остатке. Получается ровно два целых кусочка.
12 / 6 = 2
Этот кусочек и есть НОД. И вот почему: предыдущий остаток содержит два целых кусочка, а каждый предыдущий остаток укладывается в предпредыдущем целое число раз, то есть и предпредыдущий остаток и остаток до него и изначальное целое - все делятся на наш последний кусочек нацело.

НОД(150,96) = 6

Уроки курса