# CFLib.org – Common Function Library Project

## GCDee(m, n[, showWork])

##### Last updated March 07, 2010

Version: 1 | Requires: CF5 | Library: MathLib

Description:
Finds the GCD (greatest common factor [divisor]) of two numbers using the Extended Euclidean Algorithm. To express the GCD(a,b) = g as a linear combination of a and b, of the form ax + by = g. this program will always return the least positive result and will compute the value g as well. Optionally displays all of the steps in the calculation.

Return Values:
Returns a numeric value. Optionally outputs a string.

Example:

``````<cfoutput>
#GCDee(13,130,"Yes")#
</cfoutput>
``````

Parameters:

Name Description Required
m Positive integer. Yes
n Positive integer. Yes
showWork Boolean. Yes or No. Specifies whether to display work. Default is No. No

Full UDF Source:

``````/**
* Finds the GCD (greatest common factor [divisor]) of two numbers using the Extended Euclidean Algorithm.
*
* @param m      Positive integer. (Required)
* @param n      Positive integer. (Required)
* @param showWork      Boolean.  Yes or No.  Specifies whether to display work.  Default is No. (Optional)
* @return Returns a numeric value.  Optionally outputs a string.
* @author Shakti Shrivastava (shakti@colony1.net)
* @version 1, March 6, 2010
*/
function GCDee(m,n)
{
// initialize variables for calculations.
Var ShowWork=False;
Var r = arraynew(1);
Var q=arraynew(1);
Var s=arraynew(1);
Var t=arraynew(1);
Var iter=100;
Var j=3;
Var c1=0;
Var c2=0;
Var GCD=0;
Var pos_c1=0;
Var pos_c2=0;
r[1]=m;
r[2]=n;
s[1]=0;
s[2]=1;
t[1]=1;
t[2]=0;

If (ArrayLen(Arguments) eq 3 AND Arguments[3] eq "yes"){
ShowWork=True;
}

// handle possible divide by zero error.
if (r[2] eq 0) return 'Undefined';

//populate array q with quotients using a[k-2] and a[k-1] as dividends and
//divisors respectively till we hit a quotient that gives the remainder 0. Once
//we reach that step the last value of q was our GCD. And then we substitute
//for sn and tn at each iteration using the statement above. When we reach
//the index of of the GCD in our iteration that's the index in s and t arrays
//which holds the value for s and t respectively.

for(; j lte iter; j=j+1)
{
q[j-1]=Int(r[j-2]/r[j-1]);
r[j]=r[j-2] mod r[j-1];
s[j]=s[j-2]-q[j-1]*s[j-1];
t[j]=t[j-2]-q[j-1]*t[j-1];

//once we reach a non-zero remainder we know we have our values.
if(r[j] eq 0)
{
gcd=r[j-1];
c1=t[j-1];
c2=s[j-1];
break;
}
}

//Now we make c1 > 0 if it was negative
pos_c1=c1; pos_c2=c2;
if(pos_c1 lte 0)
{
while(pos_c1 lte 0)
{
pos_c1=pos_c1+(r[2]/gcd);
pos_c2=pos_c2-(r[1]/gcd);
}
}

if (ShowWork EQ True) {
//Write the final answer. The code from hereon simply displays all oour //calculated results.
WriteOutput("a = " &r[1]&", b = " &r[2]&", GCD = g = " &gcd&", s = " &c1&", t = " &c2);
WriteOutput("<br>");
WriteOutput("Thus expressing g in the form of sa + tb = gcd(a,b),<blockquote>");
WriteOutput("("&c1&") * ("&r[1]&") + ("&c2&") * ("&r[2]&") = "&gcd);
WriteOutput("</blockquote>");
if(pos_c1 lte 0)
{
WriteOutput("<br>Solution with s > 0<br><blockquote>s = "&pos_c1&", t = "&pos_c2&"</blockquote>");}
WriteOutput("</blockquote>");
//exit the function
return'';
}
else {
return gcd;
}
}
``````

### Search CFLib.org

QueryDeleteRows
November 04, 2017

May 11, 2016