# PostgreSQL GCD() Function

**Summary**: in this tutorial, you will learn how to use the PostgreSQL `gcd()`

function to find the greatest common divisor of two numbers.

## Introduction to the PostgreSQL gcd() function

The greatest common divisor (GCD) is the largest positive integer that divides two numbers without leaving a remainder. In other words, GCD is the greatest number which is a common divisor of two given numbers.

For example, the GCD of 8 and 12 is 4, because 4 is the largest integer that divides both 8 and 12 without leaving a remainder.

There are multiple ways of finding the GCD including prime factorization and Euclidean algorithm.

PostgreSQL 13 or later offers a built-in `gcd()`

function that allows you to find the GCD of two numbers.

Here’s the syntax of the `gcd()`

function:

In this syntax, you specify two numbers that you want to find their greatest common divisor. Both a and b are the types of integer, bigint, and numeric.

The `gcd()`

function returns an integer that is the GCD of the two input numbers.

If both numbers a and b are zero, the `gcd()`

function returns zero. If a and/or b are null, the `gcd()`

function returns null.

PostgreSQL uses the Euclidean algorithm under the hood:

- Step 1. Given two integers a and b, a >= b, calculate the remainder r when a is divided by b.
- Step 2. Replace a with b and b with r.
- Step 3. Repeat steps 1 and 2 until b becomes zero.

The GCD is the last non-zero remainder.

## PostgreSQL gcd() function examples

Let’s take some examples of using the `gcd()`

function.

### 1) Basic PostgreSQL gcd() function example

The following statement uses the `gcd()`

function to find the greatest common divisor of two numbers 8 and 12:

Output:

### 2) Using the gcd() function to find the greatest common divisor of three numbers

To find the GCD of three numbers, you apply the `gcd()`

function twice:

- The first one calculates the GCD of the first two numbers.
- The second one returns the GCD of the result of the first one and the third number.

The following example uses the `gcd()`

function to find the GCD of three numbers 30, 45, and 60:

Output:

In this example:

- First,
`gcd(30, 45)`

finds the GCD of 30 and 45, which is 15. - Then,
`gcd(15, 60)`

returns the GCD of the result (15) and 60, which is 15.

### 3) Using the gcd() function to find the greatest common divisor of multiple numbers

First, create a table called `numbers`

that have two columns `id`

and `value`

:

Second, insert some rows into the `numbers`

table:

Output:

Third, use a recursive query to find the GCD of all the numbers in the `value`

column:

How it works.

Initialization: define the `gcd_calculation`

CTE that initializes the first number in the `value`

column of the `numbers`

table:

It returns 30.

Recursive part: takes the current `gcd_value`

and applies the `gcd()`

function to it with the next value in the list:

Final selection: selects the last GCD value which is the GCD of all values in `value`

column of the `numbers`

table:

### 4) Defining a gcd() function using PL/pgSQL

If you use the earlier versions of PostgreSQL, you will not be able to use the built-in `gcd()`

function.

However, you can create the following gcd() function using PL/pgSQL:

The following shows how to use the user-defined `gcd`

function:

Output:

## Defining an aggregate GCD function

Using a recursive query to calculate the GCD of multiple values is quite complex. To make it simple, you can define an aggregate GCD function based on the built-in `gcd()`

function as follows:

To calculate the GCD of all numbers in the value column of the numbers table, you can use the `gcd_agg()`

function as follows:

Output:

## Summary

- Use the
`gcd()`

function to calculate the GCD of two numbers. - Use a recursive CTE to find the GCD of three or more numbers.