Модуль: НОД и НОК. Учебные программы

Наибольший общий делитель (НОД) чисел A, B принято обозначать (A,B).
Если А, В - нечетные числа, то (А,В) - нечетное число.
Также нетрудно заметить, что:
\((a,1)=(1,a)=1 \\n (2\cdot a,2\cdot b+1)=(a,2\cdot b+1)\)
Эти простые правила позволяют модифицировать процедуру нахождения НОД для нечетных чисел.
Из Большего вычти Меньшее и запиши вместо Большего
Пока одно из чисел чётное , то дели чётное на 2
Если полученные числа равны или одно из чисел равно одному, то прекращай  работу
Меньшее из чисел и есть НОД
Для натуральных нечётных чисел A, B фрагмент кода нахождения НОД может выглядеть так:
# A, B - нечетные натуральные числа  
while ( (A != B) and (A != 1) and (A != 1)):
     if A > B:
         A = A - B
        while ( A % 2 == 0) :
              A = A // 2
     else :
         B = B - A
         while ( B % 2 == 0 ) :
               B = B // 2
if  A < B :
   gcd = A  # gcd  - наибольший общий делитель чисел A, B
else :
    gcd = B 

Замечание: Нетрудно убедиться в том, что данный алгоритм работает и в случае, когда только одно число нечётное