Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Division

Definition of "division", infinitude of primes, indivisibility of primes.  These are used to prove the Fundamental Theorem of Arithmetic.

Division

Division theorem: If a and b are integers, b ≠ 0, a unique integer q exists such that

a = bq + r, where
0 ≤ r < |b|.

The number, r, uniquely determined by the division of a by b is called the "least non-negative remainder" or "principal remainder" of a (mod b).  The remainder r is equal to zero if and only if a is divisible by b.

If the condition on r were, instead,

(-1/2) |b| ≤ r < (1/2) |b|,

then the remainder would be called the "least absolute remainder" of a (mod b).

Proof: Suppose there are two different numbers, q and s, such that

a = bq + r, where
0 ≤ r < |b|.

and

a = bs + t, where
0 ≤ t < |b|.

WLOG, assume s>q, so s=q+k for some positive integer, k.  Then,

a = b(q+k) + t,
a = bq + (bk+t)

since a is also given by a=bq+r, we see that r=bk+t, so t=r-bk.  bk is at least as large as b, and r is smaller than b, so r-bk is negative.  But t can't be negative, so this is a contradiction.

Prime divisor

If a natural number n, n>1, has only trivial divisors (±1 and ±n), then n is said to be prime.  All other natural numbers larger than 1 are said to be composite.

If a|b and b|c then a|c.   Proof: since a|b, there is an integer, r, such that ar=b.  Since b|c, there is an integer, s, such that bs=c.  Substituting ar in place of b, we se that ars=c, and as rs is an integer, a|c.

Every natural number n, n>1, has at least one prime divisor.  In fact, the smallest divisor larger than 1 of n is prime.  Proof: suppose b is the smallest divisor of n, but b is not prime.  Then b has a divisor other than 1 and b, which we will call a.  a|b and b|n, so a|n, contradicting the assumption that b was the smallest divisor of c.

Therefore, if the smallest divisor of n is q, then n can be rewritten in the form n = q m, where m is a natural number.

Lemma: Multiples of a that are divisible by p

Let p be a prime, and a a natural number not divisible by p.  Then only the following positive multiples of a are divisible by p:

a·p, a·2p, a·3p, ...   (sequence 1)

Assume, in particular, that a·m is the least positive multiple of a which is divisible by p.  Then it follows that the following positive multiples of a are divisible by p:

a·m, a·2m, a·3m, ...   (sequence 2)

The task of this proof will be to show that sequence 2 contains no elements that aren't also in sequence 1, and thus sequence 1 fully describes the multiples of a that are divisible by p.

Since a·p is a multiple of a which is divisible by p, a·m must be no larger than a·p, so 1 < m ≤ p.  Now let a·h be an arbitrary positive multiple of a which is divisible by p.  By the Division Theorem,

r = h - mq,

where q,r integers, and 0 ≤ r < m.  Multiplying through by a, we see

ar = ah - amq

Since ah and am, and therefore amq, are divisible by p, their difference is also divisible by p, and it follows that ar is divisible by p as well.  Since r<m, ar<am, and by assumption am is the least positive multiple of a that is divisible by p, so r must be zero.  Therefore h=mq is a multiple of m.  Since a·h was arbitrary, we see that all multiples of a that are divisible by p are also multiples of a·m.  ap is one such multiple of a which is also a multiple of p, so ap is a multiple of am, and therefore p is a multiple of m.  Since p is a prime that is divisible by m and m>1, m=p.

So we see that sequence 2 is the same as sequence 1, proving this lemma.

Theorem: If p|ab then p|a or p|b

I will restate the theorem as: if p|ab and pa then p|b, which is logically equivalent to the original statement.

By the lemma, above, ab is one of a·p, a·2p, a·3p, ...  That is, an integer, k, exists such that ab=akp.  So b=kp, proving that p|b.

Infinitude of Primes

To show there are infinitely many primes, we will show there is no upper bound to the primes.  For this purpose, since primes are integers, it is sufficient to show that for any prime, there is a larger prime.  Let P be the product of be the smallest n primes:

P = p1 p2 p3 ... pn

P is divisible by any of the first n primes, so P+1 would leave remainder 1 when divided by pi, 1 ≤ i ≤ n.  That is piP+1.  Let q be the smallest prime divisor of P+1.  Since q is none of pi, q>pn.

Related pages in this website

The theorems on this page are used to prove the Fundamental Theorem of Arithmetic.

 

 


The webmaster and author of this Math Help site is Graeme McRae.