Definition
- GCD – the greatest common divisor of two integers is the largest positive integer that divides both of them without a remainder.
- Euclidean identity –
gcd(a, b) = gcd(b, a % b), reducing the problem at each step until one value becomes zero. - Base case –
gcd(a, 0) = a, because every number divides zero and the largest divisor ofaisaitself. - Logarithmic time – the number of steps is bounded by O(log(min(a, b))), with the worst case at consecutive Fibonacci numbers.
- LCM shortcut –
lcm(a, b) = a / gcd(a, b) * b, dividing before multiplying to avoid overflow.
The National Bank of India wants to pay out two different cashback totals to Rajesh and Priya using vouchers of a single denomination that divides both totals exactly. The largest such voucher value is the GCD. Euclid's trick is like laying the smaller amount against the larger repeatedly, each time keeping only the leftover, until nothing is left over, and the last non-zero amount is the biggest voucher that fits both perfectly.
Understanding the Concepts
What is the GCD?
The greatest common divisor of two integers is the largest positive integer that divides both of them with no remainder. For example, gcd(48, 36) is 12 because 12 divides both 48 and 36, and no larger number does. The GCD is fundamental in number theory and appears in simplifying fractions, scheduling, and resource allocation.
package com.bank.core;
public class GCDCalculator {
public static int gcd(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println("gcd(48, 36) = " + gcd(48, 36)); // 12
System.out.println("gcd(56, 98) = " + gcd(56, 98)); // 14
}
}
gcd(48, 36) = 12
gcd(56, 98) = 14
Why does the Euclidean algorithm work?
The Euclidean algorithm relies on the identity that the GCD of a and b equals the GCD of b and the remainder of a divided by b. This works because any common divisor of a and b also divides their remainder, so the set of common divisors does not change when you replace the larger value with the remainder. The base case is that gcd(a, 0) is a, because every integer divides zero.
package com.bank.core;
public class EuclidTrace {
public static void main(String[] args) {
int a = 48, b = 36;
System.out.println("Trace: gcd(" + a + ", " + b + ")");
while (b != 0) {
System.out.println(" gcd(" + a + ", " + b
+ ") -> gcd(" + b + ", " + (a % b) + ")");
int temp = b;
b = a % b;
a = temp;
}
System.out.println(" gcd(" + a + ", 0) = " + a);
}
}
Trace: gcd(48, 36)
gcd(48, 36) -> gcd(36, 12)
gcd(36, 12) -> gcd(12, 0)
gcd(12, 0) = 12
How do you implement it recursively vs iteratively?
The recursive version reads like the mathematical identity: if b is zero, return a; otherwise return gcd(b, a mod b). The iterative version uses a while loop with a temporary variable. Both are correct, but the iterative version avoids stack overflow for very large inputs.
package com.bank.core;
public class GCDVariants {
// Recursive
public static int gcdRecursive(int a, int b) {
if (b == 0) return a;
return gcdRecursive(b, a % b);
}
// Iterative
public static int gcdIterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println("Recursive: " + gcdRecursive(48, 36)); // 12
System.out.println("Iterative: " + gcdIterative(48, 36)); // 12
}
}
Recursive: 12
Iterative: 12
What is the time complexity?
The number of steps is bounded by O(log(min(a, b))). The worst case happens with consecutive Fibonacci numbers, where each remainder is exactly the previous Fibonacci number. This is still very fast, far better than the brute-force approach of trying every candidate divisor downward, which is O(min(a, b)).
package com.bank.core;
public class GCDComplexity {
public static void main(String[] args) {
// Worst case: consecutive Fibonacci numbers
int a = 89, b = 55; // Fibonacci(11), Fibonacci(10)
int steps = 0;
while (b != 0) {
steps++;
int temp = b;
b = a % b;
a = temp;
}
System.out.println("GCD: " + a + ", Steps: " + steps);
// GCD: 1, Steps: 9 (logarithmic in input)
}
}
GCD: 1, Steps: 9
How do you compute the LCM from the GCD?
The least common multiple is computed as lcm(a, b) = a / gcd(a, b) * b. Always divide before multiplying to avoid overflow. The LCM tells you the smallest number that both a and b divide evenly.
package com.bank.core;
public class LCMCalculator {
public static long lcm(long a, long b) {
long g = gcd(a, b);
return a / g * b; // divide first to avoid overflow
}
public static long gcd(long a, long b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
long temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println("lcm(4, 6) = " + lcm(4, 6)); // 12
System.out.println("lcm(12, 18) = " + lcm(12, 18)); // 36
}
}
lcm(4, 6) = 12
lcm(12, 18) = 36
What are the edge cases?
Edge cases include negative numbers, zero inputs, and gcd(0, 0). The GCD is defined as non-negative, so take absolute values first. The GCD of any number and zero is that number. The GCD of zero and zero is conventionally zero.
package com.bank.core;
public class GCDEdgeCases {
public static void main(String[] args) {
System.out.println("gcd(-48, 36) = " + GCDCalculator.gcd(-48, 36)); // 12
System.out.println("gcd(0, 5) = " + GCDCalculator.gcd(0, 5)); // 5
System.out.println("gcd(5, 0) = " + GCDCalculator.gcd(5, 0)); // 5
System.out.println("gcd(0, 0) = " + GCDCalculator.gcd(0, 0)); // 0
System.out.println("gcd(1, 1) = " + GCDCalculator.gcd(1, 1)); // 1
}
}
gcd(-48, 36) = 12
gcd(0, 5) = 5
gcd(5, 0) = 5
gcd(0, 0) = 0
gcd(1, 1) = 1
What are common mistakes?
The most common mistake is not taking absolute values, causing incorrect results for negative inputs. Another mistake is not handling the case where one input is zero, leading to a division by zero in the modulus operation.
// WRONG: not handling negatives
public static int gcdWrong(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b; // negative remainder possible!
a = temp;
}
return a; // may return negative
}
// CORRECT: take absolute values first
public static int gcdCorrect(int a, int b) {
a = Math.abs(a);
b = Math.abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // always non-negative
}
How would you apply this in a banking system?
At the National Bank of India, the GCD helps find the largest voucher denomination that divides both Rajesh's and Priya's cashback totals exactly. The LCM helps determine after how many days two recurring fee charges fall on the same day.
package com.bank.service;
import java.math.BigDecimal;
public class VoucherService {
public static long largestVoucherDenomination(
long rajeshCashback, long priyaCashback) {
return gcd(rajeshCashback, priyaCashback);
}
public static long feeOverlapDays(
long feeACycleDays, long feeBCycleDays) {
long g = gcd(feeACycleDays, feeBCycleDays);
return feeACycleDays / g * feeBCycleDays;
}
private static long gcd(long a, long b) {
a = Math.abs(a); b = Math.abs(b);
while (b != 0) { long t = b; b = a % b; a = t; }
return a;
}
public static void main(String[] args) {
System.out.println("Largest voucher: "
+ largestVoucherDenomination(4800, 3600)); // 1200
System.out.println("Fee overlap every "
+ feeOverlapDays(4, 6) + " days"); // 12
}
}
Largest voucher: 1200
Fee overlap every 12 days
What should a senior engineer know?
A senior engineer should know the extended Euclidean algorithm, which also finds coefficients x and y such that ax + by = gcd(a, b). This is useful in modular arithmetic, particularly for computing modular inverses in cryptography. They should also know that Java's BigInteger.gcd() uses the Euclidean algorithm internally.
// Extended Euclidean: returns {gcd, x, y} where ax + by = gcd
public static long[] extendedGcd(long a, long b) {
if (b == 0) return new long[]{a, 1, 0};
long[] result = extendedGcd(b, a % b);
long gcd = result[0], x = result[2], y = result[1] - (a / b) * result[2];
return new long[]{gcd, x, y};
}
// Example: 48x + 36y = gcd(48,36) = 12
// Solution: x=1, y=-1 -> 48*1 + 36*(-1) = 12
Visual Overview
Euclidean Algorithm Trace: gcd(48, 36)
Step 1: gcd(48, 36)
48 = 1 * 36 + 12
──→ gcd(36, 12)
Step 2: gcd(36, 12)
36 = 3 * 12 + 0
──→ gcd(12, 0)
Step 3: gcd(12, 0) = 12 ← ANSWER
┌──────────────────────────────────┐
│ a=48, b=36 │ remainder = 12 │
│ a=36, b=12 │ remainder = 0 │
│ a=12, b=0 │ DONE → GCD = 12 │
└──────────────────────────────────┘
LCM from GCD:
lcm(4, 6) = 4 / gcd(4,6) * 6
= 4 / 2 * 6
= 2 * 6 = 12
Key Takeaway
The greatest common divisor of two integers is the largest positive integer that divides both with no remainder, and the Euclidean algorithm computes it efficiently. The key identity is that gcd(a, b) equals gcd(b, a mod b), with the base case that gcd(a, 0) is a. I usually code it iteratively with a while loop that replaces the pair until the second value becomes zero, and the first value is the answer.
The algorithm runs in O(log(min(a, b))) time, with the worst case occurring for consecutive Fibonacci numbers. This is far better than the brute-force approach of trying every candidate divisor downward. I always take absolute values first so the result is well defined for negative inputs, and I document that gcd(0, 0) returns zero.
Once I have the GCD, I get the LCM almost for free: lcm(a, b) = a / gcd * b. I always divide before multiplying to prevent overflow. A senior engineer should also know the extended Euclidean algorithm for computing modular inverses.
At the National Bank of India, I used the GCD to pick the largest voucher denomination that divides both Rajesh's and Priya's cashback totals exactly, and the LCM to calculate after how many days two recurring fee charges fall on the same day again.
Remember one sentence: gcd(a, b) = gcd(b, a mod b) until one value is zero, and the other is the GCD.
---