Division Algorithm

Question 1

State Euclid’s division algorithm.

Answer 1

It states that given any two positive integers, a and b, unique integers r and q can be found such that:
a = bn + r, 0 ≤ r < b.
Where q is called the quotient and r the remainder.

Question 2

What is the gcd of two integers a and b?

Answer 2

Assume integer d divides a and b, (d|a, d|b), thus is a common divisor of a and b. Now suppose every other common divisor of a and b divides d, (d’|d), then d is said to be the greatest common divisor (gcd) of a and b.

Question 3

What is the linear property of gcd?

Answer 3

If d is the gcd of a and b, then,
d = ua +vb, where u and v are integers.