Euclid’s division algorithm says that any positive integer a can be divided by another positive integer b in such a way that it leaves a remainder r that is smaller than b.
The fundamental Theorem of Arithmetic says that every composite number can be expressed as a product of primes in a unique way. Theorem 1.1 (Euclid's Division Lemma or Euclid division Algorithm)
Given positive integers a and b, there exist unique integers q and r satisfying a=bq+r, 0≤ r < b
Explanation:
Euclid’s Division Lemma is a redistribution of long division process where a is divident, b is divisor, q is quotient and r is remainder.
Consider positive integer pair (a,b) of (50,7). Based on above theorem, these can be represented as follows:
Exercise:Solve the following using Euclid Division Algorithm
