# Gcd (bc)

### From LiteratePrograms

**Other implementations**:**bc**| C

This implements the Euclidean Algorithm in the bc to find the Greatest Common Divisor of two integers 'a' and 'b'.

define gcd(a,b) { auto q,r; while(b != 0) { r=a % b; a=b; b=r; } return(a); }

Alternatively, we can write this more clearly:

define gcd(numerator,denominator) { auto quotient, remainder; scale=0; while(denominator != 0) { quotient = numerator / denominator; remainder = numerator % denominator; numerator = denominator; denominator = remainder; } return(numerator); }

The scale is set to zero so that bc will perform modulo operations correctly.

Here is another implementation of the Greatest Common Divisor that shows every step used.

define gcdsteps(a,b) { auto q,r; print "a=b*q+r\n" while(b != 0) { q=a/b; r=a%b; print a,"=",b,"*",q,"+",r,"\n"; a=b; b=r; } print "0=",b,"*",q,"+",r," -- STOP\n"; return(a); }

Download code |