Divisibility and Prime Numbers

Divisibility, the greatest common divisor, and the prime numbers form the bedrock of number theory: every integer is built multiplicatively from primes, and the way it is built governs nearly every later result.

Definition

An integer a divides b if b equals a times some integer; a prime is an integer greater than one whose only positive divisors are one and itself. Divisibility and prime numbers concern the multiplicative decomposition of integers and the irreducible building blocks of that decomposition.

Scope

This topic treats the divisibility relation on the integers, the division algorithm, greatest common divisors and least common multiples computed via the Euclidean algorithm, Bezout's identity, Euclid's lemma, the fundamental theorem of arithmetic, and the elementary theory of primes — their infinitude, distribution heuristics, and primality.

Core questions

• How does the Euclidean algorithm compute greatest common divisors and yield Bezout's identity?
• Why does Euclid's lemma force factorization into primes to be unique?
• How can one prove there are infinitely many primes, and what do such proofs reveal?
• How are primes distributed among the integers, and how is primality decided in practice?

Key theories

Division algorithm and the Euclidean algorithm

Any integer divided by a positive integer leaves a unique quotient and remainder; iterating this gives the greatest common divisor and, via back-substitution, integers expressing it as a linear combination (Bezout's identity).

Fundamental theorem of arithmetic

Every integer above one is a product of primes that is unique up to ordering; Euclid's lemma (a prime dividing a product divides a factor) is the key step.

Infinitude of primes

Euclid's classical argument shows no finite list of primes is complete; Euler's product formula for the zeta function gives an analytic proof and quantifies prime density through the divergence of the sum of reciprocals of primes.

Clinical relevance

Fast factorization and primality testing are foundational to cryptography: RSA security rests on the difficulty of factoring large products of two primes, while efficient primality tests (such as Miller-Rabin) make key generation practical.

History

Euclid's Elements (c. 300 BCE) already contained the Euclidean algorithm, Euclid's lemma, and the proof that primes are infinite. The sieve of Eratosthenes provided the first systematic method for listing primes, and eighteenth- and nineteenth-century work by Euler, Legendre, and Gauss recast prime distribution as a quantitative problem.

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

Is one a prime number?

No. One is excluded by definition so that prime factorization is unique; if one counted as prime, every number would have infinitely many factorizations.

What is Bezout's identity used for?

It states that the greatest common divisor of two integers is an integer linear combination of them, which is the basis for computing modular inverses and solving linear Diophantine equations.