From Wikibooks, the open-content textbooks collection

Current revision (unreviewed)

[edit] Elementary Properties of Divisibility

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

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

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

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

[edit] 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.

[edit] Theorem 1

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

Proof:

There exists $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) \,$ .

[edit] Corollary

Suppose $a,b,d\,$ and $r \,$ are integers and $d|a,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 \,$ .

[edit] Theorem 2

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

Proof:

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

It follows that

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

[edit] Theorem 3

If $a,b,c \,$ are integers and $c \neq 0$ , then $a|b \,$ if and only if $ac|bc \,$

Proof:

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

$b=ad \,$

So it follows that

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

For the revese direction, we note that $ac|bc \,$ implies there exists an integer $d \,$ such that

$bc=\left(ac\right)d$ .

We know that c is non-zero, hence

$b=ad \,$ .

This proves the theorem.

[edit] Theorem 4

Fundamental Theorem of Arithmetic(FTA)

Every positive integer n is a product of prime numbers.

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

$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 $p_1,p_2,\dots ,p_k$ such that

$a=p_1p_2\cdots p_k$

and primes $q_1,q_2,\dots,q_l$ such that

$b=q_1q_2\cdots q_l$ .

Hence

$N = ab = p_1p_2\cdots p_kq_1q_2\cdots q_l$ ,

which is a contradiction.

Alternative Proof:

This is an inductive proof.

The statement is true for $N = 2$

Suppose the statement is true for all $k \le 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 as a product of $p$ and some number $< N + 1$ .

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

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

[edit] 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_1p_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_1p_2...p_k+1}{p_i} = p_1p_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.