Part 2 - Divisibility

We start with building the theory of divisibility in the integers.

Definition 2.1:

  1. Suppose a,bZ a, b \in \mathbb{Z} , we say that b b divides a a (written ba b \mid a ) when there exists cZ c \in \mathbb{Z} such that a=bc a = bc . Then, we also say that a a is divisible by b b or b b is a divisor of a a .

  2. When a a is not divisible by b b , then we write ba b \nmid a .

  3. When b b divides a a and 1b<a 1 \leq b < a , we say b b is a proper divisor of a a .

  4. We write akb a^k \mid \mid b when akb a^k \mid b but ak+1b a^{k+1} \nmid b .

We note ba b \mid a only makes sense when b0 b \neq 0 .

Example

424 4 \mid \mid 24 because 424 4 \mid 24 and 4224 4^2 \nmid 24 (824 8 \mid 24 ).

Theorem 2.2:

  1. aa a \mid a for every aZ\0 a \in \mathbb{Z} \backslash {0} .
  2. a0 a \mid 0 for every aZ\0 a \in \mathbb{Z} \backslash {0} .
  3. If ab a \mid b and bc b \mid c , then ac a \mid c .
  4. If ab a \mid b and ba b \mid a , then a=±b a = \pm b .
  5. If ab a \mid b and ac a \mid c , then for all x,yZ x, y \in \mathbb{Z} , one has abx+cy a \mid bx + cy . (*)
  6. If ab a \mid b and a>0 a > 0 and b>0 b > 0 , then ab a \leq b .
  7. When m0 m \neq 0 , one has ab    mamb a \mid b \iff ma \mid mb .

Theorem 2.3: (The Division Algorithm)

For any a,bZ a, b \in \mathbb{Z} and a>0 a > 0 , there exist unique q,rZ q, r \in \mathbb{Z} with b=qa+r b = qa + r and 0r<a 0 \leq r < a . If further, one has a∤:b a \not | : b , then one has 0<r<a 0 < r < a .

Proof

Existence

We can prove existence of such q,r q, r by construction.

We define q q so that aq=maxqaq::aqb a q = \max_q {a q : | : a q \leq b} , and let r=baq r = b - a q .

Now, a(q+1)>b    aq+a>b    a>baq=r a(q + 1) > b \implies aq + a > b \implies a > b - a q = r . So, we have found r r such that 0r<a 0 \leq r < a .

Uniqueness

To prove uniqueness, suppose there exist q,r,q,r q, r, q', r' such that b=qa+r b = qa + r and b=qa+r b = q'a + r' with rr r \neq r' . WLOG assume r<r r < r' .

Then, we have qa+r=qa+r    (qq)a=rr qa + r = q'a + r' \implies (q - q')a = r' - r .

This means a(rr) a \mid (r' - r) . We also have 0r,r<a    0rr<a 0 \leq r, r' < a \implies 0 \leq r' - r < a .

But because divisors are smaller than the number they divide, we have rr<a r' - r < a . This is a contradiction which means our assumption that rr r \neq r' is wrong. Hence, r=r r = r' .

Definition 2.4:

  1. Suppose that aZ\0 a \in \mathbb{Z} \backslash {0} and b,cZ b, c \in \mathbb{Z} . Then we say a a is a common divisor of b b and c c when ab a \mid b and ac a \mid c .

  2. When b b and c c are not both 0, the number of common divisors of b b and c c is finite (Theorem 2.2 (vi)). So, we can define the greatest common divisor (or highest common factor) of b b and c c to be the largest common divisor. The gcd \gcd of b b and c c is written (b,c) (b, c) (or gcd(b,c) \gcd(b, c) ).

  3. When g1,,gn g_1, \ldots, g_n are integers, not all 0, write (g1,,gn) (g_1, \ldots, g_n) for the largest integer g g with the property that ggi(1in) g \mid g_i (1 \leq i \leq n) .

Example

(0,2)=2 (0, 2) = 2 , (1,3)=1 (1, 3) = 1 , (1729,182)=91 (1729, 182) = 91