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