Number Theory/Elementary Divisibility

Elementary Properties of Divisibility

Divisibility is a key concept in number theory. We say that an integer $a$ is divisible by a nonzero integer $b$ if there exists an integer $c$ such that $a=bc$.

For example, the integer 123456 is divisible by 643 since there exists a nonzero integer, namely 192, such that $123456=643\cdot 192\,$.

We denote divisibility using a vertical bar: $a|b$ means "a divides b". For example, we can write $643|123456\,$.

If $b$ is not divisible by $a$, we write $a\nmid b$. For example, $5\nmid 12$.

The following theorems illustrate a number of important properties of divisibility.

Theorem 1

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

Proof:

Let $a,b,d,r,\,$ and $s\,$ be integers and suppose $d|a$ and $d|b\,$. Then there exist integers $e\,$ and $f\,$ such that $a=de\,$ and $b=df\,$. Thus

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

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

Corollary

Suppose $a,b,d\,$ and $r\,$ are integers and $d|a$ and $d|b\,$. Then $d|(a+b),d|(a-b),\,$ and $d|ra\,$.

Proof: Letting $r=1$ and $s=1$ in Theorem 1 yields $d|(a+b)\,$. Similarly, letting $r=1$ and $s=-1$ yields $d|(a-b)\,$. Finally, setting s=0, yields $d|ra\,$.

Theorem 2

If $a,b,c\,$ are integers, and $a|b\,$ and $b|c\,$, then $a|c\,$.

Proof:

Let $a,b,$ and $c$ are integers, and suppose $a|b\,$ and $b|c\,$. Then $b=ad\,$ and $c=be\,$ for some integers $d\,$ and $e\,$.

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

Theorem 3

Let $a,b,c\,$ be integers. Then $a|b\,$ if and only if $ac|bc\,$

Proof:

Let $a,b,c\,$ be integers. Suppose $a|b\,$.

Then there exists an integer $d$ such that

$b=ad$.

So it follows that

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

For the reverse direction, we suppose $ac|bc\,$.

Then there exists an integer $d\,$ such that

$bc=\left(ac\right)d$, so $c(b-ad)=0.$

We know that c is non-zero, hence

$b-ad=0,\,$ i.e., $b=ad$. Thus, $a|b$.

Prime and composite numbers

A natural number p greater than one is 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.

A natural number greater than one that is not prime is composite. Thus, 4, 6, 8, 9, 10, 12, 14, 15 and 16 are the first few composite numbers.

Note that the number 1 is the only natural number that is neither prime nor composite.

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.

Suppose there exists a positive composite integer that is not a product of prime numbers; let N be the smallest such integer. Since N is composite, it can be written as N = a b for some integers a and b with a, b > 1.

Since N is not a product of primes, at least one of a and b is not a product of primes; without loss of generality, let's say a is not a product of primes.

Then, since a>1, a is composite, and hence a is a positive composite number that is not a product of prime numbers.

But, since a<N this contradicts our assumption that N is the smallest such number.

Hence, there does not exist a smallest such number, and therefore there do not exist composite positive integers which are not the product of prime numbers.

Proof of uniqueness is left to the reader.

Alternative Proof:

This is an inductive proof.

The statement "k is composite implies that k is a product of prime numbers" is true when $k=2$.

Let $N$ be an integer $\geq 2$.

Suppose the statement is true for all $k\leq N$.

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

If $N+1$ is composite, then $N+1$ is divisible by some prime $p<N+1$, so $k=N+1$ can be written k=pa where p is prime and a is an integer with $1<a<N+1$. Then a is either prime, or composite; if it is composite, then it is a product of prime numbers by our induction hypothesis.

Hence $N+1$ can be written as a product of primes.

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

Proof of uniqueness is left to the reader.

Theorem 5

There are infinitely many primes.

Proof:

Suppose that there are only $k\,$ primes.

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

Let $n=p_{1}p_{2}...p_{k}+1.\,$ Then either $n$ is prime, or it is a product of primes. If is is a product of primes, it must be divisible by a prime $p_{i}$ for some $i$. However, ${\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: $n$ is not divisible by $p_{i}$. Hence, $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 $n\,$ is prime or it is divisible by some prime greater than $p_{k}\,$.

We conclude that the assumption that there are only $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 $b>0$. Then there exist uniquely determined integers q and r such that

$a=bq+r$

and $0\leq r<b$.

Proof:

We define the set

$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 $r=a-bq$. It is $r=a-bq\geq a-b{\frac {a}{b}}=a-a=0$ and $r<b$, because otherwise

$b\leq r=a-bq$.

This implies

$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 $q'$ and $r'$ be two integers which satisfy $a=bq'+r'$ and $0\leq r'<b$. It is

$|b(q-q')|=|r'-r|<b$

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

Index