Prime Numbers

As mentioned in the property of divisibility, any integer $n$ has two distinct positive divisors: 1 and itself, and also two distinct negative divisors: -1 and $-n$. The prime numbers are defined as the follows.

Definition:

An integer $p$ is prime, if $p\ne 0,p\ne \pm 1$ and it has no divisors other than $\pm 1$ and $\pm p$.

A number which is not prime, and not $0$ nor $\pm 1$ is commonly referred as a composite number.

This name suggests that composite numbers are composed of prime numbers, and we should view prime numbers as the building blocks of all integers. This is in fact a non-formal way to state the fundamental theorem of arithmetic. Before we state this theorem, we will establish some properties of prime numbers.

Properties of Prime Numbers

In our definition of prime numbers, we allow $p$ to be negative. This sounds strange at first, but it generalize better when we deal with abstract rings and ideals. The price is, we need to be careful when stating properties of prime numbers. We start with the easiest properties, the proof of which are left as exercises.

1. $p$ is prime if and only if $-p$ is prime.
2. If $p$ and $q$ are both prime, and $p\mid q$, then $p=\pm q$.
3. If $p$ is prime, and $p\nmid a$, then $\gcd (p,a)=1$.

The second property is already suggesting prime numbers has some kind of uniqueness and exclusiveness. The following theorem makes this kind of intuition precise.

Theorem:

Let $p$ be an integer which is not $\pm 1$ and not $0$. Then $p$ is prime if and only if $p$ has the following property:

$$\text{If }p\mid ab,\text{ then }p\mid a\text{ or }p\mid b.$$

Proof of Theorem

We have two directions to prove. First, we assume $p$ is prime, and show the property holds. We can do a proof by contradiction: if $p$ is a prime and does not have the property, then there exists $a,b$ such that $p\mid ab$, but $p\nmid a$ and $p\nmid b$. Now consider $\gcd (p,a)$, it must be $1$ due to $p$ is prime and $p\nmid a$. Recall the property of coprime numbers, we have $p\mid b$, which leads to a contradiction.

Second, we assume the property holds, and show $p$ is prime. We can do a proof by contradiction: if $p$ has the property, but is not prime, i.e. $p$ has a divisor $d$ other than $\pm 1$ and $\pm p$. Then $p=dk$ for some integer $k$, and $k\ne \pm 1$ and $k\ne \pm p$. Now $p$ cannot be a divisor for $d$ or $k$ due to $|p|>|d|$ and $|p|>|k|$, this contradicts the property. $■$

It is not hard to generalize the above theorem to the multiple product case. We state it as a corollary.

Corollary:

Let $p$ be an integer which is not $\pm 1$ and not $0$. Then $p$ is prime if and only if $p$ has the following property:

$$\text{If }p\mid a_1{a}_2\cdots a_n,\text{ then }p\mid a_i\text{ for some }i.$$