Real numbers -Euclid’s division algorithm

So, let us state Euclid’s division algorithm clearly.
To obtain the HCF of two integers, say c and d, with c > d , follow the steps below :
Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers , q and r such that c = dq + r, 0 rStep 2 : If r = 0, d is the HCF of c and d. If r 0, apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c,d) = HCF (d,r) where the symbol HCF (c,d) denotes the HCF of c and d, etc.

Real numbers-Euclid’s Division Lemma

Theorem 1.1 (Euclid’s Division Lemma) : Given positive integers a and b, there exist unique integers q and r satisfying a = bq +r, 0£ r

This result was perhaps known for a long time , but was first recorded in Book VII of Euclid’s Elements division algorithem is based on this lemma.

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.

Let us see how the algorithm works, through an example first. Supposewe need to find the 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 = 35 x 1 +7

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get

35 = 7 x5 + 0

Notice that the remainder has become zero, and we cannot proceed any further . We claim that the HCF of 455 and 42 is the divisor at this stage i.e, 7. You can easily verify this by listing all the factors of 455 and 42. Why does this method work ? It works because of the following result.

REAL NUMBERS - introduction

1.1 Introduction

In Class IX, you began your exploration of the world of real nubers and encountered irrational numbers. We continue our discussion on real numbers in this chapter . We begin with two very important properties of positive integers in Sections 1.2 and 1.3, namely the Euclid’s division algorithm and the Fundamental Theorem of Airthemetic.

Euclid’s division algorithm , as the name suggests , has to do with divisibility of integers. Stated simply , it says any positive integer a can be divided by another positive integer b in such a way that it leaves a remainder r that is smaller than b. Many of you probably recognize this as the usual long division process. Although this result is quite easy to state and understand , it has many applications related to the divisibility properities of integers. We touch upon a few of them, and use it mainly to compute the HCF of two positive integers.

The fundamental Theorem of Airthemetic , on the other hand has to do something with multiplication of positive integers. You already know that every composite number can be expressed as a product of primes in a unique way. This important fact is the Fundamental Theorem of Airthemetic . Again, while it is a result that is easy to state and understand, it has some very deep and significant applications in the field of mathematics. We use the Fundamental Theorem of Airthemetic for two main applications. First, we use it prove the irrationality of many of the nubers you studied in Class IX, such as Ã, and Ä. Second , we apply this theorem to explore when exactly the decimal expansion of a rational number , say p/q (q¹0), is terminating and when it is non-terminating repeating. We do so by looking at the prime factorization of the denominator q of p/q. You will see that the prime factorization of q will completely reveal the nature of the decimal expansion of p/q. So let us begin our exploration.