Elementary Properties of Divisibility

Prime numbers

A natural number p is called a prime number if it has exactly two distinct natural number divisors, itself and 1. The first eleven such numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. There are an infinite number of primes, however, as will be proven below. Note that the number 1 is generally not considered a prime number even though it has no divisors other than itself. The reason for this will be discussed later.

Theorem 1

Suppose ${\displaystyle a,b,d,r,\,}$ and ${\displaystyle s\,}$ are integers and ${\displaystyle d|a,d|b\,}$. Then ${\displaystyle d|(ra+sb)\,}$.

Proof:

There exists ${\displaystyle e\,}$ and ${\displaystyle f\,}$ such that ${\displaystyle a=de\,}$ and ${\displaystyle b=df\,}$. Thus

${\displaystyle ra+sb=rde+sdf=d(re+sf).\,}$

We know that ${\displaystyle re+sf\,}$ is also an integer, hence ${\displaystyle d|(ra+sb)\,}$.

Theorem 2

If ${\displaystyle a,b,c\,}$ are integers,verify the following: if ${\displaystyle a|b\,}$ and ${\displaystyle b|c\,}$, then ${\displaystyle a|c\,}$.

Proof:

Let us write b as ${\displaystyle b=ad\,}$ and c as ${\displaystyle c=be\,}$ for some integers ${\displaystyle d\,}$ and ${\displaystyle e\,}$.

It follows that

${\displaystyle c=ade=a\left(de\right)\,}$, and hence ${\displaystyle a|c\,}$.

Theorem 3

given ${\displaystyle a,b,c\,}$ are integers, verify the following: ${\displaystyle a|b\,}$ if and only if ${\displaystyle ac|bc\,}$

Proof:

${\displaystyle a|b\,}$ implies that there exists an integer d such that

${\displaystyle b=ad\,}$

So it follows that

${\displaystyle bc=\left(ac\right)d}$ and hence ${\displaystyle ac|bc\,}$.

For the reverse direction, we note that ${\displaystyle ac|bc\,}$ implies there exists an integer ${\displaystyle d\,}$ such that

${\displaystyle bc=\left(ac\right)d}$.

We know that c is non-zero, hence

${\displaystyle b=ad\,}$.

This proves the theorem.

Theorem 4

Fundamental Theorem of Arithmetic (FTA)

Every composite positive integer n is a product of prime numbers. Moreover, these products are unique up to the order of the factors.

Proof:

We prove this theorem by contradiction.

Let N be the smallest positive integer that is not a product of prime numbers. Since N has to be composite, it can be written as N = a b with a, b > 1. It is

${\displaystyle 1<a,b<N}$.

We conclude that the theorem is true for a and b because N was the smallest counterexample. Hence there are primes ${\displaystyle p_{1},p_{2},\dots ,p_{k}}$ such that

${\displaystyle a=p_{1}p_{2}\cdots p_{k}}$

and primes ${\displaystyle q_{1},q_{2},\dots ,q_{l}}$ such that

${\displaystyle b=q_{1}q_{2}\cdots q_{l}}$.

Hence

${\displaystyle N=ab=p_{1}p_{2}\cdots p_{k}q_{1}q_{2}\cdots q_{l}}$,

which is a contradiction.

Alternative Proof:

This is an inductive proof.

The statement is true for ${\displaystyle N=2}$

Suppose the statement is true for all ${\displaystyle k\leq N}$

${\displaystyle N+1}$ is either composite or prime. If ${\displaystyle N+1}$ is prime, then the statement is true for ${\displaystyle k=N+1}$

If ${\displaystyle N+1}$ is composite, then ${\displaystyle N+1}$ is divisible by some prime, ${\displaystyle p<N+1}$, so ${\displaystyle k=N+1}$ can be written as a product of ${\displaystyle p}$ and some number ${\displaystyle <N+1}$.

Hence ${\displaystyle N+1}$ can be written as a product of primes.

It follows that the statement is true for all ${\displaystyle k\leq N+1}$ and hence by induction for all ${\displaystyle \mathbb {N} }$.

Theorem 5

There are infinitely many primes.

Proof:

Suppose that there are only ${\displaystyle k\,}$ primes.

Let these primes be: ${\displaystyle p_{1},p_{2},...,p_{k}\,}$.

Let ${\displaystyle n=p_{1}p_{2}...p_{k}+1.\,}$ Then either ${\displaystyle n}$ is prime, or it is a product of primes. If is is a product of primes, it must be divisible by a prime ${\displaystyle p_{i}}$ for some ${\displaystyle i}$. However, ${\displaystyle {\frac {n}{p_{i}}}={\frac {p_{1}p_{2}...p_{k}+1}{p_{i}}}=p_{1}p_{2}...p_{i-1}p_{i+1}...p_{k}+{\frac {1}{p_{i}}}}$ which is clearly not an integer: ${\displaystyle n}$ is not divisible by ${\displaystyle p_{i}}$. Hence, ${\displaystyle n\,}$ is not a product of primes.

This is a contradiction, as by Theorem 4, all numbers can be expressed as a product of primes.

Therefore, either ${\displaystyle n\,}$ is prime or it is divisible by some prime greater than ${\displaystyle p_{k}\,}$.

We conclude that the assumption that there are only ${\displaystyle k\,}$ primes is false.

Thus there are not a finite number of primes, i.e., there are infinitely many primes.

Theorem 6

The Division Algorithm (Division with smallest non-negative remainder)

Let a and b be integers where ${\displaystyle b>0}$. Then there exist uniquely determined integers q and r such that

${\displaystyle a=bq+r}$

and ${\displaystyle 0\leq r<b}$.

Proof:

We define the set

${\displaystyle M=\{x\in \mathbb {Z} \mid x\leq {\frac {a}{b}}\}}$

which is nonempty and bounded from above. Hence it has a maximal element which we denote by q.

We set ${\displaystyle r=a-bq}$. It is ${\displaystyle r=a-bq\geq a-b{\frac {a}{b}}=a-a=0}$ and ${\displaystyle r<b}$, because otherwise

${\displaystyle b\leq r=a-bq}$.

This implies

${\displaystyle q+1\leq {\frac {a}{b}}}$

which contradicts to the maximality of q in M.

We now prove the uniqueness of q and r:

Let ${\displaystyle q'}$ and ${\displaystyle r'}$ be two integers which satisfy ${\displaystyle a=bq'+r'}$ and ${\displaystyle 0\leq r'<b}$. It is

${\displaystyle |b(q-q')|=|r'-r|<b}$

and thus ${\displaystyle |q-q'|<1}$ which implies ${\displaystyle q=q'}$. This also shows ${\displaystyle r=r'}$ and we are done.

Index