Greatest Common Divisor (GCD)

Problem Description

Given two non-negative integers \(a\) and \(b\), compute their greatest common divisor—i.e., the largest integer \(d\) such that \(d\) divides both \(a\) and \(b\). In notation, this is written as \(d \mid a\) and \(d \mid b\), which means that there exist integers \(k\) and \(\ell\) such that \(a = dk\) and \(b = d\ell\).

Given two non-negative integers \(a\) and \(b\), compute their greatest common divisor—i.e., the largest integer \(d\) such that \(d \mid a\) and \(d \mid b\).

Input

Two non-negative integers \(a\) and \(b\), (optionally, with \(a \geq b\)).

Output

An integer \(d\), the greatest common divisor of \(a\) and \(b\).

Motivation/Applications

The GCD is fundamental in number theory and appears in many areas such as simplifying fractions, modular arithmetic, cryptography (e.g., RSA), and algorithmic problems like computing least common multiples (LCMs) and Diophantine equations.

Examples

Example 1

Input: \(a = 48, \; b = 18\)

Output: \(6\)

Explanation: \(6\) divides both 48 and 18, and no larger number does.

Example 2

Input: \(a = 101, \; b = 103\)

Output: \(1\)

Explanation: 101 and 103 are relatively prime.

Common Algorithms/Techniques

Brute-force divisor check (inefficient)
Euclidean Algorithm (efficient and classic)
Extended Euclidean Algorithm: An extension of the Euclidean Algorithm that not only computes \(\gcd(a, b)\), but also finds integers \(x\) and \(y\) such that \[ ax + by = \gcd(a, b). \] This is useful for solving linear Diophantine equations and is essential for computing modular inverses, which are important in cryptography and modular arithmetic.