Greatest Common Factor Calculator

What is Greatest Common Factor Calculator?

A Greatest Common Factor (GCF) Calculator (also known as a greatest common divisor — gcd — calculator) is a tool that determines the largest positive integer that divides two or more integers without leaving a remainder. It is fundamental in number theory and practical tasks such as simplifying fractions, solving Diophantine equations, and computing least common multiples. The calculator can use a variety of methods — the Euclidean algorithm, prime factorization, or Bézout coefficients — and typically returns both the numerical result and the intermediate steps so users can learn the process.

\[ \gcd(a,b)=\max\{d\in\mathbb{Z}^+ : d\mid a \ \text{and}\ d\mid b\}. \]

About the Greatest Common Factor Calculator

This calculator automates classical algorithms. For prime factorization it factors each number and takes the product of common prime powers:

\[ a=\prod p_i^{\alpha_i},\qquad b=\prod p_i^{\beta_i} \quad\Rightarrow\quad \gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}. \]

The Euclidean algorithm is preferred for large integers because it is efficient and requires only division with remainder. It uses the recurrence:

\[ \gcd(a,b)=\gcd(b,\,a\bmod b), \]

repeated until the remainder is zero. The last nonzero remainder is the gcd. The calculator can also compute Bézout coefficients \(x,y\) such that

\[ ax+by=\gcd(a,b), \]

which are useful for solving linear Diophantine equations and finding modular inverses.

How to Use this Greatest Common Factor Calculator

Enter two or more integers into the input fields (positive or negative — the tool uses absolute values).
Choose the method (Euclidean algorithm, prime factorization, or show Bézout coefficients).
Click Calculate — the tool displays step-by-step operations, remainders (for Euclid), prime factorizations, and the final gcd.
Optionally request Bézout coefficients to solve \(ax+by=\gcd(a,b)\) or verify fraction simplification.

Worked Example (Euclidean algorithm)

Compute \(\gcd(48,18)\):

\[ \begin{aligned} 48 &= 18\cdot 2 + 12,\\ 18 &= 12\cdot 1 + 6,\\ 12 &= 6\cdot 2 + 0. \end{aligned} \]

Since the last nonzero remainder is 6, \(\gcd(48,18)=6\).

Worked Example (Bézout)

The calculator can back-substitute to find \(x,y\) with:

\[ 6 = 18 - 12\cdot1 = 18 - (48 - 18\cdot2)\cdot1 = 18\cdot3 - 48\cdot1, \]

so one valid pair is \(x=-1\), \(y=3\) because \(48(-1)+18(3)=6\).

This Greatest Common Factor Calculator is a helpful learning and computation aid for students, programmers, and practitioners working with integers, fractions, and modular arithmetic.