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

< Famous Theorems of Mathematics | Number Theory## 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 . In case b is not divisible by a, we write . For example and .

If and 0 < a < b then a is called a proper divisor of b. The notation is used to indicate that but . For example .

## Basic propertiesEdit

- implies for any integer c.
- and imply .
- and imply for any integers x and y.
- and imply .
- , a > 0, b > 0, imply .
- If , implies and is implied by .

*Proof*:

- Clearly if then x such that b = ax. Then bc = a(xc) = ay and so .
- and imply that m,n exist such that b = am and c = bn. Then clearly c = bn = (am)n = ap and so .
- and imply existence of m,n such that b = am and c = an so that bx + cy = amx + any = az and so .
- and 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.
- b = ax for some x > 0 as otherwise a and b would have opposite signs. So b = (a + a + ...) x times a.
- implies b = ax for some x which imples mb = amx i.e. . Conversely implies mb = max from which b = ax and so follows.

*Remarks*:

- Properties 2 and 3 can be extended by the principle of mathematical induction to any finite set. That is, , , implies ; and , implies that for any integers .
- 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

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.*a*−*dn*≥ 0. - If
*d*> 0, then again by the Archimedean property, there is a nonnegative integer*n*such that*dn*≥ −*a*, i.e.*a*−*d*(−*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* = (*a* − *r*)/*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*r*≥*d*implies*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*.

- 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 *q* ≤ *q'* .

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

If *d* > 0 then *r'* ≤ *r* and *r* < *d* ≤ *d*+*r'* , and so (*r*-*r'* ) < *d*. Similarly, if *d* < 0 then *r* ≤ *r'* 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.