Number Theory/Elementary Divisibility

Elementary Properties of DivisibilityEdit

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.

Prime numbersEdit

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 1Edit

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  .

Theorem 2Edit

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  .

Theorem 3Edit

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.

Theorem 4Edit

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.

Alternative Proof:

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  .

Theorem 5Edit

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.

Theorem 6Edit

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


and  .


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


This implies


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.