Think & Discuss

Can you find the HCF of 1.2? and 0.1? justify your answer.

Euclid's algorithm is useful for calculating the HCF of very large numbers,and it was one of the earliest examples of an algorithm that a computer had been programmed to carry out.

Remarks:

 1. Euclid's algorithm are so closely interlinked that people often call former as the division algorithm also.

2. Although Division Algorithm is stated for only positive integers,it can be extended for all integers a and b where b≠0. However,we shall not dicuss this aspect here.

Division algorithm has several application related to finding properties of numbers.We give some examples of these applications below:

Example1:

Show that every positive even integer is of the form 2q,and that every positive odd integer is form 2q+1,where q is some integer.

Solution:

Let a be any positive integer and b=2.Then,by division algorithm,a=2q+r,for some integer q>0,r=0 or r=1,because 0

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 2q+1.

Example2:

show that every positive odd integer is of the form 4q+1 or 4q+3,where q is some integer.

Solution:

Let a be a positive odd integer,and b=4.We apply the division algorithm for a and b=4.
We get a=4+r,for q>0,and 0

That is,a can be 4q,4q+1,4q+2,or 4q+3,where q is the quotient.However,since a is odd,a cannot be 4q=2(2q)or 4q+2=2(2q+1)(since they are both divisible by 2).

Therfore,any odd integer is of the form 4q+1 or 4q+3.




page no:5

Home