GMAT GRE 1st Grade 2nd Grade 3rd Grade 4th Grade 5th Grade 6th Grade 7th grade math 8th grade math 9th grade math 10th grade math 11th grade math 12th grade math Precalculus Worksheets Chapter wise Test MCQ's Math Dictionary Graph Dictionary Multiplicative tables Math Teasers NTSE Chinese Numbers CBSE Sample Papers |
Euclids Division LemmaCovid-19 has led the world to go through a phenomenal transition . E-learning is the future today. Stay Home , Stay Safe and keep learning!!! In this section we will discuss Euclids division lemma a new way of thinking the study of geometry.Euclid was the first Greek Mathematician who initiated a new way of thinking the study of geometry. A Euclids division lemma is a proven statement which is used to prove other statements. Consider the division of positive integer by positive integer, say 58 by 9. ![]() Here, 9 is the divisor, 58 is the dividend, 6 is the quotient and 4 is the remainder. We can write the result in following form Dividend = Divisor X quotient + Remainder 58 = 9 x 6 + 4; 0 ≤ 4 ≤ 9 For each pair of positive integers a and b, we can find unique integers q and r satisfying the relation a = bq + r , 0 ≤ r ≤ b. In fact, this holds for every pair of positive integers as proved in the following lemma. Euclids division lemma : Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that a = bq + r, 0 ≤ r ≤ b. If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b. Proof : Consider the following arithmetic progression …, a – 3b, a – 2b, a – b, a, a + b, a + 2b, a + 3b, … Clearly, it is an arithmetic progression with common difference ‘b’ and it extends infinitely in both the directions. Let ‘r’ be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer ‘q’ such that, a – bq = r ⇒ a = bq + r As, r is the smallest non-negative integer satisfying the above result. Therefore, 0 ≤ r ≤ b Thus, we have a = bq1 + r1 , 0 ≤ r1 ≤ b We shall now prove that r1 = r and q1 = q We have, a = bq + r and a = bq1 + r1 ⇒ bq + r = bq1 + r1 ⇒ r1 – r = bq1 – bq ⇒ r1 – r = b(q1 – q) ⇒ b | r1 – r ⇒ r1 – r = 0 [ since 0 ≤ r ≤ b and 0 ≤ r1 ≤ b ⇒ 0 ≤ r1 - r ≤ b ] ⇒ r1 = r Now, r1 = r ⇒ -r1 = r ⇒ a – r1 = a – r ⇒ bq1 = bq ⇒ q1 = q Hence, the representation a = bq + r, 0≤ r ≤ b is unique. Examples Euclids division lemma 1) Show that n 2 - 1 is divisible by 8, if n is an odd positive integer. Solution : We know that any odd positive integer is of the form 4q + 1 or 4q + 3 for some integer q. So, we have the following cases : Case I When n = 4q + 1 In this case, we have n 2 - 1 = (4q + 1) 2 - 1 = 16q 2 + 8q + 1 – 1 = 16q 2 + 8q = 8q ( 2q + 1) ⇒ n 2 - 1 is divisible by 8 [ since 8q ( 2q + 1) is divisible by 8] Case II When n = 4q + 3 In this case, we have n 2 -1 = (4q + 3) 2 - 1 = 16q 2 + 24q + 9 – 1 = 16q 2 + 24q + 8 ⇒ n 2 - 1 = 8(2q 2 + 3 q + 1) ⇒ n 2 - 1 is divisible by 8 [ since 8(2q 2 + 3 q + 1) is divisible by 8] Hence, n 2 - 1 is divisible by 8. -------------------------------------------------------------------- 2) 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. Solution : Let ‘a’ be any positive integer and b = 2. Then, by Euclid’s division Lemma there exists integers q and r such that a = 2q + r , where 0 ≤ r < 2 Now, 0 ≤ r < 2 ⇒ 0 ≤ r ≤ 1 ⇒ r = 0 or r = 1 [ since r is and integer] ∴ a = 2q or a = 2q + 1 If a = 2q, then ‘a’ is an even integer. We know that an integer can be either even or odd. Therefore, any odd integer is of the form of 2q + 1. Euclid's Geometry • Euclid Geometry • Euclids division lemma • Euclids division Algorithm • Fundamental Theorem of Arithmetic • Finding HCF LCM of positive integers • Proving Irrationality of Numbers • Decimal expansion of Rational numbers Home Page Covid-19 has affected physical interactions between people. Don't let it affect your learning.
More To Explore
|