Part 2 - Divisibility
We start with building the theory of divisibility in the integers.
Definition 2.1:
Suppose a,b∈Z , we say that b divides a (written b∣a) when there exists c∈Z such that a=bc. Then, we also say that a is divisible by b or b is a divisor of a.
When a is not divisible by b, then we write b∤a.
When b divides a and 1≤b<a, we say b is a proper divisor of a.
We write ak∣∣b when ak∣b but ak+1∤b.
We note b∣a only makes sense when b=0.
Example
4∣∣24 because 4∣24 and 42∤24 (8∣24).
Theorem 2.2:
- a∣a for every a∈Z\0.
- a∣0 for every a∈Z\0.
- If a∣b and b∣c, then a∣c.
- If a∣b and b∣a, then a=±b.
- If a∣b and a∣c, then for all x,y∈Z, one has a∣bx+cy. (*)
- If a∣b and a>0 and b>0, then a≤b.
- When m=0, one has a∣b⟺ma∣mb.
Theorem 2.3: (The Division Algorithm)
For any a,b∈Z and a>0, there exist unique q,r∈Z with b=qa+r and 0≤r<a. If further, one has a∣:b, then one has 0<r<a.
Proof
Existence
We can prove existence of such q,r by construction.
We define q so that aq=maxqaq:∣:aq≤b, and let r=b−aq.
Now, a(q+1)>b⟹aq+a>b⟹a>b−aq=r. So, we have found r such that 0≤r<a.
Uniqueness
To prove uniqueness, suppose there exist q,r,q′,r′ such that b=qa+r and b=q′a+r′ with r=r′. WLOG assume r<r′.
Then, we have qa+r=q′a+r′⟹(q−q′)a=r′−r.
This means a∣(r′−r). We also have 0≤r,r′<a⟹0≤r′−r<a.
But because divisors are smaller than the number they divide, we have r′−r<a. This is a contradiction which means our assumption that r=r′ is wrong. Hence, r=r′.
Definition 2.4:
Suppose that a∈Z\0 and b,c∈Z. Then we say a is a common divisor of b and c when a∣b and a∣c.
When b and c are not both 0, the number of common divisors of b and c is finite (Theorem 2.2 (vi)). So, we can define the greatest common divisor (or highest common factor) of b and c to be the largest common divisor. The gcd of b and c is written (b,c) (or gcd(b,c)).
When g1,…,gn are integers, not all 0, write (g1,…,gn) for the largest integer g with the property that g∣gi(1≤i≤n).
Example
(0,2)=2, (1,3)=1, (1729,182)=91