Greatest Common Divisor (GCD)

The greatest common divisor is the largest nonnegative integer dividing both inputs, using gcd(a,0)=a and the programming convention gcd(0,0)=0. It measures shared factors without enumerating them. Euclid’s algorithm repeatedly replaces the pair by the smaller remainder problem, making it useful for simplifying fractions, detecting coprimality and many number-theory reductions. We compare iterative, recursive and C++17 standard-library versions.

Prerequisites: Divisibility; recursion; functions.

Build the idea

1. 1. Derive the remainder invariant

   If a=q·b+r, every common divisor of a,b also divides r=a−q·b. Conversely, any divisor of b,r divides a=q·b+r. The two pairs have exactly the same common divisors, so replacing (a,b) by (b,r) preserves their GCD. Stop when the second value is zero because every positive divisor of a also divides zero.

   $$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$$

2. 2. Trace Euclid

   For 48,18, successive pairs are (48,18),(18,12),(12,6),(6,0), yielding 6. Each remainder is smaller than the positive divisor it follows, ensuring progress. Inputs can be exchanged automatically: if a<b, the first remainder is a and the next pair has them in descending order.

   a	b	a mod b
   48	18	12
   18	12	6
   12	6	0

3. 3. Implement the same recurrence three ways

   The iterative version updates local variables in a loop. The recursive version directly returns gcd(b,a%b), with b==0 as its base. std::gcd from <numeric> supplies the standard C++17 operation. All three use nonnegative inputs here, avoiding sign/absolute-value edge cases such as the smallest representable signed integer whose magnitude may not fit its type.

4. 4. Reduce a fraction and identify coprimality

   For b>0 and g=gcd(a,b), divide numerator and denominator by g. No larger common factor remains: otherwise its product with g would contradict maximality. Thus 48/18 simplifies to 8/3. Coprime means GCD 1, not that both numbers are prime; for example 8 and 15 are coprime. If b=0, fraction simplification is undefined even though GCD itself is still meaningful.

5. 5. Understand efficiency

   Over at most two Euclidean steps, the larger active scale shrinks by at least a constant factor, giving a logarithmic number of remainder operations. Consecutive Fibonacci numbers are slow examples in step count. This machine-integer analysis treats one remainder as constant-time; very large multiprecision integers require bit-operation analysis instead.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 1. Derive the remainder invariant If a=q·b+r, every common divisor of a,b also divides
// r=a−q·b.
#include<iostream>
#include<numeric>
long long gcdIterative(long long a,long long b){
    while(b!=0){
        long long remainder=a%b;
        a=b;
        b=remainder;
    }
    return a;
}
long long gcdRecursive(long long a,long long b){
    return b==0?a:gcdRecursive(b,a%b);
}
int main(){
    long long a,b;
    std::cin>>a>>b;
    long long g=gcdIterative(a,b);
    std::cout<<g<<' '<<gcdRecursive(a,b)<<' '<<std::gcd(a,b)<<'\n';
    if(b==0){
        std::cout<<"UNDEFINED\n";
    }
    else{
        std::cout<<a/g<<' '<<b/g<<'\n';
    }
    std::cout<<(g==1?"COPRIME":"NOT COPRIME")<<'\n';
}

Complexity analysis

O(log(max(a,b)+1)) remainder operations per GCD. Iterative/std::gcd need constant-sized working state in the usual Euclidean model; the shown recursive function uses logarithmic stack. The complete program runs three methods, so its auxiliary stack is O(log(max(a,b)+1)).

Example input and output

Read a b in 0..10^12. Print three GCD results, then reduced numerator/denominator or UNDEFINED for b=0, then coprimality status.

Input

48 18

Output

6 6 6
8 3
NOT COPRIME

The Euclidean chain ends at 6. Dividing both fraction terms by 6 gives 8/3.

Practical applications

Use GCD for fraction normalization, shared periodicity, ratios and coprimality. It underlies LCM, modular inverses and Diophantine equations. Prefer std::gcd in ordinary C++17 solutions when custom coefficient tracking is not needed.

Check your understanding

Why may a be replaced by a%b in Euclid?

Put it into practice

Test (0,0), (0,7), (7,0) and consecutive Fibonacci values.