Log in
MODULE 07

GCD Calculator & Chinese Remainder Theorem Solver

Prime Checker

Prime Factorization

GCD (Euclidean Algorithm)

GCD as a Linear Combination

Finds x, y such that ax + by = gcd(a,b) (Bézout's identity), via the Extended Euclidean Algorithm. Works for zero, negative, and equal inputs.

LCM

Extended Euclidean Algorithm

Modular Inverse

Congruence Check

Chinese Remainder Theorem

Solve a system x ≡ ai (mod mi). Add as many congruences as you need. Supports both pairwise coprime moduli and non-coprime moduli (when a solution exists).

Euler's Totient φ(n)

Fermat's Little Theorem

Verifies ap-1 ≡ 1 (mod p) for prime p.

Euler's Theorem

Verifies aφ(n) ≡ 1 (mod n) for gcd(a,n)=1.

What is GCD & CRT?

Number theory studies integer properties — divisibility, primes, and modular arithmetic. This calculator focuses on GCD (via the Euclidean algorithm) and the Chinese Remainder Theorem, both core to cryptography.

How Does This Calculator Work?

For GCD, enter two integers and see the full Euclidean algorithm division chain. For the Chinese Remainder Theorem, enter your system of congruences (remainders and moduli) and see the solution built step by step.

Common Formulas & Rules

  • GCD(a,b): the largest integer dividing both a and b, computed efficiently by repeated division (the Euclidean algorithm).
  • Bézout's identity: for any a, b, there exist integers x, y such that ax + by = GCD(a,b) — a "linear combination" that the extended Euclidean algorithm finds directly.
  • Coprime (relatively prime): two numbers whose GCD is 1.
  • Chinese Remainder Theorem (CRT): given a system of congruences with pairwise coprime moduli, there's a unique solution modulo the product of the moduli.
  • Modular arithmetic: arithmetic that "wraps around" after reaching a fixed modulus, written a ≡ b (mod n).

Worked Example

GCD(48, 18) via the Euclidean algorithm: 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0, so GCD = 6. Working backwards through those steps (the extended algorithm) also expresses 6 as a linear combination: 6 = 1×18 - 1×12 = ... eventually 6 = (-1)×48 + 3×18, confirming ax + by = GCD directly.

Study guide: Number Theory

Written for students learning this topic for the first time. Last updated October 2026.

Overview

Number theory studies the integers: divisibility, primes, greatest common divisors and congruences. It looks old-fashioned, yet it powers RSA encryption, hash tables, checksums and pseudo-random generators.

Almost everything rests on the division algorithm: for integers a and b > 0 there are unique q and r with a = bq + r and 0 ≤ r < b. The Euclidean algorithm is just that statement applied repeatedly.

Key ideas explained

Divisibility and primes

a divides b when b = ak for some integer k. A prime has exactly two positive divisors. Every integer greater than 1 factors into primes in exactly one way (the Fundamental Theorem of Arithmetic), and to test whether n is prime you only need to try divisors up to √n.

GCD, LCM and the Euclidean algorithm

gcd(a, b) = gcd(b, a mod b); stop when the remainder is 0. The number of steps grows only logarithmically. Also lcm(a, b) = ab / gcd(a, b). Bézout's identity says gcd(a, b) = ax + by for some integers x and y, and the extended Euclidean algorithm finds them.

Modular arithmetic

a ≡ b (mod m) means m divides a − b. You can add, subtract and multiply congruences freely. Division is only possible when the divisor has an inverse: a has an inverse modulo m exactly when gcd(a, m) = 1, and the extended Euclidean algorithm computes it.

CRT, Fermat and Euler

Chinese Remainder Theorem: if the moduli are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo their product. Fermat: if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Euler generalises this: if gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n), where φ(n) counts the integers from 1 to n that are coprime to n.

Worked examples

GCD, LCM and a Bézout combination

Problem. Find gcd(252, 198), lcm(252, 198), and integers x, y with 252x + 198y = gcd.

  1. 252 = 1·198 + 54
  2. 198 = 3·54 + 36
  3. 54 = 1·36 + 18
  4. 36 = 2·18 + 0, so the gcd is 18.
  5. lcm = 252·198 / 18 = 2772.
  6. Back-substitute: 18 = 54 − 36 = 54 − (198 − 3·54) = 4·54 − 198 = 4(252 − 198) − 198 = 4·252 − 5·198.
  7. Check: 1008 − 990 = 18.

Answer. gcd = 18, lcm = 2772, and 18 = 4·252 + (−5)·198.

A Chinese Remainder system

Problem. Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

  1. From the first two: 8 satisfies both (8 mod 3 = 2, 8 mod 5 = 3), so x ≡ 8 (mod 15).
  2. Write x = 8 + 15t. Modulo 7 this is 1 + t, and we need 2, so t ≡ 1.
  3. Then x = 23, unique modulo 3·5·7 = 105.

Answer. x ≡ 23 (mod 105).

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Treating 1 as prime. Excluding it is what makes prime factorization unique.
  • Cancelling a factor from both sides of a congruence when it shares a factor with the modulus: 2·3 ≡ 2·0 (mod 6), yet 3 ≢ 0 (mod 6).
  • Using Fermat's little theorem when the modulus is composite or when p divides a.
  • Mixing up gcd and lcm. The gcd never exceeds the smaller number, and gcd × lcm = ab.

Where this shows up in computer science

  • RSA: encryption is modular exponentiation, and the private exponent is a modular inverse modulo φ(n).
  • Check digits (ISBN, credit-card Luhn check) and hash-table indexing use modular arithmetic.
  • Finding when two repeating events coincide is a least-common-multiple problem.

Test yourself

Try each question before opening the answer.

Find the inverse of 7 modulo 40.

23, because 7·23 = 161 = 4·40 + 1.

Compute 3¹⁰⁰ mod 7.

By Fermat 3⁶ ≡ 1, and 100 = 6·16 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).

What is φ(36)?

36·(1 − 1/2)·(1 − 1/3) = 12.

Frequently asked questions

What is the Euclidean algorithm used for?

It efficiently finds the greatest common divisor (GCD) of two integers by repeated division, without needing to factor either number — much faster than listing all divisors, especially for large numbers.

What does it mean for two numbers to be coprime?

Two integers are coprime (relatively prime) if their GCD is 1 — they share no common factors other than 1, even if neither number is prime itself (e.g. 8 and 9 are coprime).

What is the Chinese Remainder Theorem used for?

It solves systems of simultaneous congruences with pairwise coprime moduli, guaranteeing a unique solution modulo the product of the moduli. It's used in cryptography, calendar calculations, and error-correcting codes.