The Euclidean Algorithm (for finding the greatest common divisor)

Question

The Challenge

Write a program or function that takes two input integers, i and j, and outputs their greatest common divisor; calculated by using the Euclidean algorithm (see below).

---

Input

Input may be taken as a space-delimited string representation of i and j or as two separate integers. You can assume that integers will be less than or equal to 10,000. You can also assume that the input integers will not be prime to one another.

---

Euclidean Breakdown

The larger number between i and j is divided by the smaller as many times as possible. Then, the remainder is added. This process is repeated with the remainder and the previous number, until the remainder becomes 0.

For example, if the input was 1599 650:

1599 = (650 * 2) + 299
 650 = (299 * 2) + 52
 299 = (52 * 5) + 39
 52 = (39 * 1) + 13
 39 = (13 * 3) + 0

The final number, 13, is the greatest common divisor of the two input integers. It can be visualized like this:

---

Output

Your output must be the breakdown in the form above, followed by a newline and the GCD. It can be output through any medium.

---

Examples

Inputs

18 27
50 20
447 501
9894 2628

Outputs

27 = (18 * 1) + 9
18 = (9 * 2) + 0
9
50 = (20 * 2) + 10
20 = (10 * 2) + 0
10
501 = (447 * 1) + 54
447 = (54 * 8) + 15
 54 = (15 * 3) + 9
 15 = (9 * 1) + 6
 9 = (6 * 1) + 3
 6 = (3 * 2) + 0
3
9894 = (2628 * 3) + 2010
2628 = (2010 * 1) + 618
2010 = (618 * 3) + 156
 618 = (156 * 3) + 150
 156 = (150 * 1) + 6
 150 = (6 * 25) + 0
6

Note: Outputs do not have to be spaced as they are above. The spacing is only for clarity. Parentheses are required.

---

Bonus

If your output is spaced as above, you may add a -10% bonus to your score.

• Level River St: 1. Can we assume the largest number is given first? 2. For the bonus, you mean the field width should be constant and just enough to allow for one space before the largest number? (with the spaces coming before the left parenthesis in the second column of numbers.) You should avoid ambiguous phrasing such as "as they are above" when the output is variable. It's OK if the required output is fixed.
• Level River St: Ok I see some examples have the largest number second
• Level River St: Your original title was OK, I've commented on what happened at meta.codegolf.stackexchange.com/q/7043/15599 . The phrase "greatest common denominator" was wrong however. "Denominator" relates to fractions. Googling "greatest common denominator" only gives results for "greatest common divisor / factor."
• Zach Gates: I thought the title was OK, but I changed it to "The" as to not displease anyone. Thanks for editing in "divisor", BTW. @steveverrill

Answer 1

Python 2, 70

f=lambda a,b:b and'%d=(%d*%d)+%d\n'%(a,b,a/b,a%b)*(a>=b)+f(b,a%b)or`a`

A recursive function that returns a multiline string. The function creates the first line, then appends it to the recursive result with the next pair of numbers in the Euclidean algorithm. Once the second number is zero, we take the string of the other number as the base case, causing it to be printed on its own line at the end.

The formatting is done via string substitution, using integer division to get the multiplicand.

One hiccup is needing to start with the larger number being taken mod the smaller number. Conveniently, if the numbers are in the wrong order, the first step of the Euclidian algorithm flips them. To prevent this step from being displayed, only add the current line if the first number is at least the second (equality is needed for, say f(9,9)).

Answer 2

CJam, (削除) 46 (削除ここまで) (削除) 43 (削除ここまで) 39 bytes

q~]3ドル*~\{N5$"=("3$:G'*3$Gmd")+"\}h]7>NG

Try it online in the CJam interpreter.

How it works

q~] e# Read all input, evaluate it and wrap the results in an array.
3ドル* e# Sort the array and repeat it thrice.
~\ e# Dump the array and swap its last two elements.
{ e# Do:
 N e# Push a linefeed.
 5$ e# Copy the sixth topmost element from the stack.
 "=(" e# Push that string.
 3$:G e# Copy the fourth topmost element from the stack. Save it in G.
 '* e# Push that character.
 3$ e# Copy the fourth topmost element from the stack.
 Gmd e# Push quotient and remainder of its division by G.
 ")+" e# Push that string.
 \ e# Swap the string with the remainder.
}h e# If the remainder is positive, repeat the loop.
]7> e# Wrap the stack in an array and discard its first seven elements.
NG e# Push a linefeed and G.

Answer 3

Pyth, 33 bytes

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H

Try it online: Demonstration or Test Suite

Explanation:

ASQWGs[H\=\(G\*/HG\)\+K%HG)A,KG)H
 Q read the two numbers from input
 S sort them
A and assign them to G and H
 WG while G != 0:
 K%HG assign H mod G to K
 s[H\=\(G\*/HG\)\+K ) join the following list items and print:
 H=(G*(H/G))+K
 A,KG assign K, G to G, H
 ) end while
 H print H

Answer 4

awk, (削除) 78 (削除ここまで) 77

x=1ドル{for(x<2ドル?x+=2ドル-(y=x):y=2ドル;t=y;x=t)print x"=("y"*"int(x/y)")+",y=x%y}0ドル=x

Sorting the input by size takes a lot of bytes :/
It comes down to this:

x=1ドル;
if(x<2ドル) x+=2ドル-(y=x); # add 2ドル subtract 1ドル and set y to 1ドル
else y=2ドル; # set y to 2ドル

Output

650 1599 (input)
1599=(650*2)+ 299
650=(299*2)+ 52
299=(52*5)+ 39
52=(39*1)+ 13
39=(13*3)+ 0
13

Just for the fun of it I made a properly spaced version too, giving me a score of 233 * 0.9 == 209.7 bytes.

Update I was able to shorten this from 285 bytes and now it works for arbitrarily long numbers if calling gawk4 with the -M option.

x=1ドル{x<2ドル?x+=2ドル-(y=x):y=2ドル;a=length(x);b=length(y);for(d=length(x%y);t=y;x=t){$++i=x;$++i=y;if(c<l=length($++i=int(x/y)))c=l;$++i=y=x%y}while(j<NF)printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",$++j,_,$++j,$++j,$++j}0ドル=x

But I still got a feeling I ran into some mental block there somewhere...

Output (gawk4 called with awk -M -f code.awk)

6837125332653632513763 18237983363879361 (input)
6837125332653632513763 = (18237983363879361 * 374883) + 15415252446024000
 18237983363879361 = (15415252446024000 * 1) + 2822730917855361
 15415252446024000 = (2822730917855361 * 5) + 1301597856747195
 2822730917855361 = (1301597856747195 * 2) + 219535204360971
 1301597856747195 = (219535204360971 * 5) + 203921834942340
 219535204360971 = (203921834942340 * 1) + 15613369418631
 203921834942340 = (15613369418631 * 13) + 948032500137
 15613369418631 = (948032500137 * 16) + 444849416439
 948032500137 = (444849416439 * 2) + 58333667259
 444849416439 = (58333667259 * 7) + 36513745626
 58333667259 = (36513745626 * 1) + 21819921633
 36513745626 = (21819921633 * 1) + 14693823993
 21819921633 = (14693823993 * 1) + 7126097640
 14693823993 = (7126097640 * 2) + 441628713
 7126097640 = (441628713 * 16) + 60038232
 441628713 = (60038232 * 7) + 21361089
 60038232 = (21361089 * 2) + 17316054
 21361089 = (17316054 * 1) + 4045035
 17316054 = (4045035 * 4) + 1135914
 4045035 = (1135914 * 3) + 637293
 1135914 = (637293 * 1) + 498621
 637293 = (498621 * 1) + 138672
 498621 = (138672 * 3) + 82605
 138672 = (82605 * 1) + 56067
 82605 = (56067 * 1) + 26538
 56067 = (26538 * 2) + 2991
 26538 = (2991 * 8) + 2610
 2991 = (2610 * 1) + 381
 2610 = (381 * 6) + 324
 381 = (324 * 1) + 57
 324 = (57 * 5) + 39
 57 = (39 * 1) + 18
 39 = (18 * 2) + 3
 18 = (3 * 6) + 0
3

Some newlines and tabs added

x=1ドル{
 x<2ドル?x+=2ドル-(y=x):y=2ドル;
 a=length(x);
 b=length(y);
 for(d=length(x%y);t=y;x=t)
 {
 $++i=x;
 $++i=y;
 if(c<l=length($++i=int(x/y)))c=l;
 $++i=y=x%y
 }
 while(j<NF)
 printf "%"a"d = %"b-length($(j+2))"s(%d * %"c"d) + %"d"d\n",
 $++j,_,$++j,$++j,$++j
}0ドル=x

I can save the lengths of the initial values for x, y and x%y in the beginning, because they can only get shorter each step. But for the factor I have to determine the maximum length before printing anything, because it's length can vary. I use $i as an array here, because it saves two characters compared to using a[i] every time.

Answer 5

C++, GCC compiler, 171 bytes( -10%, so 154 bytes)

okay so my first try..

#include<iostream>
using namespace std;
int main()
{
 int a,b,c;
 cin>>a>>b;
 if(a<b)
 swap(a,b);
 while(b>0)
 {
 c=a;
 cout<<a<<" = ("<<b<<" * "<<a/b<<") + "<<a%b<<endl;
 a=b;
 b=c%b;
 }
 cout<<a;
}

tips to code golf appreciated.

P.S. Is it necessary to count bytes of standard header files and int main while using c++? Excluding it reduces 50 bytes

• Devang Jayachandran: Note: I excluded the white space used to make the code pretty.

Answer 6

JavaScript (ES6), (削除) 74 (削除ここまで) (削除) 50 (削除ここまで) (削除) 62 (削除ここまで) (削除) 61 (削除ここまで) 55 bytes

f=(x,y)=>y?y>x?y:x+`=(${y}*${x/y|0})+${x%=y}
`+f(y,x):x

• Sacrificed 12 bytes allowing the integers to be passed in any order, rather than largest first.

---

Try It

f=(x,y)=>y?y>x?y:x+`=(${y}*${x/y|0})+${x%=y}
`+f(y,x):x
o.innerText=f(i.value=683712533265363251376,j.value=18237983363879361)
i.oninput=j.oninput=_=>o.innerText=f(+i.value,+j.value)

<input id=i type=number><input id=j type=number><pre id=o>

---

Explanation

f= :Assign the function to variable f ...
(x,y)=> :And take the two integer inputs as arguments via parameters x and y.
y? :If y is greater than 0 then
y>x? : If y is greater than x then
f(y,x) : Call f again, with the order of the integers reversed.
 : (This can only happen the first time the function is called.)
: : Else
x : Start building the string, beginning with the value of x.
+`=( : Append "=(".
${y} : The value of y.
* : "*"
${x/y|0} : The floored value of x divided by y
)+ : ")+"
${x%=y} : The remainder of x divided by y, which is assigned to x
 : (x%=y is the same as x=x%y.)
\n : A newline (a literal newline is used in the solution).
`+f(y,x) : Append the value f returns when y and the new value of x
 : are passed as arguments.
: :Else
x : Return the current value of x,
 : which will be the greatest common divisor of the original two integers.

Answer 7

T-SQL (2012+), 268 bytes

Implemented as an inline table function that executes a recursive CTE. Might be worthwhile trying to put formatting in for the 10% bonus, but that will have to wait.

CREATE FUNCTION E(@ INT,@B INT)RETURNS TABLE RETURN WITH M AS(SELECT IIF(@<@B,@B,@)A,IIF(@>@B,@B,@)B),R AS(SELECT A,B,A/B D,A%B R FROM M UNION ALL SELECT B,R,B/R,B%R FROM R WHERE 0<>R)SELECT CONCAT(A,'=(',B,'*',D,')+',R)R FROM R UNION ALL SELECT STR(B)FROM R WHERE R=0

Explanation and usage:

--Create the function
CREATE FUNCTION E(@ INT,@B INT)RETURNS TABLE RETURN
WITH
 --Order the input correctly
 M AS (
 SELECT IIF(@<@B,@B,@)A,
 IIF(@>@B,@B,@)B
 )
 --Recursive selection
 ,R AS (
 SELECT A,B,A/B D,A%B R FROM M -- Anchor query
 UNION ALL
 SELECT B,R,B/R,B%R FROM R -- Recurse until R = 0
 WHERE 0<>R
 )
SELECT CONCAT(A,'=(',B,'*',D,')+',R)R -- Concat results into output string
FROM R 
UNION ALL -- ALL required to maintain order
SELECT STR(B) -- Add final number
FROM R WHERE R=0
--Function Usage
SELECT * FROM E(447,501)
R
-----------------------------------------------------
501=(447*1)+54
447=(54*8)+15
54=(15*3)+9
15=(9*1)+6
9=(6*1)+3
6=(3*2)+0
3

Answer 8

Rev 1: Ruby, 86

Recursive algorithm, thanks to tip from Doorknob.

f=->i,j{j>i&&(i,j=j,i)
0<j ?(print i," = (#{j} * #{i/j}) + #{i%j}
";f[j,i%j]):puts(i)}

Rev 0: Ruby, 93

This really hasn't worked out well at all. The while loop takes up too many characters, especially with the end. I can't see a way of avoiding it. Recursion would require a named function instead of a lambda, which would also eat up a lot of characters.

->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}

Call it like this:

f=->i,j{j>i&&(i,j=j,i)
while j>0
print(i," = (#{j} * #{i/j}) + #{i%j}\n")
i,j=j,i%j
end
puts i}
I=gets.to_i
J=gets.to_i
f.call(I,J)

• Doorknob: You can use recursion via a=->i,j{...} and call a via a[1,2]—not sure if this would save you characters, though.
• Level River St: @Doorknob thanks for the tip, I wasn't aware of that syntax for calling lambda functions (see my use of f.call.) It is actually quite a bit shorter, but still a long way off Python.

Answer 9

PowerShell, 84

A recursive code block, stored in a variable. Invoke it with & $e num1 num2, e.g.:

$e={$s,$b=$args|Sort;if(!$s){$b}else{$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";&$e $s $r}}
PS D:\> & $e 9894 2628
9894=(2628*3)+2010
2628=(2010*1)+618
2010=(618*3)+156
618=(156*3)+150
156=(150*1)+6
150=(6*25)+0
6

In a more readable form, it does the following (nb. for clearer code, I've put the full commandlet names, more spaces in the string, and made the pipeline output commands explicit):

function Euclid {
 $small, $big = $args|Sort-Object #Sort argument list, assign to two vars.
 if (!$small) { #Recursion end, emit the last
 Write-Output $big #number alone, for the last line.
 } else { #main recursive code
 $remainder = $big % $small
 Write-Output "$big = ( $small* $(($big-$remainder)/$small)) + $remainder"
 Euclid $small $remainder
 }
}

One annoyance from a codegolf point of view; PoSh has no integer division, 10/3 returns a Double, but cast the result to an integer and it doesn't always round down, it rounds N.5 to the nearest even number - up or down. So [int](99/2) == 50.

That leaves two awkward choices:

$remainder = $x % $y
$quotient = [Math]::Floor($x/$y)
# or, worse
$remainder=$null
$quotient = [Math]::DivRem($x, $y, [ref]$remainder)

Which is why I have to burn some characters doing:

$remainder = $big % $small
($big - $remainder)/$small

Apart from that, it's the number of $$$$ and the lack of ternary operator which really hurts.

---

I also have an iterative version which, rather nicely, is also 84 characters:

{$r=1;while($r){$s,$b=$args|Sort;$r=$b%$s;"$b=($s*$(($b-$r)/$s))+$r";$args=$s,$r}$s}

Completely anonymous codeblock, so run it with

& {*codeblock*} 1599 650

Answer 10

PHP, 118 Bytes

for(list(,$n,$m)=$argv,$g=max($n,$m),$l=min($n,$m);$g;$g=$l,$l=$m)
echo$g,$l?"=($l*".($g/$l^0).")+".($m=$g%$l)."
":"";

Try it online!

PHP, 131 Bytes

for(list(,$n,$m)=$argv,$r=[max($n,$m),min($n,$m)];$r[+$i];)echo$g=$r[+$i],($l=$r[++$i])?"=($l*".($g/$l^0).")+".($r[]=$g%$l)."
":"";

Try it online!

-4 Bytes replace list(,$n,$m)=$argv with [,$n,$m]=$argv needs PHP>=7.1

Answer 11

C, 83 bytes

g(x,y,z){y&&(printf("%u=(%u*%u)+%u\n",x,y,x/y,z=x%y),z)?g(y,z,0):printf("%u\n",y);}

test and results

int main()
{g(18,27,0);
 g(50,20,0);
 g(447,501,0);
 g(9894,2628,0);
}
18=(27*0)+18
27=(18*1)+9
18=(9*2)+0
9
50=(20*2)+10
20=(10*2)+0
10
447=(501*0)+447
501=(447*1)+54
447=(54*8)+15
54=(15*3)+9
15=(9*1)+6
9=(6*1)+3
6=(3*2)+0
3
9894=(2628*3)+2010
2628=(2010*1)+618
2010=(618*3)+156
618=(156*3)+150
156=(150*1)+6
150=(6*25)+0
6

Answer 12

Japt, (削除) 43 (削除ここまで) (削除) 42 (削除ここまで) 41 bytes

My newfound Japt "skills" seem to be getting worse, not better!

?U>V?ßVU :[V'='(U'*V/U|0')'+V%=UR,ßVU]¬:V

Try it online

Answer 13

JS, 151

a=prompt("g","");b=prompt("l","");c=0;l=[a,b];for(var i=0;i<=1;i++){t=c;o=c+1;r=c+2;n=l[t]%l[o];if(n!==0){l[r]=n;c=c+1;i=0;}else{p=l[o];alert(p);i=2;}}

Answer 14

R, (削除) 90 (削除ここまで) 82 bytes

• -8 bytes golfed by pajonk

`?`=\(a,b)`if`(a<b,b?a,{cat(a,'= (',b,"*",a%/%b,') +',x<-a%%b,'
');`if`(x,b?x,b)})

Attempt This Online!

• pajonk: -8 bytes by making the a<->b swap also recursive.
• Glory2Ukraine: @pajonk I don't know how do you manage to reduce almost every code:)

Answer 15

C(gcc), 74 bytes

g(a,b){b?printf("%d=(%d*%d)+%d\n",a,b,a/b,a%b),g(b,a%b):printf("%d\n",a);}

code test:

main(){g(21,15);g(3,1);g(1,3);g(3,3);g(1,1);g(15,55);return 0;}

result:

C:\>a
21=(15*1)+6
15=(6*2)+3
6=(3*2)+0
3
3=(1*3)+0
1
1=(3*0)+1
3=(1*3)+0
1
3=(3*1)+0
3
1=(1*1)+0
1
15=(55*0)+15
55=(15*3)+10
15=(10*1)+5
10=(5*2)+0
5

Answer 16

Java 133

public void z(int i,int j){for(int d=1;d!=0;i=j,j=d){d=i%j;System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);}System.out.println(i);}

It doesn't do the regular Euclidean algorithm. Instead, it uses modulus and then computes the 2nd number to multiply by when it's printed out. You can also make this shorter by turning it into a lambda expression, but I'm not sure how.

public void z(int i, int j)
{
 for(int d=1;d!=0;i=j,j=d)
 {
 d=i%j;
 System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);
 }
 System.out.println(i);
}

• Kevin Cruijssen: I know it's been over 1.5 years, but you can remove the public , change the second println to print, and change d!=0 to d>0. Also, it's currently giving an incorrect output for the first rows. This can be fixed by adding if(d!=i) in front of System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);. So in total: void z(int i,int j){for(int d=1;d>0;i=j,j=d){d=i%j;if(d!=i)System.out.println(i+"=("+j+"*"+((i-d)/j)+")+"+d);}System.out.print(i);} (131 bytes & bug-fixed)

Answer 17

C# 115

First time on this forum

int g(int a,int b){(a,b)=a<b?(b,a):(a,b);Console.Write($"{a}=({b}*{a/b})+{a%b}\n");return a%b==0?b:g(b,a%b);}

• Glorfindel: Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work?

Answer 18

05AB1E, (削除) 32 (削除ここまで) 30 bytes

{R[D`‰«Â`"ÿ=(ÿ*ÿ)+ÿ",¤_#ιθ}1è,

Inputs as a pair [i,j]. Output is without spaces.

Try it online or verify all test cases.

The -10% bonus isn't worth it to output in the correct format, but here it is anyway:
48.6 bytes (54^† bytes - 10% bonus)
^{† Should have been -1 byte by removing the §, but there is a bug with j and integer-lists.}

{R[D`‰«¤_#¤UDιθ})øε§Zgj}øεR`"ÿ = (ÿ * ÿ) + ÿ"}Xa»„( Â:

Try it online or verify all test cases.

Explanation:

{ # Sort the (implicit) input-pair from lowest to highest
 R # Reverse it from highest to lowest
[ # Start an infinite loop:
 D # Duplicate the current pair
 ` # Pop one and push both values separated to the stack
 ‰ # Divmod: a,b → [a//b,a%b]
 « # Merge the pairs together: [a,b,a//b,a%b]
 Â # Bifurcate this quadruplet; short for Duplicate & Reverse copy
 ` # Pop and push the reversed items separated to the stack
 "ÿ=(ÿ*ÿ)+ÿ" # Push this string, where the `ÿ` are one by one filled with the values
 , # Pop and output it with trailing newline
 ¤ # Push the last value (`a%b`), without popping
 _ # If this is 0:
 # # Stop the infinite loop
 # (else)
 ι # Uninterleave it into two parts: [a,b,a//b,a%b] → [[a,a//b],[b,a%b]]
 θ # Pop and keep the last pair (`[b,a%b]`)
} # After the infinite loop:
 1è # Pop the final quadruplet, and leave its second item: `b`
 , # Pop and output it with trailing newline as well

{R[D`‰« # Similar as above
¤_# # Similar as above as well
 ¤ # Push the last item without popping again
 U # Pop and store it in variable `X`
 D # Duplicate the quadruplet
 ιθ} # Similar as above as well
) # Wrap the quadruplets of the stack into a list
 ø # Zip/transpose; swapping rows/columns
 ε # Map over each inner list
 § # Cast every integer to a string (†bug work-around for builtin `j`)
 Z # Push the largest integer, without popping
 g # Pop and push its length
 j # Potentially add leading spaces so all values in the list are of this length
 }ø # After the map: zip/transpose back
 ε # Map over each inner list:
 R` # Push the items in reverse order to the stack
 "ÿ = (ÿ * ÿ) + ÿ"
 # Push this string, where the `ÿ` are one by one filled with the values
 }Xa # After the map: append value `X`
 » # Join this list by newlines
 „( # Push string "( "
 Â # Bifurcate; short for Duplicate & Reverse copy: " ("
 : # Infinitely replace "( " to " ("
 # (after which the string is output implicitly as result)

Answer 19

APL(NARS), 38 chars

{⍵<1:⍺⋄⎕←⍺'=('⍵'*'(⌊⍺÷⍵)')+'t←⍵∣⍺⋄⍵∇t}

Note: if the number in left is small than the number in right, there is one print more, the one of swap...test:

 f←{⍵<1:⍺⋄⎕←⍺'=('⍵'*'(⌊⍺÷⍵)')+'t←⍵∣⍺⋄⍵∇t}
 42 f 15
 42 =( 15 * 2 )+ 12 
 15 =( 12 * 1 )+ 3 
 12 =( 3 * 4 )+ 0 
3
 6 f 15
 6 =( 15 * 0 )+ 6 
 15 =( 6 * 2 )+ 3 
 6 =( 3 * 2 )+ 0 
3
 3 f 3
 3 =( 3 * 1 )+ 0 
3
 1 f 3
 1 =( 3 * 0 )+ 1 
 3 =( 1 * 3 )+ 0 
1
 1 f 1
 1 =( 1 * 1 )+ 0 
1

Answer 20

Scala 3, 116 bytes

Golfed version. Attempt This Online!

def f(a:Int,b:Int):String=if(b==0)a.toString else if(a>=b)s"$a = (${a / b} * $b) + ${a % b}\n"+f(b,a%b)else f(b,a%b)

Ungolfed version. Attempt This Online!

object Main {
 def my_gcd(a: Int, b: Int): String = {
 if (b == 0) {
 a.toString
 } else if (a >= b) {
 s"$a = (${a / b} * $b) + ${a % b}\n" + my_gcd(b, a % b)
 } else {
 my_gcd(b, a % b)
 }
 }
 def main(args: Array[String]): Unit = {
 // Test cases
 println(my_gcd(18, 27))
 println(my_gcd(50, 20))
 println(my_gcd(447, 501))
 println(my_gcd(9894, 2628))
 }
}