Here's the euclidean algorithm as a recursive function in bc:

define gcf(a,b)

{

if(a%b==0)

{return b}

{return gcd(b,a%b)}

}

1. You take the two numbers A and B (A>B).

2. Find the integer remainder when A/B and call it C.

3. If C == **0**, then B is your GCF.

4. If C > **0**, assign B's value to A, assign C's value to B, and repeat from step 2.

It usually doesn't take more than a few steps.

Last edited: Jan 23, 2005