Наибольший общий делитель
g = gcd(A,B)
вычисляется с помощью Алгоритма Евклида. [1]
[g,u,v] = gcd(A,B)
вычисляется с помощью расширенного Алгоритма Евклида. [1]
[1] Knuth, D. “Алгоритмы A и X.” Искусство программирования, издания 2, разделяют 4.5.2. Чтение, MA: Аддисон-Уэсли, 1973.