CONTENTS ' Euclid's Division Lemma ' The Fundamental Theorem of Arithmetic ' Revisiting Irrational Numbers ' Revisiting Rational Numbers and Their Decimal Expansions ' Summary
3
Euclid's Division Lemma ' An algorithm is a series of well defined steps which gives a procedure for solving a type of problem. ' A lemma is a proven statement used for proving another statement. THEORM 1 (Euclid's Division Lemma) : Given positive integers a and b, there exist unique integers q and r satisfying WHEREOsr
4
What exactly does the theorem mean? 'Euclid's division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
5
EXAMPLE HCF of the integers 455 and 42. We start with the larger integer, that is, 455. Then we use Euclid's lemma to get 455 = 42 x 10 + 35 Now consider the divisor 42 and the remainder 35, and apply the division lemma to get 42=35x1+7 Now consider the divisor 35 and the remainder 7, and apply the division lemma to get
7
NOTE: 'The flow of the divisor, dividend and remainder! 'The second last remainder, before the remainder becomes zero is the HCF required!
8
To findinq properties of numbers Show that every positive even integer is of the form 24, and that every positive odd integer is of the form 2q + 1, where q is some integer. Solution : Let a be any positive integer and b = 2. Then, by Euclid's algorithm, a = 2q + r, for some integer q >=0, and r = 0 or r = 1, because r < 2. so, a = 2q or 2q + 1. If a is of the form 2q, then a is an even integer. Also, a positive integer can be either even or odd. Therefore, any positive odd integer is of the form 24 + 1.
Discussion
Copyright Infringement: All the contents displayed here are being uploaded by our members. If an user uploaded your copyrighted material to LearnPick without your permission, please submit a Takedown Request for removal.
Need a Tutor or Coaching Class?
Post an enquiry and get instant responses from qualified and experienced tutors.
If you have your own Study Notes which you think can benefit others, please upload on LearnPick. For each approved study note you will get 25 Credit Points and 25 Activity Score which will increase your profile visibility.