# Prime Numbers

## Definition of Prime Numbers

Prime numbers are the fundamental building blocks of arithmetic.

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

$$
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
$$

are prime numbers.

The integer $2$ is prime because its positive divisors are only

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

Similarly, $13$ is prime because no positive integer other than $1$ and $13$ divides it.

## Composite Numbers

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

Thus $n$ is composite if there exist integers $a,b$ such that

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

and

$$
n=ab.
$$

For example,

$$
12=3\cdot4,
$$

so $12$ is composite.

Similarly,

$$
15=3\cdot5.
$$

The integers greater than $1$ therefore split into two classes:

1. prime numbers,
2. composite numbers.

The integer $1$ belongs to neither class.

## Why $1$ Is Not Prime

The integer $1$ has exactly one positive divisor, namely itself.

Prime numbers require exactly two distinct positive divisors:

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

Therefore $1$ is not prime.

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

$$
6=2\cdot3
$$

but also

$$
6=1\cdot2\cdot3
$$

and

$$
6=1\cdot1\cdot2\cdot3.
$$

Excluding $1$ 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.
$$

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

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

Thus every prime number except $2$ is odd.

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

$$
9=3^2,
\qquad
15=3\cdot5.
$$

## Testing for Primality

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

A basic observation simplifies this process.

Suppose $n=ab$ with

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

Then at least one of $a$ or $b$ must satisfy

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

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

$$
ab>n,
$$

which is impossible.

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

$$
\sqrt n.
$$

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

$$
2,3,5.
$$

Since none divide $37$, the number is prime.

## Prime Divisors

Every composite integer has a prime divisor.

For example,

$$
84
$$

is divisible by $2$, and

$$
45
$$

is divisible by $3$ and $5$.

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

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

$$
n=ab
$$

with

$$
1<a<n.
$$

If $a$ is prime, then $a$ is a prime divisor of $n$. Otherwise $a$ 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=2^2\cdot3\cdot5.
$$

Similarly,

$$
84=2^2\cdot3\cdot7.
$$

These decompositions are called prime factorizations.

The fundamental theorem of arithmetic states that every integer greater than $1$ 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:

$$
p_1,p_2,\ldots,p_n.
$$

Consider the integer

$$
N=p_1p_2\cdots p_n+1.
$$

No prime $p_i$ divides $N$, because division leaves remainder $1$:

$$
N\equiv1\pmod{p_i}.
$$

Thus either $N$ itself is prime or $N$ 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.
$$

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 $x$ is approximately

$$
\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.