Euclidean Algorithm Command
For the sake of having fun and to get introduced to the matter a short tail-recursive routine which does with \numexpr from the ε-TeX-extensions for the subtraction.
(One could replace \number\numexpr...\relax by an own \romannumeral-expansion-driven expandable subtraction-routine. But why? Nowadays LaTeX doesn't work without ε-TeX-extensions.)
It is suitable only for calculating gcds of natural numbers.
It does not print the single steps. It just delivers the result.
There is no checking implemented if arguments form natural numbers/if the requirements for the arguments are fulfilled.
Instead of using temporary macros as variables and doing temporary assignments all the time for storing values of variables, macro arguments are used as "variables". In the tail-recursive loop the values of "variables" are changed by changing the corresponding macro-arguments for the next iteration.
\documentclass{article}
%% Pseudocode:
%%
%% Euclid(#1,#2) // Calculates gcd(#1,#2).
%% // #1 and #2 are to be _natural_ numbers !!
%%
%% WHILE #2 =/= 0
%% IF #1 > #2 THEN
%% #1 := #1 - #2
%% ELSE
%% #2 := #2 - #1
%% ENDIF
%% ENDWHILE
%% RESULT := #1
%%
\newcommand\UDPassFirstToSecond[2]{#2{#1}}%
\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%
\newcommand\Euclid[2]{%
\ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{#1}{%
\ifnum#1>#2 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\expandafter\Euclid\expandafter{\number\numexpr#1-#2\relax}{#2}%
}{%
\expandafter\UDPassFirstToSecond\expandafter{\number\numexpr#2-#1\relax}{\Euclid{#1}}%
}%
}%
}%
\begin{document}
gcd(377; 610) is: \Euclid{377}{610}
\noindent\hrulefill
gcd(144; 960) is: \Euclid{144}{960}
\noindent\hrulefill
gcd(960; 144) is: \Euclid{960}{144}
\end{document}
For the sake of having more fun an expandable tail-recursive routine which does with \numexpr from the ε-TeX-extensions for the subtraction.
It is suitable for calculating gcds of integers.
It does print the single steps.
There is no checking implemented if arguments form integers/if the requirements for the arguments are fulfilled.
Due to \romannumeral-expansion the result is delivered after "hitting" with \expandafter twice.
You might consider doing arithmetic and comparison of numbers by means of the expandable routines of the package bigintcalc.
By the way:
The routine "says" that gcd(0,0) is undefined.
It "says" so because it is an implementation of Euclid's algorithm while Euclid left gcd(0,0) undefined.
If "greatest" in "greatest common divisor" does refer to the partial order of divisibility on the natural numbers, then gcd(0,0)=0.
Besides this, if "greatest" in "greatest common divisor" does refer to the partial order of divisibility on the natural numbers, then there usually is not just one gcd. E.g., if the natural number x is the greatest common divisor referring to the order of integers, then referring to the partial order of divisibility on the natural numbers, gcds are x and -x.
Changing the routine accordingly should be straightforward and therefore is left as an exercise for the interested. ;->
\documentclass{article}
\usepackage{amsmath}
\newcommand\UDPassFirstToSecond[2]{#2{#1}}%
\newcommand\UDExchange[2]{#2#1}%
\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%
\csname @ifdefinable\endcsname\UDstopromannumeral{\chardef\UDstopromannumeral=`\^^00}%
\newcommand\Euclidean[2]{%
\romannumeral
% Wrapping between braces as argument of \UDExchange might help ensuring that
% things won't get disturbed if carried out insige a tabular-environment or
% the like.
\expandafter\UDExchange\expandafter{%
\romannumeral
\expandafter\UDPassFirstToSecond
\expandafter{\number#2}%
{\expandafter\EuclideanSignCheck\expandafter{\number#1}}%
}{\UDstopromannumeral}%
}%
\newcommand\EuclideanSignCheck[2]{%
\ifnum#1=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
\ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
\UDstopromannumeral
\[\begin{gathered}\text{The gcd of #1 and #2 is not defined.}\end{gathered}\]%
}{%
\expandafter\UDPassFirstToSecond\expandafter{%
\romannumeral
\expandafter\UDExchange
\expandafter{\number\ifnum#2<0 -\fi\number#2.}%
{\UDstopromannumeral The gcd of #1 and #2 is }%
}{\UDstopromannumeral\[\begin{gathered}\text}%
\end{gathered}\]%
}%
}{%
\ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
\expandafter\UDPassFirstToSecond\expandafter{%
\romannumeral
\expandafter\UDExchange
\expandafter{\number\ifnum#1<0 -\fi\number#1.}%
{\UDstopromannumeral The gcd of #1 and #2 is }%
}{\UDstopromannumeral\[\begin{gathered}\text}%
\end{gathered}\]%
}{%
\ifnum#1<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\ifnum#2<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\expandafter\UDPassFirstToSecond
\expandafter{\number-#2}%
{\expandafter\EuclideanLoopStart\expandafter{\number-#1}}%
{\UDfirstoftwo}%
}%
{\expandafter\EuclideanLoopStart\expandafter{\number-#1}{#2}{\UDfirstoftwo}}%
}%
{%
\ifnum#2<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\expandafter\UDPassFirstToSecond
\expandafter{\number-#2}%
{\EuclideanLoopStart{#1}}%
{\UDfirstoftwo}%
}%
{\EuclideanLoopStart{#1}{#2}{\UDsecondoftwo}}%
}%
{The gcd of #1 and #2 is equal to }%
}%
}%
}%
\newcommand\EuclideanLoopStart[4]{%
%#1 = absolute value of 1st number
%#2 = absolute value of 2nd number
%#3 = \UDfirstoftwo/\UDsecondoftwo - flag indicating if switching sign occurred
%#4 = begin of result-phrase, holding initial numbers
#3{%
\EuclideanLoop{#1}{0}{#2}{#1}{}{#4}{the gcd of #1 and #2:}%
}{%
\EuclideanLoop{#1}{0}{#2}{#1}{}{#4}{}%
}%
}%
\newcommand\EuclideanLoop[7]{%
%#1 = minuend
%#2 = amount of subtractions since last switching subtrahend to minuend
%#3 = subtrahend
%#4 = value of minuend at last switching subtrahend to minuend
%#5 = \\-separated list of steps
%#6 = begin of result-phrase, holding initial numbers
%#7 = phrase to insert at the begin
\ifnum#3=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\expandafter\UDExchange\expandafter{%
\romannumeral
\ifx\relax#5\relax\expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral}{%
\ifx\relax#7\relax\expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{\UDstopromannumeral}{%
\UDstopromannumeral\text{\textit{[#6#7]}}\\[0.5ex]%
}%
\begin{aligned}#5\end{aligned}\\[0.5ex]%
}%
}{\UDstopromannumeral\[\begin{gathered}}%
\text{#6#4.}\end{gathered}\]%
}{%
\ifnum#1<#3 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
{%
\EuclideanLoop{#3}{0}{#1}{#3}{#5\mathbf{#4}&=#2\cdot\mathbf{#3}+\mathbf{#1}\\}%
}{%
\expandafter\UDPassFirstToSecond
\expandafter{\number\numexpr#2+1\relax}{%
\expandafter\EuclideanLoop\expandafter{\number\numexpr#1-#3\relax}%
}{#3}{#4}{#5}%
}%
{#6}{#7}%
}%
}%
\begin{document}
\Euclidean{377}{610}
\noindent\hrulefill
\Euclidean{144}{960}
\noindent\hrulefill
\Euclidean{960}{144}
\noindent\hrulefill
\Euclidean{-1380451}{24361}
\noindent\hrulefill
\Euclidean{0}{-12}
\noindent\hrulefill
\Euclidean{-12}{0}
\noindent\hrulefill
\Euclidean{0}{0}
\noindent\hrulefill
\begin{verbatim*}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{%
\Euclidean{-1380451}{24361}%
}%
\end{verbatim*}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{%
\Euclidean{-1380451}{24361}%
}%
\begingroup\ttfamily\frenchspacing\string\test: \meaning\test\endgroup
\end{document}
You can use an alignment, accumulating material as you go on and delivering it at the end.
\documentclass{article}
\usepackage{amsmath}
\newif\ifgeq
\newcount\a
\newcount\b
\newcount\r
\newcount\q
\newcount\step
\newcommand{\euclidean}[3][1]{%
\[\begin{gathered}
\step=#1 \a=#2 \b=#3
\gdef\sofar{}%
\gdef\result{\number\b}%
\loop\ifnum\b>0
\q=0
\r=\a
\find
\printIntDiv
\a=\b
\b=\r
\repeat
\begin{aligned}\sofar\end{aligned} \\[0.5ex]
\text{The gcd of $#2$ and $#3$ is equal to $\result$}
\end{gathered}\]
}
\def\isgeq{\ifnum\r<\b \global\geqfalse\fi}
\def\find{{% <-- group
\global\geqtrue
\isgeq
\loop\ifgeq
\global\advance\q by1
\global\advance\r by-\b
\isgeq
\repeat
}}
\def\printIntDiv{%
\ifnum\step=1
\xdef\sofar{%
\unexpanded\expandafter{\sofar}%
\number\a &= \number\q \cdot \number\b + \number\r\noexpand\\
}%
\xdef\result{\number\b}%
\fi
}
\begin{document}
\euclidean{377}{610}
\euclidean{24}{18}
\euclidean{4}{2}
\end{document}
A “simpler” implementation with expl3
\documentclass{article}
\usepackage{amsmath}
\ExplSyntaxOn
\tl_new:N \l_needle_euclid_steps_tl
\tl_new:N \l_needle_euclid_gcd_tl
\cs_new_protected:Nn \needle_euclid_steps:nn
{
\tl_put_right:Nx \l_needle_euclid_steps_tl
{
#1 &= \int_div_truncate:nn { #1 } { #2 } \cdot #2 + \int_mod:nn { #1 } { #2 } \exp_not:N \\
}
\int_compare:nTF { \int_mod:nn { #1 } { #2 } > 0 }
{
\needle_euclid_steps:ne { #2 } { \int_mod:nn { #1 } { #2 } }
}
{
\tl_set:Nn \l_needle_euclid_gcd_tl { #2 }
}
}
\cs_generate_variant:Nn \needle_euclid_steps:nn { ne }
\NewDocumentCommand{\euclidean}{mm}
{
\[
\needle_euclid_steps:nn { #1 } { #2 }
\begin{gathered}
\begin{aligned}
\l_needle_euclid_steps_tl
\end{aligned} \\[0.5ex]
\text{The~gcd~of~$#1$~and~$#2$~is~$\l_needle_euclid_gcd_tl$}
\end{gathered}\]
}
\ExplSyntaxOff
\begin{document}
\euclidean{377}{610}
\euclidean{24}{18}
\euclidean{4}{2}
\end{document}
The main function \needle_euclid_steps:nn does the job of computing quotient and remainder; it appends the step and recursively calls itself unless the last remainder is zero. At this point it records the last remainder and quits the recursion.
Just computing the gcd is much simpler, but the idea is the same
\ExplSyntaxOn
\NewExpandableDocumentCommand{\computegcd}{mm}
{
\int_compare:nTF { #2 = 0 }
{ #1 } % #2 = 0, do nothing and return #1
{ \needle_gcd:nn { #1 } { #2 } }
}
\cs_new:Nn \needle_gcd:nn
{
\int_compare:nTF { \int_mod:nn { #1 } { #2 } = 0 }
{ #2 }
{ \needle_gcd:ne { #2 } { \int_mod:nn { #1 } { #2 } } }
}
\cs_generate_variant:Nn \needle_gcd:nn { ne }
\ExplSyntaxOff