# 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=m;
r=n;
s=0;
s=1;
t=1;
t=0;

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

// handle possible divide by zero error.
if (r 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/gcd);
pos_c2=pos_c2-(r/gcd);
}
}

if (ShowWork EQ True) {
//Write the final answer. The code from hereon simply displays all oour //calculated results.
WriteOutput("a = " &r&", b = " &r&", 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&") + ("&c2&") * ("&r&") = "&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 Raymond Camden added
QueryDeleteRows
November 04, 2017 Leigh added
May 11, 2016 Raymond Camden added
stripHTML
May 10, 2016 Kevin Cotton added
date2ExcelDate
May 05, 2016 Raymond Camden added
CapFirst
April 25, 2016

Created by Raymond Camden / Design by Justin Johnson