Engineering/Mathematics/Foundations of number theory
Divisibility, Ideals and Unique Factorization
Every modular algorithm, every public-key scheme and every finite-field construction rests on four facts about the integers: you can divide with remainder, ideals are principal, greatest common divisors are linear combinations, and factorization into primes is unique.
- Foundation layer
- Number theory
- Proof-based
- ≈18 min read
- Prerequisite for 20+ pages
01
Executive summary
Elementary number theory is often taught as a collection of tricks about integers. It is more useful, and far more portable to algorithms, when it is taught as the study of a single algebraic object: the ring ℤ and its ideals. Divisibility becomes containment of ideals, the greatest common divisor becomes an ideal generator, and Bézout's identity becomes a statement that a certain ideal is principal.
That reframing is what makes the material transfer. The same argument that gives unique factorization of integers gives unique factorization of polynomials over a field; the same extended Euclidean algorithm that inverts an integer modulo n inverts a polynomial modulo an irreducible, which is how finite fields are built in practice.
Structural view
Divisibility, gcd and lcm are properties of the ideals aℤ, not of decimal representations of numbers.
Algorithmic view
gcd is cheap; factorization is not. The gap between these two costs is the economic basis of RSA.
Transfer view
Every result here has a mirror image in F[X], the polynomials over a field, with degree replacing absolute value.
02
Definitions and notation
Fix the vocabulary once; it is used unchanged across the whole library.
Divisibility
For a, b ∈ ℤ we write a ∣ b (“a divides b”) when b = ac for some integer c. Then a is a divisor of b and b is a multiple of a. Note that every integer divides 0, and only ±1 divides 1.
Prime and composite
An integer p > 1 is prime if its only positive divisors are 1 and p; otherwise it is composite. The number 1 is a unit and is deliberately neither — treating it as prime would destroy the uniqueness of factorization.
| Arithmetic statement | Ideal-theoretic statement | Why it matters |
|---|---|---|
| a ∣ b | bℤ ⊆ aℤ | Divisibility is reverse containment: bigger ideal, smaller divisor. |
| d = gcd(a,b) | aℤ + bℤ = dℤ | The gcd is the generator of the sum of two ideals. |
| m = lcm(a,b) | aℤ ∩ bℤ = mℤ | The lcm is the generator of the intersection. |
| gcd(a,b) = 1 | aℤ + bℤ = ℤ | Coprimality is the statement that 1 is a combination of a and b. |
| p prime | pℤ maximal | ℤp is a field precisely when p is prime. |
This table is the bridge between elementary arithmetic and the ring theory used later in the library.
03
Division with remainder
Everything computational begins with a statement that looks trivial and is not.
Division with remainder
Existence follows from the well-ordering of the non-negative integers applied to the set {a − bq : q ∈ ℤ, a − bq ≥ 0}; uniqueness follows because two candidate remainders differ by a multiple of b that is smaller than b in absolute value.
Sign conventions matter in code
The mathematical convention above always yields 0 ≤ r < b. Many programming languages implement truncated division instead, so -7 % 3 returns -1 in C, Java, Go and Rust, but 2 in Python. Modular code written against the mathematical convention must normalise remainders explicitly, or it will fail on negative operands in ways that are silent and intermittent.
Division with remainder is what makes ℤ a Euclidean domain: there is a size measure (absolute value) that strictly decreases under remaindering. The polynomial ring F[X] over a field has the same property with degree as the size measure, which is exactly why the same algorithms run there.
Contents04
Ideals and the greatest common divisor
The one structural result that generates all the rest.
An ideal of ℤ is a non-empty subset I closed under addition and under multiplication by arbitrary integers. The sets dℤ = {dk : k ∈ ℤ} are ideals; the content of the next theorem is that there are no others.
ℤ is a principal ideal domain
Every ideal I ⊆ ℤ equals dℤ for a unique d ≥ 0. Proof sketch: if I = {0} take d = 0; otherwise let d be the smallest positive element of I. For any a ∈ I, write a = dq + r with 0 ≤ r < d. Then r = a − dq ∈ I, and minimality of d forces r = 0.
Apply this to I = aℤ + bℤ = {as + bt : s,t ∈ ℤ}, which is visibly an ideal. Its generator is by definition gcd(a,b), and two properties fall out immediately:
- Bézout's identity. There exist integers s,t with as + bt = gcd(a,b). The extended Euclidean algorithm computes them in the same asymptotic time as the gcd itself.
- Common divisors divide the gcd. If c ∣ a and c ∣ b then c ∣ as + bt, hence c ∣ gcd(a,b). The gcd is therefore greatest in the divisibility order, not merely in magnitude — a stronger and more usable statement.
The definition you should carry
Define gcd(a,b) as the non-negative generator of aℤ + bℤ, not as “the largest common divisor.” The generator definition handles gcd(0,0) = 0 correctly, extends verbatim to polynomials, and makes Bézout's identity a triviality rather than a theorem.
05
Primes and the fundamental theorem of arithmetic
Existence of a prime factorization is a short induction: any n > 1 is either prime or splits into two smaller factors. Uniqueness is where the real content lies, and it depends on one lemma.
Euclid's lemma
If p is prime and p ∣ ab, then p ∣ a or p ∣ b. Proof: if p ∤ a then gcd(p,a) = 1, so ps + at = 1 for some s,t. Multiplying by b gives b = psb + abt, and p divides both terms on the right.
Fundamental theorem of arithmetic
Every integer n > 0 factors into primes, and the multiset of prime factors is unique. Uniqueness follows from Euclid's lemma by induction on n.
The valuation calculus
Writing νp(n) for the exponent of p in n converts multiplicative questions into additive ones:
| Question | Exponent form | Consequence |
|---|---|---|
| a ∣ b | νp(a) ≤ νp(b) for all p | Divisibility is a componentwise order on exponent vectors. |
| gcd(a,b) | min(νp(a), νp(b)) | Correct, but computationally useless — it needs the factorizations. |
| lcm(a,b) | max(νp(a), νp(b)) | Gives gcd(a,b) · lcm(a,b) = |ab| from min + max = sum. |
| n is a perfect square | all νp(n) even | The parity of exponent vectors is the entire idea behind the quadratic sieve. |
| a and b coprime, ab a square | disjoint supports, all even | Standard step in descent arguments and in Pythagorean parametrisation. |
06
What unique factorization buys you
Irrationality proofs
If √n were rational, some prime would carry an odd exponent on one side of an equation and an even exponent on the other. The argument is uniform, not special to √2.
Rational root test
A rational root r/t in lowest terms of an integer polynomial has t dividing the leading coefficient and r dividing the constant term.
Canonical fractions
Every rational has a unique representation a/b with b > 0 and gcd(a,b) = 1 — the basis of exact rational arithmetic and of rational reconstruction.
Multiplicative functions
Any function determined by its values on prime powers is determined everywhere: this is what makes φ, μ and σ tractable.
Smoothness
A number is y-smooth when every νp(n) > 0 has p ≤ y. Sieve-based factoring is built entirely on counting smooth numbers.
Structure of ℤn
The Chinese remainder theorem decomposes ℤn along the prime-power factorization of n, reducing most modular questions to prime powers.
Infinitude of primes, with a bound
Suppose p1, …, pk were all the primes. Then N = p1⋯pk + 1 is greater than 1 and is divisible by no pi, contradicting the existence half of unique factorization. The argument also yields a crude bound: the k-th prime is at most 22k. Sharper density results are treated separately.
07
The computational fault line
Which of these operations are cheap, and which are believed to be hard.
The whole of applied number theory lives in the gap between two problems that sound similar and are not.
Do not compute gcds by factoring
The identity gcd(a,b) = ∏ pmin(νp(a),νp(b)) is true and it is a trap. Evaluating it requires factoring both inputs, which is exponentially harder than the Euclidean algorithm that answers the same question directly. Unique factorization is a proof device here, not an algorithm.
The same asymmetry, expressed positively, is the reason RSA can exist: generating two large primes and multiplying them is cheap, while recovering them from the product is not.
Contents08
Common mistakes
| Mistake | Why it is wrong | Correct practice |
|---|---|---|
| Treating 1 as prime | Uniqueness of factorization fails immediately — you could append any number of 1s. | Units are excluded from the prime list by definition. |
| gcd(0,0) undefined or set to 1 | The ideal 0ℤ + 0ℤ is {0}, whose generator is 0. | Define gcd(0,0) = 0; library code should return 0 and not raise. |
| Assuming a ∣ bc ⇒ a ∣ b or a ∣ c | Euclid's lemma requires a prime; 6 ∣ 4·3 but divides neither. | Use gcd(a,b) = 1 ⇒ (a ∣ bc ⇒ a ∣ c) in the general case. |
| Cancelling freely in congruences | 2·3 ≡ 2·0 (mod 6) does not give 3 ≡ 0. | Cancel only by elements coprime to the modulus. |
Language % assumed non-negative | Truncated division returns negative remainders for negative operands. | Normalise once at the boundary of the modular layer. |
| Assuming unique factorization is automatic | It fails in rings such as ℤ[√−5], where 6 has two genuinely different factorizations. | Cite the property explicitly when generalising to other rings. |
09
Quick reference
| Fact | Statement |
|---|---|
| Division | a = bq + r, 0 ≤ r < b, q,r unique |
| Bézout | ∃ s,t : as + bt = gcd(a,b) |
| Coprime test | gcd(a,b) = 1 ⟺ ∃ s,t : as + bt = 1 |
| gcd–lcm | gcd(a,b)·lcm(a,b) = |ab| |
| Euclid's lemma | p prime, p ∣ ab ⇒ p ∣ a or p ∣ b |
| FTA | n = ∏ pνp(n), exponents unique |
| Divisor count | τ(n) = ∏ (νp(n) + 1) |
| Divisor sum | σ(n) = ∏ (pνp(n)+1 − 1)/(p − 1) |
| Trial division bound | n composite ⇒ it has a prime factor ≤ √n |
Why is uniqueness of factorization harder to prove than existence?
Is the gcd defined for negative numbers?
Does any of this change for polynomials?
How large can the gcd computation get in practice?
11
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 1 (basic properties of the integers). Author's electronic edition available at shoup.net/ntb.
- G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford, 2008 — classical treatment of divisibility and the fundamental theorem.
- D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., Addison-Wesley, 1997 — §4.5 on gcd computation and its complexity.
- K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990 — unique factorization in general rings and where it fails.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: divisibility-ideals-unique-factorizationReview cycle: annual