Skip to content

Prime Numbers

Prime numbers are the fundamental building blocks of arithmetic.

number-theory book chatgpt

Definition of Prime Numbers

Prime numbers are the fundamental building blocks of arithmetic.

A positive integer p>1p>1 is called prime if its only positive divisors are

1andp. 1 \quad\text{and}\quad p.

Thus a prime number cannot be factored into smaller positive integers.

For example,

2,3,5,7,11,13 2,3,5,7,11,13

are prime numbers.

The integer 22 is prime because its positive divisors are only

1and2. 1 \quad\text{and}\quad 2.

Similarly, 1313 is prime because no positive integer other than 11 and 1313 divides it.

Composite Numbers

A positive integer n>1n>1 that is not prime is called composite.

Thus nn is composite if there exist integers a,ba,b such that

1<a<n,1<b<n, 1<a<n, \qquad 1<b<n,

and

n=ab. n=ab.

For example,

12=3⋅4, 12=3\cdot4,

so 1212 is composite.

Similarly,

15=3⋅5. 15=3\cdot5.

The integers greater than 11 therefore split into two classes:

  1. prime numbers,
  2. composite numbers.

The integer 11 belongs to neither class.

Why 11 Is Not Prime

The integer 11 has exactly one positive divisor, namely itself.

Prime numbers require exactly two distinct positive divisors:

1and the number itself. 1 \quad\text{and the number itself}.

Therefore 11 is not prime.

This convention is essential for the uniqueness of prime factorization. If 11 were prime, then factorizations would become nonunique because arbitrary copies of 11 could be inserted:

6=2⋅3 6=2\cdot3

but also

6=1⋅2⋅3 6=1\cdot2\cdot3

and

6=1⋅1⋅2⋅3. 6=1\cdot1\cdot2\cdot3.

Excluding 11 from the primes avoids this ambiguity.

Small Prime Numbers

The first few prime numbers are

2,3,5,7,11,13,17,19,23,29. 2,3,5,7,11,13,17,19,23,29.

Among these, 22 is unique because it is the only even prime.

Indeed, every even integer greater than 22 is divisible by 22, and therefore composite.

Thus every prime number except 22 is odd.

However, not every odd integer is prime. For example,

9=32,15=3⋅5. 9=3^2, \qquad 15=3\cdot5.

Testing for Primality

To determine whether an integer n>1n>1 is prime, one checks whether it has divisors other than 11 and nn.

A basic observation simplifies this process.

Suppose n=abn=ab with

1<a<n,1<b<n. 1<a<n, \qquad 1<b<n.

Then at least one of aa or bb must satisfy

a≤norb≤n. a\le\sqrt n \quad\text{or}\quad b\le\sqrt n.

Indeed, if both were larger than n\sqrt n, then

ab>n, ab>n,

which is impossible.

Therefore, to test whether nn is prime, it suffices to check divisibility by integers up to

n. \sqrt n.

For example, to test whether 3737 is prime, one checks divisibility by

2,3,5. 2,3,5.

Since none divide 3737, the number is prime.

Prime Divisors

Every composite integer has a prime divisor.

For example,

84 84

is divisible by 22, and

45 45

is divisible by 33 and 55.

This fact is fundamental because it allows arbitrary integers to be reduced to primes.

A proof follows from strong induction. If nn is composite, then

n=ab n=ab

with

1<a<n. 1<a<n.

If aa is prime, then aa is a prime divisor of nn. Otherwise aa is composite and has a smaller divisor. Repeating the process eventually reaches a prime divisor.

Prime Factorization

Primes are the basic multiplicative components of integers.

For example,

60=22⋅3⋅5. 60=2^2\cdot3\cdot5.

Similarly,

84=22⋅3⋅7. 84=2^2\cdot3\cdot7.

These decompositions are called prime factorizations.

The fundamental theorem of arithmetic states that every integer greater than 11 can be written uniquely as a product of primes, up to ordering.

This theorem gives primes their central importance.

Infinitude of Primes

There are infinitely many prime numbers.

This fact was first proved by Euclid.

Suppose there were only finitely many primes:

p1,p2,…,pn. p_1,p_2,\ldots,p_n.

Consider the integer

N=p1p2⋯pn+1. N=p_1p_2\cdots p_n+1.

No prime pip_i divides NN, because division leaves remainder 11:

N≡1(modpi). N\equiv1\pmod{p_i}.

Thus either NN itself is prime or NN has a prime divisor not contained in the list. Both possibilities contradict the assumption that all primes were already listed.

Therefore infinitely many primes exist.

Distribution of Primes

Although infinitely many primes exist, they become less frequent among large integers.

For example, small intervals contain many primes:

2,3,5,7,11. 2,3,5,7,11.

But among very large integers, primes appear more sparsely.

The distribution of primes is one of the central problems of analytic number theory. The prime number theorem describes the asymptotic density of primes and shows that the number of primes up to xx is approximately

xlog⁡x. \frac{x}{\log x}.

Despite this approximation, the exact distribution of primes remains highly irregular.

Primes in Number Theory

Prime numbers occupy a position in arithmetic analogous to that of atoms in chemistry. Composite integers are built multiplicatively from primes.

Many major areas of number theory revolve around prime numbers:

  • prime factorization,
  • congruences,
  • quadratic residues,
  • analytic estimates,
  • algebraic number fields,
  • elliptic curves,
  • cryptography.

Modern cryptographic systems such as RSA depend directly on the arithmetic of large primes.

Even today, many basic questions about primes remain unsolved. Examples include the twin prime conjecture and the Riemann hypothesis.

Thus prime numbers lie at the center of both elementary and advanced number theory.