Famous Theorems of Mathematics/Number Theory/Basic Results (Divisibility)

Definition of divisibilityEdit

An integer b is divisible by an integer a, not zero, if there exists an integer x such that b = ax and we write  a|b . In case b is not divisible by a, we write  a \nmid b. For example  3|6 and  4 \nmid 6.

If  a | b and 0 < a < b then a is called a proper divisor of b. The notation  a^k || b is used to indicate that  a^k | b but  a^{k+1} \nmid b. For example  3||6.

Basic propertiesEdit

  1.  a|b implies  a|bc for any integer c.
  2.  a|b and  b|c imply  a|c.
  3.  a|b and  a|c imply  a|(bx + cy) for any integers x and y.
  4.  a|b and  b|a imply  a=\pm b.
  5.  a|b, a > 0, b > 0, imply a \le b.
  6. If  m \ne 0,  a|b implies and is implied by  ma|mb.

Proof:

  1. Clearly if  a | b then \exists x such that b = ax. Then bc = a(xc) = ay and so  a | bc.
  2.  a | b and  b | c imply that m,n exist such that b = am and c = bn. Then clearly c = bn = (am)n = ap and so  a | c.
  3.  a | b and  a | c imply existence of m,n such that b = am and c = an so that bx + cy = amx + any = az and so  a | bx + cy.
  4.  a | b and  b | a imply that m,n exist such that b = am and a = bn. Then a = bn = amn and so mn = 1. The only choice for m and n is to be simultaneously 1 or -1. In either case we have the result.
  5. b = ax for some x > 0 as otherwise a and b would have opposite signs. So b = (a + a + ...) x times  \ge a.
  6.  a | b implies b = ax for some x which imples mb = amx i.e.  ma | mb. Conversely  ma | mb implies mb = max from which b = ax and so  a | b follows.

Remarks:

  • Properties 2 and 3 can be extended by the principle of mathematical induction to any finite set. That is,  a_1 | a_2,  a_2 | a_3,  a_3 | a_4 \cdots a_{k-1} | a_k implies  a_1 | a_k; and  a | b_1,  a | b_2 \cdots a | b_n implies that  a | \sum_{j=1}^n b_jx _j for any integers x_j.
  • Property 4 uses the fact that the only units in the set of integers are 1 and -1. (A unit in a ring is an element which possesses a multiplicative inverse.)

The division algorithmEdit

Specifically, the division algorithm states that given two integers a and d, with d ≠ 0

There exist unique integers q and r such that a = qd + r and 0 ≤ r < | d |, where | d | denotes the absolute value of d.

Note: The integer

  • q is called the quotient
  • r is called the remainder
  • d is called the divisor
  • a is called the dividend

Proof: The proof consists of two parts — first, the proof of the existence of q and r, and secondly, the proof of the uniqueness of q and r.

Let us first consider existence.

Consider the set

S = \left\{a - nd : n \in \mathbb{Z}\right\}

We claim that S contains at least one nonnegative integer. There are two cases to consider.

  • If d < 0, then −d > 0, and by the Archimedean property, there is a nonnegative integer n such that (−d)n ≥ −a, i.e. adn ≥ 0.
  • If d > 0, then again by the Archimedean property, there is a nonnegative integer n such that dn ≥ −a, i.e. ad(−n) = a + dn ≥ 0.

In either case, we have shown that S contains a nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. If we now let q = (ar)/d, then q and r are integers and a = qd + r.

It only remains to show that 0 ≤ r < |d|. The first inequality holds because of the choice of r as a nonnegative integer. To show the last (strict) inequality, suppose that r ≥ |d|. Since d ≠ 0, r > 0, and again d > 0 or d < 0.

  • If d > 0, then rd implies a-qdd. This implies that a-qd-d ≥0, further implying that a-(q+1)d ≥ 0. Therefore, a-(q+1)d is in S and, since a-(q+1)d=r-d with d>0 we know a-(q+1)d<r, contradicting the assumption that r was the least nonnegative element of S.
  • If d<0 then r ≥ -d implying that a-qd ≥ -d. This implies that a-qd+d ≥0, further implying that a-(q-1)d ≥ 0. Therefore, a-(q-1)d is in S and, since a-(q-1)d=r+d with d<0 we know a-(q-1)d<r, contradicting the assumption that r was the least nonnegative element of S.

In either case, we have shown that r > 0 was not really the least nonnegative integer in S, after all. This is a contradiction, and so we must have r < |d|. This completes the proof of the existence of q and r.

Now let us consider uniqueness.

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |d| such that a = dq + r and a = dq' + r' . Without loss of generality we may assume that qq' .

Subtracting the two equations yields: d(q' - q) = (r - r' ).

If d > 0 then r'r and r < dd+r' , and so (r-r' ) < d. Similarly, if d < 0 then rr' and r' < -d ≤ -d+r, and so -(r- r' ) < -d. Combining these yields |r- r' | < |d|.

The original equation implies that |d| divides |r- r' |; therefore either |d| ≤ |r- 'r' | (if |r- r' | > 0 so that |d| is also > 0 and property 5 of Basic Properties above holds), or |r- r' |=0. Because we just established that |r-r' | < |d|, we may conclude that the first possibility cannot hold. Thus, r=r' .

Substituting this into the original two equations quickly yields dq = dq' and, since we assumed d is not 0, it must be the case that q = q' proving uniqueness.

Remarks:

  • The name division algorithm is something of a misnomer, as it is a theorem, not an algorithm, i.e. a well-defined procedure for achieving a specific task.
  • There is nothing particularly special about the set of remainders {0, 1, ..., |d| − 1}. We could use any set of |d| integers, such that every integer is congruent to one of the integers in the set. This particular set of remainders is very convenient, but it is not the only choice.
Last modified on 24 July 2009, at 15:30