Euclid's Division Lemma

Theorem: 

Given positive numbers a and b, there exist unique integers q and r satisfying a=bq + r, provided  o <=r<o.






Applications:
  .  Show that every positive integer is of the form 2q    when       even and 2q+1 when odd.

Solution:  Let a be any positive number and b=2.
0<=r<b. Therefore, possible values of r are 0 and 1.
So for any integer q,  a= 2q or 2q+1 (According to Euclid’s division lemma)
When a is equal to 2q it is even and when a= 2q+1 it is odd. (Thus proved!)

2.  Show that every positive odd integer is of the form of 6q+1, 6q+3 or 6q+5.

Solution: Let a be any positive number and b=6.
0<=r<b. Therefore, possible values of r are 0, 1,2,3,4 and 5.(According to Euclid’s division lemma)
So for any integer q, a= 6q or 6q+1 or 6q+2 or 6q+3 or 6q+4 or 6q+5.
When a is equal to 6q+1 or 6q+3 or 6q+5. it is odd. (Thus proved!)

3. Show that square of any positive integer is of the form 3x or 3x+1.

Solution:  Let a be any positive number and b=3.
0<=r<b. Therefore, possible values of r are 0, 1 and 2.
So for any integer q, a= 3q or 3q+1 or 3q+2.(According to Euclid’s division lemma)
a^2= (3q)^2= 9q^2= 3(3q^2)= 3x (for some integer x= 3q^2)
a^2= (3q+1)^2= 9q^2 +1+6q= 3(3q^2 + 2q)+1= 3x (for some integer x= 3q^2 +2q)
a^2= (3q+2)^2= 9q^2 +4+12q= 3(3q^2 + 4q +1)+1= 3x (for some integer x= 3q^2 +4q =1)
Therefore a^2 = 3x or 3x+1 . (Thus proved!)


Euclid's division lemma can be used to prove many more cases similar to the above one in a very simple way by aasuming an integer a = bq+r given the above mentioned condition.

Sample question:
Show that the cube of any positive integer is of the form 9m, 9m+1 or 9m+8.

(In case of any problem, please communicate. Comment or mail (dhritijain1999@gmail.com))


Comments

Post a Comment

What others are reading?

Group 14-16: Non metals ( Periodic Table #6)

Non-metals are the elements in groups 14-16 of the periodic table. Non-metals are not able to conduct electricity or heat very well . Non-metallic elements are very brittle , and not malleable (i.e.cannot be rolled into wires or pounded into sheets). The non-metals exist in two of the three states of matter at room temperature: gases (such as oxygen) and solids (such as carbon). The non-metals have no metallic luster, and do not reflect light . They have oxidation numbers of ±4, -3, and -2. The Non-Metal elements are: Hydrogen Carbon Nitrogen Oxygen Phosphorus Sulfur Selenium  Although five times more elements are metals than nonmetals, two of the nonmetals —hydrogen and helium—make up over 99 per cent of the observable Universe,  and one—oxygen—makes up close to half of the Earth's crust, oceans and atmosphere.   Living organisms are also composed almost entirely of nonmetals,  and nonmetals form many more compounds than metals CREDIT: wikiped...
Read more

Hachiko: A Dog's Tale

Image
Movie Facts Directed by: Lasse Hallstrom Based on: A dog Hachiko's loyalty Emotions prevailing: Pathetic, painful.   Music by: Jan A. P. Kaczmarek Released date: June 13, 2014 Japanese theatrical release poster Cast Hachi is portrayed by three dogs, Chico, Layla, and Forrest Richard Gere as Professor Parker Wilson Joan Allen as Cate Wilson, his wife Sarah Roemer as Andy Wilson, his daughter Cary-Hiroyuki Tagawa as Ken Fujiyoshi Jason Alexander as Carl Boilins Erick Avari as Jasjeet, an Indian vendor Davenia McFadden as Mary Anne Kevin DeCoste as Ronnie Tora Hallström as Heather Robbie Sublett as Michael Robert Capron as a pupil Frank Aronson as a Butcher Screenshot: Hachiko with his master                   Plot    Credit: (Wikipedia) Students are giving oral presentations about personal heroes. Ronnie's subject is his ...
Read more

Structure of atoms #2 : Electronic Configuration

Image
The arrangement of electrons in the various shells/orbits/energy levels of an atom of the element is known as electronic configuration. Bohr-Bury scheme Electrons revolve around the nucleus in different energy levels or shells and each shell is associated with definite energy. The energy of the K shell is the least while those of L, M, N and O shells increases progressively. We also know that any system that has least energy is the most stable. 1 s t  energy level is K shell 2 n d  energy level is L shell 3 r d  energy level is M shell 4 t h  energy level is N shell and so on. Electronic configuration of an element Bohr and Bury Scheme - Important Rules 1. Maximum number of electrons that can be accommodated in a shell is given by 2n 2  where n=shell number For 1 s t  energy level, n = 1 Maximum number of electrons in 1 s t  energy level = 2n 2 2 x (1) 2 = 2 For 2 n d  energy level n=2 Maximum number of...
Read more