Euclid's Division Lemma & Euclid's Division Algorithm
Euclid’s Division Lemma (Division Algorithm) : Given positive integers a , b; there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b. This result was first recorded in Book VII of Euclid ’s Elements. Find q and r for the following pairs of positive integers a and b, satisfying a = bq + r. (i) a = 13, b = 3 (ii) a = 80, b = 8 (iii) a = 125, b = 5 (iv) a = 132, b = 11 Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form 2q + 1, where q is some integer. Show that any positive odd integer is of the form 4q + 1 or 4q + 3, where q is some integer. Show that any positive odd integer is of the form 6q + 1, or 6q + 3, or 6q + 5, where q is some integer. Use Euclid’s division lemma to show that the square of any positive integer is either of the form 3m or 3m + 1 for some integer m. [Hint : Let x be any positive integer then it is of the form 3q, 3q + 1 or 3q + 2. Now square each of these and show that they can b...