Prime
A positive integer greater than 1 with no positive divisors except 1 and itself.
Algebra & Number · Accessible first encounter
Number Theory:
Remainders, Primes, and Hidden Structure
Number theory investigates divisibility, primes, congruences, and integer equations. Its objects are familiar from elementary arithmetic, but its questions can be subtle enough to shape centuries of mathematics.
01 · Opening mystery
Why does repeated remainder-taking reveal the greatest common divisor?
To find gcd(414, 662), listing every divisor would be unpleasant. The Euclidean algorithm repeatedly replaces the larger number by a remainder and quickly reaches the answer.
The algorithm works because subtracting a multiple of one number from the other does not change which integers divide them both. A computational shortcut is really an invariant.
Before exploringHow can an algorithm more than two thousand years old still be central to computer security?
Make a prediction. The laboratory is designed to challenge or refine it.
02 · Interactive laboratory
Run the Euclidean algorithm and uncover a Bézout identity.
Enter two positive integers. Each row writes the larger number as a multiple of the smaller plus a remainder. The last nonzero remainder is the gcd.
Greatest common divisor2
Bézout combination2 = ···
The same remainders can be traced backward to express the gcd as an integer combination of the original numbers.
03 · The big idea
Divisibility survives the remainder step.
If a = qb + r, then r = a − qb. Any number dividing both a and b also divides r. Conversely, any number dividing b and r also divides a = qb + r. Therefore gcd(a, b) = gcd(b, r).
This idea extends naturally to congruence. We write a ≡ b (mod m) when m divides a − b—that is, when a and b leave the same remainder modulo m.
Central definition
Integers a and b are congruent modulo m when their difference is divisible by m.
a ≡ b (mod m) ⇔ m | (a − b)
Congruence
A way to treat integers as equivalent when they have the same remainder.
Bézout identity
The gcd of a and b can be written ax + by for some integers x and y.
04 · A beautiful result
Coprime numbers have modular inverses.
Suppose gcd(a, m) = 1. Bézout’s identity gives integers x and y with ax + my = 1. Reducing this equation modulo m removes the multiple my and leaves ax ≡ 1 (mod m).
Therefore x is a multiplicative inverse of a modulo m. This is the arithmetic mechanism behind solving linear congruences and an essential step in public-key cryptography.
- 1
Use the Euclidean algorithm to establish gcd(a, m) = 1.
- 2
Trace the remainders backward to obtain ax + my = 1.
- 3
Reduce modulo m: my becomes 0, so ax ≡ 1 (mod m).
- 4
Thus multiplying by x reverses multiplication by a in modular arithmetic.
05 · Why this subject matters
Modern security depends on arithmetic that is easy one way and hard in reverse.
RSA encryption uses modular exponentiation and the difficulty of factoring a large product of primes. The theory does not rely on numbers being mysterious; it relies on a carefully chosen asymmetry between efficient operations and computationally difficult inverse problems.
Number theory also connects to error-correcting codes, pseudorandomness, Diophantine equations, and the distribution of primes.
Cryptography
Builds keys and reversible operations from modular arithmetic.
Abstract Algebra
Congruence classes form groups, rings, and fields.
Coding Theory
Finite arithmetic helps detect and correct transmission errors.
06 · Friendly assessment
Check the central ideas without pressure.
The questions focus on the main insights, not obscure details. Each response receives an explanation immediately.
Where this idea leads
Continue through the mathematical atlas.
Connected field
Cryptography
Turn modular arithmetic into secure communication.
Explore →Connected fieldAbstract Algebra
Study modular systems as algebraic structures.
Explore →Connected fieldCoding Theory
Use finite fields to protect information.
Explore →Connected fieldCombinatorics
Count number-theoretic patterns and configurations.
Explore →You have now experienced
You have seen the Euclidean algorithm as an invariant-preserving proof, not merely a recipe for calculating a gcd.
This is an invitation to continue, not a compressed substitute for a full university course.