Division Algorithm

Theorem 1 (Division Algorithm)

Given integers a and b,with b>0,there exist unique integers q and r satisfying a = qb + r. The integers q and r are called,respectively,the quotient and remainder in the division of a by b.
Example,
a = 8 , b = 3, q = 2, r = 2
8 = 2 x 3 + 2 ( a = qb + r)

Definition.

An integer b is said to be divisible by an integer , in symbols a|b, if there exist some integer c such that b = ac.
3|6 indicate 3 divide 6 , which exist c=2.

Theorem 2
For integers a , b , c , the following hold :-
1. a|0 , 1|a , a|a

2. a|1 iff

3. if a|b and c|d , then ac|bd

4. if a|b and b|c , then a|c

5. a|b and b|a iff

6. if a|b and b|c , then a|(bx+cy) for some integers x and y.

Proof
3. since a|b and c|d,then exist e and f such that b = ac and d = cf. Because bd = ae•cf = ac•ef , thus ac|bd.

4. Since a|b and b|c,then exist e and f such that b = ae and c = bf. Because c = bf =aef,thus a|c.

5. Since a|b and a|c,then exist e and f such that b = ae and c = af. Hence,
bx + cy = aex + afy = a(ex+fy). Let (ex+fy) = w. Hence, bx + cy = aw. Thus,a|(bx+cy) for some x and y.

Definition

Let a anb b be given integers,with at least one of them different from zero. The greatest common divisor (gcd) of a and b,denoted by gcd(a,b) is positive integer d satisfying the following;
a) d|a and d|b (d is a common divisor)
b) if c|a and c|b,then c|d.