What Are Prime Numbers?
Prime numbers are integers greater than 1 whose only positive
divisors are 1 and themselves.
They are the multiplicative building blocks of the integers because
every integer greater than 1 has a unique prime factorization once its
distinct prime factors are written in increasing order. Prime numbers
connect elementary arithmetic to modular arithmetic, finite fields,
cryptography, the Prime Number Theorem, and the Riemann Hypothesis.
Prime numbers are the multiplicative building blocks of the integers.
Key Takeaways
-
A prime is an integer greater than 1 with exactly two positive
divisors. -
The integer 1 is not prime because allowing it as a prime would
destroy uniqueness of prime factorization. - Every integer greater than 1 has a unique prime factorization.
- Euclid proved that infinitely many primes exist.
-
The Prime Number Theorem describes the large-scale distribution of
primes by \(\pi(x)\sim x/\ln x\). -
Prime numbers connect directly to cryptography, prime fields,
finite fields, and the Riemann zeta function.
What Is a Prime Number?
A prime number is an integer greater than 1 whose only positive
divisors are 1 and itself.
A prime number is an integer \(p\gt1\) whose only
positive divisors are \(1\) and \(p\). Equivalently, a prime number
has exactly two positive divisors.
\[
\boxed{
p\text{ is prime}
\iff
p\in\mathbb Z,\quad
p\gt1,\quad
\operatorname{Div}^{+}(p)=\{1,p\}
}.
\]
The first few primes are
\[
2,3,5,7,11,13,17,19,23,29,\ldots
\]
The integer \(2\) is the smallest prime and the only even prime.
An integer greater than 1 that is not prime is called
composite. For example,
\[
4=2^2,
\qquad
6=2\cdot3,
\qquad
9=3^2.
\]
Why Isn’t 1 Prime?
The best reason is structural, not merely “because mathematicians
defined it that way.” If \(1\) were prime, prime factorization would
no longer be unique:
\[
6
=
2\cdot3
=
1\cdot2\cdot3
=
1^2\cdot2\cdot3
=
\cdots
\]
Excluding 1 from the primes makes the Fundamental Theorem of
Arithmetic possible in its clean, unique form.
The Fundamental Theorem of Arithmetic:
Every Integer Has a Unique Prime DNA
Prime factorization is the unique multiplicative fingerprint of
an integer.
The Fundamental Theorem of Arithmetic says that every
integer \(n\gt1\) can be expressed uniquely as
\[
\boxed{
n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},
\qquad
p_1\lt p_2\lt\cdots\lt p_k,
\qquad
a_i\ge1
}.
\]
The ordering
\(p_1\lt p_2\lt\cdots\lt p_k\)
builds “unique up to order” directly into the notation.
Once the primes are arranged this way, the prime factorization is
literally unique.
| Integer | Prime Factorization |
|---|---|
| 84 | \(84=2^2\cdot3\cdot7\) |
| 100 | \(100=2^2\cdot5^2\) |
| 360 | \(360=2^3\cdot3^2\cdot5\) |
This theorem is why primes are often called the
atoms of arithmetic:
every integer greater than 1 is assembled multiplicatively from
primes.
Why There Are Infinitely Many Prime Numbers
Euclid’s proof shows that no finite list can contain all prime
numbers.
Euclid’s proof is one of the cleanest contradiction arguments in
mathematics.
-
Assume there are only finitely many primes:
\[
p_1,p_2,\ldots,p_n.
\] -
Multiply them and add 1:
\[
N=p_1p_2\cdots p_n+1.
\] -
For every listed prime \(p_i\),
\[
N\equiv1\pmod{p_i}
\qquad\Longrightarrow\qquad
p_i\nmid N.
\] - Therefore \(N\) is prime or has a prime divisor not on the list.
-
Either possibility contradicts the assumption that
\(p_1,\ldots,p_n\) were all the primes.
Important Misconception
Euclid’s proof does not claim that
\(N=p_1p_2\cdots p_n+1\) must itself be prime.
The proof only needs \(N\) to have a prime divisor outside the
original list.
For example,
\[
2\cdot3\cdot5\cdot7\cdot11\cdot13+1
=
30031
=
59\cdot509.
\]
The constructed number is composite here, but its prime divisors
\(59\) and \(509\) are new. Euclid’s argument works exactly as
intended.
How Do We Find Prime Numbers?
The Sieve of Eratosthenes finds primes systematically, and trial
division only needs prime divisors up to \(\sqrt n\).
The Sieve of Eratosthenes
The Sieve of Eratosthenes finds all primes up to a chosen bound by
repeatedly eliminating composite numbers. To find the primes up to 30:
-
List the integers from 1 through 30 and mark 1 as neither prime nor
composite. - Keep 2 and cross out its proper multiples.
- Keep 3 and cross out its remaining proper multiples.
-
Keep 5 and cross out its remaining proper multiples.
Since \(\sqrt{30}\lt6\), no larger sieving prime is needed.
The survivors are exactly
\[
2,3,5,7,11,13,17,19,23,29.
\]
Why Trial Division Stops at \(\sqrt n\)
Suppose \(n\) is composite, so \(n=ab\) with integers \(a,b\gt1\).
If both \(a\) and \(b\) were larger than \(\sqrt n\), then
\[
a\gt\sqrt n,
\quad
b\gt\sqrt n
\quad\Longrightarrow\quad
ab\gt n,
\]
which is impossible because \(ab=n\).
Therefore every composite \(n\) has a prime divisor at most
\(\sqrt n\).
Example: Is 97 Prime?
\[
\sqrt{97}\approx9.85.
\]
\[
\text{Test only }2,3,5,7.
\]
None divides 97, so
\[
\boxed{97\text{ is prime}.}
\]
Prime Numbers Have Patterns—but Not a Simple Predictive Formula
Every prime greater than 3 is congruent to \(\pm1\) modulo 6,
but satisfying that pattern does not guarantee primality.
Every integer belongs to one of six residue classes modulo 6:
\[
n\equiv0,1,2,3,4,\text{ or }5\pmod6.
\]
Residues \(0,2,4\) are even, while residue \(3\) is divisible by 3.
Therefore a prime \(p\gt3\) can only occupy residue classes 1 or 5:
\[
\boxed{
p\gt3\text{ prime}
\quad\Longrightarrow\quad
p\equiv\pm1\pmod6
}.
\]
But the converse is false:
\[
25\equiv1\pmod6,
\qquad
25=5^2,
\]
\[
35\equiv-1\pmod6,
\qquad
35=5\cdot7.
\]
So \(n\equiv\pm1\pmod6\) is a
necessary
condition for primes greater than 3, not a sufficient one.
Prime numbers have deep structure, but their local placement is not
governed by a simple repeating rule.
How Many Primes Are There Below \(x\)?
The Prime Number Theorem says
\(\pi(x)\sim x/\ln x\),
describing the large-scale distribution of prime numbers.
The prime-counting function is
\[
\boxed{
\pi(x)=\#\{p\le x:p\text{ is prime}\}
}.
\]
| \(x\) | \(\pi(x)\) | \(x/\ln x\) | \(\pi(x)/(x/\ln x)\) |
|---|---|---|---|
| 100 | 25 | \(\approx21.7\) | \(\approx1.15\) |
| 1,000 | 168 | \(\approx144.8\) | \(\approx1.16\) |
| 10,000 | 1,229 | \(\approx1085.7\) | \(\approx1.13\) |
| 100,000 | 9,592 | \(\approx8685.9\) | \(\approx1.10\) |
The Prime Number Theorem
\[
\boxed{
\pi(x)\sim\frac{x}{\ln x}
\qquad(x\to\infty)
}.
\]
Equivalently,
\[
\frac{\pi(x)}{x/\ln x}
\longrightarrow1.
\]
A useful density heuristic follows:
near a large number \(x\), the rough proportion of integers that are
prime is about
\[
\frac1{\ln x}.
\]
Prime numbers become sparser as numbers grow, yet they never
disappear. Locally they look irregular; globally they obey a precise
asymptotic law.
Prime Numbers and Cryptography
RSA-style cryptography exploits the asymmetry between multiplying
large primes and factoring a large semiprime.
Prime numbers are central to several areas of public-key cryptography.
In RSA-style cryptography, choose large distinct primes \(p\) and
\(q\) and form
\[
N=pq.
\]
Multiplying \(p\) and \(q\) is efficient. Given only a
cryptographically large \(N\), recovering the original prime factors
is believed to be computationally difficult for classical computers
when appropriate parameters are used.
Important Distinction
RSA arithmetic is performed modulo the composite number \(N=pq\).
RSA is not “arithmetic inside a prime field.” Prime fields enter
other cryptographic systems, including many constructions built
from finite fields and elliptic curves.
For a broader application-focused lesson, see
Blockchain Mathematics Explained: Cryptography, AI, and Consensus
.
Why Prime Numbers Create Fields
One of the most important bridges from elementary number theory to
abstract algebra is the fact that arithmetic modulo \(n\) becomes a
field exactly when \(n\) is prime:
\[
\boxed{
n\gt1,
\qquad
\mathbb Z/n\mathbb Z
\text{ is a field}
\iff
n\text{ is prime}
}.
\]
For prime \(p\), this field is denoted
\[
\mathbb F_p
\cong
\mathbb Z/p\mathbb Z.
\]
Example: Why Modulo 5 Works
Every nonzero residue modulo 5 has a multiplicative inverse.
For example,
\[
2\cdot3
=
6
\equiv1\pmod5.
\]
Why Modulo 6 Fails
\[
2\cdot3
=
6
\equiv0\pmod6.
\]
The nonzero classes represented by 2 and 3 multiply to zero, so
modulo 6 has zero divisors and cannot be a field.
This prime-versus-composite distinction is the doorway to finite
field theory.
Continue with
Finite Field Theory Explained: Galois Fields and Cryptography
.
Bonus Connection: Mersenne Primes and Perfect Numbers
Prime numbers also control the complete classification of
even perfect numbers.
The Euclid–Euler theorem says that an even integer is perfect exactly
when it has the form
\[
\boxed{
N
=
2^{p-1}(2^p-1)
}
\]
where \(p\) is prime and \(2^p-1\) is also prime.
A prime of the form \(2^p-1\) is called a
Mersenne prime.
For example, \(p=3\) gives
\[
2^{3-1}(2^3-1)
=
4\cdot7
=
28.
\]
The even case is completely classified.
The odd case is dramatically different:
no odd perfect number is known.
For the deeper research framework, see
Odd Perfect Numbers Explained:
Euler’s Form, Abundancy, and Modular Valuations
.
Do Prime Numbers Hide a Deeper Pattern?
Euler’s product connects the Riemann zeta function directly to
every prime number, while the Riemann Hypothesis places all
nontrivial zeros on the critical line
\(\operatorname{Re}(s)=1/2\).
The deepest part of this lesson begins with a function that initially
looks unrelated to prime numbers:
\[
\boxed{
\zeta(s)
=
\sum_{n=1}^{\infty}\frac1{n^s},
\qquad
\operatorname{Re}(s)\gt1
}.
\]
In this same half-plane, Euler discovered the product identity
\[
\boxed{
\zeta(s)
=
\prod_{p\text{ prime}}
\frac1{1-p^{-s}},
\qquad
\operatorname{Re}(s)\gt1
}.
\]
This Euler product is one of the most important identities in number
theory: a sum over all positive integers equals a product over all
primes. Unique prime factorization is the mechanism behind that
connection.
Analytic Continuation and the Riemann Hypothesis
The Dirichlet series above converges only when
\(\operatorname{Re}(s)\gt1\), but the zeta function extends
meromorphically to the complex plane, with a simple pole at \(s=1\).
The Riemann Hypothesis states:
\[
\boxed{
\zeta(s)=0
\text{ and }s\text{ is nontrivial}
\quad\Longrightarrow\quad
\operatorname{Re}(s)=\frac12
}.
\]
The hypothesis does not directly predict the next prime.
Instead, it would give extraordinarily strong control over the error
in our estimates for prime distribution.
Continue with the dedicated flagship lesson:
Riemann Hypothesis Explained:
Prime Numbers and the $1,000,000 Problem
.
Prime Numbers: The Map of Modern Number Theory
Prime numbers connect arithmetic, modular arithmetic, cryptography,
abstract algebra, finite fields, open problems, and modern
mathematical research.
Prime numbers form a natural hub connecting several major branches of
mathematics:
-
Arithmetic:
divisibility, greatest common divisors, and prime factorization. -
Modular arithmetic:
congruences, residue classes, inverses, and divisibility structure. -
Abstract algebra:
prime fields, quotient rings, units, zero divisors, and field
structure. -
Finite fields:
\(\mathbb F_p\), extension fields \(\mathbb F_{p^n}\),
coding theory, and cryptography. -
Cryptography:
factoring-based systems, finite-field systems, digital signatures,
and algebraic security. -
Analytic number theory:
\(\pi(x)\), the Prime Number Theorem, zeta functions, and prime
distribution. -
Open problems:
twin primes, Goldbach’s conjecture, prime gaps, and the
Riemann Hypothesis. -
Research:
perfect numbers, finite fields, permutation polynomials, and
algebraic number-theoretic structures.
The Big Takeaway
We understand exactly what a prime number is.
We understand how every integer factors into primes.
We know there are infinitely many primes and we understand their
average distribution remarkably well.
Yet the local placement of the primes continues to generate some of
the deepest open problems in mathematics.
Common Prime Number Mistakes
-
Calling 1 prime.
It is excluded so that prime factorization remains unique. -
Thinking every odd number is prime.
For example, \(9=3^2\) and \(15=3\cdot5\). -
Thinking Euclid’s constructed number must be prime.
It only needs a prime divisor outside the assumed list. -
Testing every smaller integer for primality.
Trial division only requires prime divisors through \(\sqrt n\). -
Believing \(n\equiv\pm1\pmod6\) guarantees primality.
The condition is necessary for primes greater than 3, not sufficient. -
Treating primes as completely random.
Their local behavior is irregular, but their global distribution
obeys the Prime Number Theorem. -
Confusing RSA with arithmetic in a prime field.
RSA works modulo the composite \(N=pq\). -
Thinking the Riemann Hypothesis predicts the next prime directly.
It concerns the global error structure in prime distribution.
Woody Mastery Check
Close the lesson before attempting these.
Retrieval is the test.
If you can explain each item without looking, you are beginning to own
the mathematics.
-
Define
a prime number exactly. -
Explain aloud
why 1 is not prime using uniqueness of factorization. -
Rewrite
the Fundamental Theorem of Arithmetic from memory. -
Explain
the contradiction in Euclid’s proof of infinitely many primes. -
Use
the Sieve of Eratosthenes to find all primes through 30. -
Justify
why trial division only needs primes through \(\sqrt n\). -
Prove
why every prime greater than 3 is congruent to
\(\pm1\pmod6\). -
Define
\(\pi(x)\)
and
state
the Prime Number Theorem. -
Explain
the difference between RSA modulo \(N=pq\) and a prime field
\(\mathbb F_p\). -
Describe
how Euler’s product links unique prime factorization to the
Riemann zeta function.
Prime Number FAQ
What is a prime number?
A prime number is an integer greater than 1 whose only positive
divisors are 1 and itself.
Why isn’t 1 prime?
If 1 were prime, prime factorization would not be unique because
arbitrarily many factors of 1 could be inserted into any
factorization.
Is 2 the only even prime?
Yes. Every even integer greater than 2 is divisible by 2 and is
therefore composite.
What is a composite number?
A composite number is an integer greater than 1 that is not prime,
so it has a positive divisor other than 1 and itself.
What is prime factorization?
Prime factorization writes an integer greater than 1 as a product of
prime powers.
What is the Fundamental Theorem of Arithmetic?
Every integer greater than 1 has a unique prime factorization once
its distinct prime factors are written in increasing order.
Are there infinitely many prime numbers?
Yes. Euclid proved that no finite list can contain every prime number.
What is Euclid’s proof of infinitely many primes?
Assume a finite list contains all primes, multiply those primes and
add 1, and observe that the resulting number is not divisible by any
prime on the list. It must therefore be prime or have a new prime
divisor.
What is the Sieve of Eratosthenes?
The Sieve of Eratosthenes finds all primes up to a bound by keeping
each new prime and eliminating its proper multiples.
How do you test whether a number is prime?
A basic method is trial division by prime numbers no larger than the
square root of the number being tested.
Why is it enough to test divisors up to the square root of n?
If \(n\) is composite, then in any factorization \(n=ab\) at least
one factor must be at most \(\sqrt n\).
Therefore a composite number has a prime divisor at most
\(\sqrt n\).
Why are primes greater than 3 congruent to plus or minus 1 modulo 6?
Modulo 6, residues 0, 2, and 4 are even and residue 3 is divisible by
3, so a prime greater than 3 can only occupy residue class 1 or 5.
Does being congruent to plus or minus 1 modulo 6 guarantee a number is prime?
No.
For example,
\(25\equiv1\pmod6\)
and
\(35\equiv-1\pmod6\),
but both numbers are composite.
What is the prime-counting function pi of x?
The function \(\pi(x)\) counts the number of primes less than or equal
to \(x\).
What does the Prime Number Theorem say?
The Prime Number Theorem says
\(\pi(x)\sim x/\ln x\),
so the ratio of the actual prime count to \(x/\ln x\) approaches 1
as \(x\) grows.
Are prime numbers random?
Prime numbers are not random objects.
Their local spacing is irregular, but their global distribution
follows precise laws such as the Prime Number Theorem.
How are prime numbers used in cryptography?
Prime numbers appear in factoring-based cryptography such as RSA and
in finite-field and elliptic-curve systems.
Different cryptographic systems use primes in different algebraic
ways.
What is a prime field?
A prime field is a finite field
\(\mathbb F_p\cong\mathbb Z/p\mathbb Z\),
where \(p\) is prime and arithmetic is performed modulo \(p\).
How does Euler’s product connect prime numbers to the zeta function?
For \(\operatorname{Re}(s)\gt1\),
Euler’s identity
\(\zeta(s)=\prod_p(1-p^{-s})^{-1}\)
rewrites the zeta function as a product over every prime, with unique
prime factorization underlying the identity.
What is the Riemann Hypothesis?
The Riemann Hypothesis conjectures that every nontrivial zero of the
Riemann zeta function has real part \(1/2\).
It is deeply connected to the error term in prime distribution.
References and Further Reading
These sources provide authoritative reference points for the prime
sequence, the Prime Number Theorem, the Riemann zeta function, and the
Riemann Hypothesis.
Need Help With Number Theory or Proof-Based Mathematics?
Prime numbers are an ideal gateway into proof writing, modular
arithmetic, finite fields, abstract algebra, and analytic number theory.
If you want structured practice and professor-led support beyond a
single lesson, continue with the Woody Calculus Number Theory resources
and Mastery Lab.
|