Number Theory/Elementary Divisibility
Elementary Properties of Divisibility
Divisibility is a key concept in number theory. We say that an integer is divisible by a nonzero integer if there exists an integer such that .
For example, the integer 123456 is divisible by 643 since there exists a nonzero integer, namely 192, such that .
We denote divisibility using a vertical bar: means "a divides b". For example, we can write .
If is not divisible by , we write . For example, .
The following theorems illustrate a number of important properties of divisibility.
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.
Suppose and are integers and . Then .
There exists and such that and . Thus
We know that is also an integer, hence .
Suppose and are integers and . Then and .
Proof: Letting and in Theorem 1 yields . Similarly, letting and yields . Finally, setting s=0, yields .
If are integers,verify the following: if and , then .
Let us write b as and c as for some integers and .
It follows that
, and hence .
given are integers, verify the following: if and only if
implies that there exists an integer d such that
So it follows that
and hence .
For the reverse direction, we note that implies there exists an integer such that
We know that c is non-zero, hence
This proves the theorem.
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.
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
We conclude that the theorem is true for a and b because N was the smallest counterexample. Hence there are primes such that
and primes such that
which is a contradiction.
This is an inductive proof.
The statement is true for
Suppose the statement is true for all
is either composite or prime. If is prime, then the statement is true for
If is composite, then is divisible by some prime, , so can be written as a product of and some number .
Hence can be written as a product of primes.
It follows that the statement is true for all and hence by induction for all .
There are infinitely many primes.
Suppose that there are only primes.
Let these primes be: .
Let Then either is prime, or it is a product of primes. If is is a product of primes, it must be divisible by a prime for some . However, which is clearly not an integer: is not divisible by . Hence, 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 is prime or it is divisible by some prime greater than .
We conclude that the assumption that there are only primes is false.
Thus there are not a finite number of primes, i.e., there are infinitely many primes.
The Division Algorithm (Division with smallest non-negative remainder)
Let a and b be integers where . Then there exist uniquely determined integers q and r such that
We define the set
which is nonempty and bounded from above. Hence it has a maximal element which we denote by q.
We set . It is and , because otherwise
which contradicts to the maximality of q in M.
We now prove the uniqueness of q and r:
Let and be two integers which satisfy and . It is
and thus which implies . This also shows and we are done.