The GCD (Greatest Common Divisor), also called HCF, is the largest positive integer that divides both numbers with no remainder.
Remember
gcd(a, b) = largest d > 0 such that
a % d == 0 and b % d == 0
Example: gcd(48, 18) = 6
48 = 6 * 8
18 = 6 * 3
No larger positive integer divides both
a
b
gcd(a, b)
48
18
6
17
13
1
0
21
21
-12
18
6
Approach
How to Find GCD in C#
Four clear steps — Euclid’s remainder loop is the interview default.
Take absolute values of a and b so the result is nonnegative.
While b != 0, replace (a, b) with (b, a % b).
When b becomes 0, return a — that is the GCD.
Optionally derive LCM with |a * b| / gcd(a, b).
Method
Idea
Time
Best for
Iterative Euclid
Loop with a % b until b == 0
O(log min)
Interviews, production default
Recursive Euclid
gcd(b, a % b) until base case
O(log min)
Showing the recurrence
LCM via GCD
|a * b| / gcd(a, b)
O(log min)
Follow-up questions
Pseudocode
Pseudocode
function Gcd(a, b):
a = abs(a)
b = abs(b)
while b != 0:
temp = b
b = a mod b
a = temp
return a
function Lcm(a, b):
if a == 0 or b == 0:
return 0
return abs(a / Gcd(a, b) * b)
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Core step
(a, b) ← (b, a % b)
Stop when
b == 0; answer is a
Signs
Use Math.Abs first
gcd(0, n)
|n| for n != 0
gcd(0, 0)
Usually defined as 0
LCM link
lcm = |a * b| / gcd
Classic check
gcd(48, 18) = 6
Try it
Live Preview
Enter two integers to see the Euclidean remainder chain and the GCD.
Start with the iterative loop — it is the clearest interview answer. Then show the recursive form, and finish with LCM built from GCD.
Example 1 — Iterative Euclidean Algorithm
Loop with remainders until the second value becomes zero.
C#
using System;
class Program
{
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;
}
static void Main()
{
int number1 = 48;
int number2 = 18;
Console.WriteLine("GCD of " + number1 + " and " + number2 + " is: " + Gcd(number1, number2));
}
}
Output
GCD of 48 and 18 is: 6
How It Works
Take absolute values so negatives do not break the remainder chain.
While b != 0, store b, set b = a % b, then set a to the old b.
For (48, 18) the pairs become (18, 12), (12, 6), then (6, 0).
When b is 0, return a — here 6.
Extra space is O(1); time is logarithmic in the smaller number.
Example 2 — Recursive Euclidean Algorithm
Same remainder idea, written as a recurrence with a clear base case.
C#
using System;
class Program
{
static int Gcd(int a, int b)
{
a = Math.Abs(a);
b = Math.Abs(b);
if (b == 0)
{
return a;
}
return Gcd(b, a % b);
}
static void Main()
{
int number1 = 48;
int number2 = 18;
Console.WriteLine("GCD of " + number1 + " and " + number2 + " is: " + Gcd(number1, number2));
}
}
Same answer as the loop; stack depth is about O(log min(a, b)).
Prefer the iterative version when you must mention space carefully.
Example 3 — LCM via GCD
Use the identity lcm(a, b) = |a / gcd * b| after finding the GCD.
C#
using System;
class Program
{
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;
}
static long Lcm(int a, int b)
{
if (a == 0 || b == 0)
{
return 0;
}
int g = Gcd(a, b);
return Math.Abs((long)a / g * b);
}
static void Main()
{
int a = 48;
int b = 18;
Console.WriteLine("gcd = " + Gcd(a, b));
Console.WriteLine("lcm = " + Lcm(a, b));
}
}
Output
gcd = 6
lcm = 144
How It Works
Reuse the same iterative Gcd helper.
If either input is 0, LCM is defined as 0 here.
Divide one value by the GCD first: a / g * b reduces overflow risk.
Cast to long before multiplying for a safer product.
