# GCD using Euclidean Algorithm

My assignment is to calculate the GCD of two numbers n and m using the Euclidean Algorithm which basically states that if the remainder = 0 the GCD is the 2nd of the two numbers. SO my thought was to write a recursive program looking for the GCD of two numbers, if the remainder is not 0 then change n to m and m to r and then calculate the GCD of those two numbers until you get a remainder of 0. I am not strong with recursion and my program loops forever. Any help would be greatly appreciated!

MyBetterGCD[n_, m_] :=
Module[{q, r, DebugFlag = True},
r = Mod[n, m]; (*remainder*)
While[r != 0,
q = Floor[(n/m)]; (*quotient*)
n = m;
m = r;
MyBetterGCD[n, m];
];(*End While Loop*)
Return[m]
](*End Module*)

• Your loop never terminates because the variable r is never changed within the loop. You need to redeine r within the loop. – bill s Oct 2 '17 at 18:05
• – Coolwater Oct 2 '17 at 21:24

gcd[a_, 0] := a;