# Greatest Common Divisor

### From PostgreSQL wiki

Greatest Common Divison

Works with PostgreSQL

8.4

Written in

SQL

Depends on

Nothing

Using a CTE, the calculation of greatest common divisor (gcd) is trivial.

CREATE OR REPLACE FUNCTION gcd( a BIGINT, b BIGINT) RETURNS BIGINT IMMUTABLE STRICT LANGUAGE SQL AS $$ WITH RECURSIVE t(a,b) AS ( VALUES (abs($1)::BIGINT, abs($2)::BIGINT) UNION ALL SELECT b, MOD(a,b) FROM t WHERE b > 0 ) SELECT a FROM t WHERE b = 0 $$;

Thanks to David Fetter for this query. Thanks to Pasha Golub for the faster, more correct version.