1st Course for high Diploma, Number Theory Lecture 1: Divisibility Theory in the Integers

1.1 Introduction
A short way to determine the divisibility of a given integer by a fixed divisor without performing the division can be done through examining its digits. However, there are divisibility tests for numbers to do that. In this lecture, several concepts related to the divisibility theory are discussed as follows:
1.2 The Division Algorithm
In this section, the division algorithm has been discussed as follows:

Theorem 1.2.1. (Division Algorithm). For given integers a and b, with b > 0, there exist unique integers q and r satisfying
a = qb + r, 0 ? r < b.
The integers q and r are called, respectively, the quotient and remainder in the division of a by b.

Proof. First, it requires to prove that the set
S = {a ? xb | x an integer; a ? xb ? 0}
is nonempty. For performing that, it suffices to exhibit a value of x making a ? xb nonnegative.

Because the integer b ? 1, therefore | a | b ? | a |, and so
a ? (?| a |)b = a +| a | b ? a +| a |? 0
For the choice x = -|a| , then, a -xb lies in S. This paves the way for an application of the Well-Ordering Principle which states [Every nonempty set S of nonnegative integers contains a least element; that is, there is some integer a in S such that a ?b for all b’s belonging to S], this means that the set S contains a smallest integer; suppose it r . By the definition of S, there exists an integer q satisfying
r = a – qb 0 ? r
We argue that r < b. If this were not the case, then r ? b and
a ? (q + 1)b = (a ? qb) ? b = r ? b ? 0

The implication is that the integer a - (q + 1)b has the proper form to belong to the set S. But a - (q + 1)b r - b < r , leading to a contradiction of the choice of r as the smallest member of S. Hence, r < b.

Next, it turns to the task of showing the uniqueness of q and r . Suppose that a has two representations of the desired form, say,
a = qb + r = q b + r
where 0 ? r < b,0 ?r < b. Then r - r b(q - q ) and, owing to the fact that the absolute value of a product is equal to the product of the absolute values,
| r ? r |= b | q – q |
Upon adding the two inequalities ?b < ?r ? 0 and 0 ? r < b, we obtain

?b < r ? r < b or, in equivalent terms, | r ? r | < b. Thus, b | q – q | < b, which yields
0 ? | q – q | < 1
Because | q – q | is a nonnegative integer, the only possibility is that | q – q |= 0, whence q = q ; this, in turn, gives r = r , ending the proof. ?