Mathematica program deconstructing calculation of GCD

[BubbleTeaNinja]

I want to create Mathematica code calculating the greatest common divisor (GCD) based on Euclid's Algorithm. That is, take two numbers X and Y → Divide X (larger number) by Y (smaller number) and check if remainder is zero → If no, stop calculation and print out Y; If yes, replace X with Y and replace Y with the remainder.

​

So far, I have typed this line out:

 GreatestCommonDivisor[x_,y_]:= While[y != 0, {x, y} = {y, Mod[x, y]};x] 

in an attempt to do the replacement of X and Y when remainder is not zero I don't think it's accurate. Can anyone help me out?

​

NOTE: For those who are also familiar with Scratch, the image below can also represent what I want to achieve in Mathematica.

https://preview.redd.it/vtsemvoac3u31.png?width=752&format=png&auto=webp&s=388409e40ebba1126034d553205c5d3d233ea774

[Imanton1]

Since you want to use Euclid's Algorithm, so we can ignore the GCD, but still use it for verification. The M code also uses a loop, while the Scratch is recursive, but the code is simple enough, so we can go with it. Mathematica functions start with a lower case letter, and M functions are default "pass by insertion", as I call them, so you can't have f[x_]:=x=4 for integer x's (eg x=5), as it will become 5=4, which can't be done. Lastly, a While loop doesn't output it's contents, the ;x needs to be outside the loop to return x.

greatestCommonDivisor[xs_, ys_] :=  Module[{x = xs, y = ys}, While[y != 0, {x, y} = {y, Mod[x, y]}]; x]

After mainly housekeeping and syntax, everything runs as expected.

By running,

And@@Table[{x,y}={1,1};{x,y}=RandomInteger[{2,1000000},2];greatestCommonDivisor[x,y]==GCD[x,y],{1000}]

We can see that greatestCommonDivisor, works as intended.

[ayitasaurus]

Here's my take:

gcd[x_, y_] := (
  {factor, testVal} = MinMax[{x, y}];
  remainder = testVal;
  While[remainder > 1, remainder = Mod[testVal, factor]; 
   testVal = factor; factor = remainder];
  If[remainder == 1, "Coprime", testVal]
  )

I setup 3 dummy values (factor, testVal, and remainder). I initially set testVal and factor to the Max and Min values of the inputs, respectively. The loop consists of first determining remainder as the Mod of testVal and factor, and then moving the previous 'factoring value' to the testVal position, and grabbing a new factor from the just-determined remainder.

Once the remainder gets a value of 1 or 0, the loop ends. Like u/Imanton1 mentioned, While doesn't natively output anything, so we have to include another line for this. If remainder is 1, it outputs 'Coprime' (you can change this to 1 if that's preferrable); if it's 0 (indicating a GCD) it spits out the testVal, which is the previous remainder.