**Division Algorithm on abstract algebra**: Let a and b be integers, with b > 0.Then there exist unique integers q and r such that

a = bq + r where 0 ≤ r < b.

**Proof**: Suppose that the numbers q and r actually exist. Then we must show that if qˊ and rˊ are two other such numbers, then q = qˊ and r = rˊ.

Existence of q and r. Let

S = {a – bk : k ∊ Z and a – bk ≥ 0}.

If 0 ∊ S, then b divides a, and we can let q = a=b and r = 0. If 0 =2 S, we can use the Well-Ordering Principle. We must first show that S is nonempty.

If a > 0, then a – b.0 ∊ S. If a < 0, then a – b(2a) = a(1–2b) 2 S. In either case S ≠ ∅. By the Well-Ordering Principle, S must have a smallest member, say r = a – bq. Therefore, a = bq + r, r ≥ 0. We now show that r < b. Suppose that r > b. Then

a – b(q + 1) = a – bq – b = r –b > 0:

In this case we would have a – b(q +1) in the set S. But then a – b(q +1) < a – bq, which would contradict the fact that r = a – bq is the smallest member of S. So r ≤ b. Since 0 ∉S, r ≠ b and so r < b.

Uniqueness of q and r. Suppose there exist integers r, rˊ, q, and qˊ such that

a = bq + r; 0 ≤ r < b and a = bqˊ + rˊ; 0 ≤ rˊ < b.

Then bq + r = bqˊ + rˊ. Assume that rˊ – r. From the last equation we have

b(q – qˊ) = rˊ – r; therefore, b must divide rˊ – r and 0 ≤ rˊ – r – rˊ < b. This is possible only if rˊ – r = 0. Hence, r = rˊ and q = q ˊ. (Proved)

**Theorem** : Let a and b be nonzero integers. Then there exist integers r and s such that

gcd(a; b) = ar + bs.

Furthermore, the greatest common divisor of a and b is unique.

**Proof**: Let S = {am + bn : m; n ∊ Z and am + bn > 0}.

Clearly, the set S is nonempty; hence, by the Well-Ordering Principle S must have a smallest member, say d = ar + bs. We claim that d = gcd(a; b). Write a = dq + rˊ where 0 ≤ rˊ < d . If rˊ > 0, then

rˊ = a – dq

= a – (ar + bs)q

= a – arq – bsq

= a(1 –rq) + b(–sq);

which is in S. But this would contradict the fact that d is the smallest member of S. Hence, rˊ = 0 and d divides a. A similar argument shows that d divides b. Therefore, d is a common divisor of a and b.

Suppose that d0 is another common divisor of a and b, and we want toshow that dˊ j d. If we let a = dˊh and b = dˊk, then d = ar + bs = dˊhr + dˊks = dˊ(hr + ks).

So dˊ must divide d. Hence, d must be the unique greatest common divisor of a and b.