1. Euclid’s division lemma states that “Given
positive integers a and b, there exist whole numbers q and r satisfying a = bq
+ r, 0 ≤ r < b.”
This result was perhaps known for a long time, but was first recorded in Book VII of Euclid's Elements. Euclid's division algorithm is based on this 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.
This result was perhaps known for a long time, but was first recorded in Book VII of Euclid's Elements. Euclid's division algorithm is based on this 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.
2. Euclid’s division algorithm: Euclid’s division algorithm is based on Euclid’s division lemma. According to this algorithm, the HCF of any two positive integers a and b, with a ˃ b, is obtained as follows:
Step 1: Apply the division lemma to find q and r where a = bq + r, 0 ≤ r < b.
Step
2: If r = 0, the HCF is b and if r ≠ 0,
apply Euclid’s lemma to b and r.
Step
3: Continue the process till the
remainder is zero. At this stage, the divisor will be HCF of a and b. Also, HCF
of a and b equals HCF of b and r.
Example: Use Euclid's division algorithm to find the HCF of 210 and 350.
Solution:
Step 1: Since 350 > 210, we apply the division lemma to 350 and 210, to get
350 = 210 × 1 + 140
Step 2: Since the remainder 140 ≠ 0, we apply the division lemma to 210 and 140, to get
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 70, the HCF of 350 and 210 is 70.
Example: Use Euclid's division algorithm to find the HCF of 210 and 350.
Solution:
Step 1: Since 350 > 210, we apply the division lemma to 350 and 210, to get
350 = 210 × 1 + 140
Step 2: Since the remainder 140 ≠ 0, we apply the division lemma to 210 and 140, to get
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 70, the HCF of 350 and 210 is 70.
3. The Fundamental Theorem of Arithmetic: Every composite number can be expressed as a
product of prime numbers, and this factorization is unique, apart from the
order in which the prime factors occur.
4. If p is a prime number and p divides a2,
then p divides a, where a is a positive integer.
5. We can prove that √2, √3 and √5 are irrational
numbers.
Example: Prove that √2 is an irrational number.
Solution:
Let us assume that √2 is a rational number.
We can find integers a and b (b ≠ 0) such that √2 = a/b.
Suppose a and b have a common factor other than 1, then we can divide by the common factor, and assume that a and b are coprimes.
So, b√2 = a
Squaring on both sides, we get 2b2 = a2
Therefore, a2 is divisible by 2.
Then, a is divisible by 2.
So, we can write a = 2c for some integer c.
Substituting for a in above, we get 2b2 = 4c2 implies b2 = 2c2
This means that 2 divides b2 and also 2 divides b.
Therefore, a and b have at least 2 as a common factor.
But this contradicts the fact that a and b have no common factors other than 1.
This contradiction has arisen because of our incorrect assumption that √2 is a rational number.
So, we conclude that √2 is an irrational number.
Similarly, we can prove that √3, √5, etc. are all irrational numbers.
Note: 1. The sum and difference of a rational and an irrational number is irrational.
2. The product and quotient of a non-zero rational and irrational number is irrational.
Example: Prove that √2 is an irrational number.
Solution:
Let us assume that √2 is a rational number.
We can find integers a and b (b ≠ 0) such that √2 = a/b.
Suppose a and b have a common factor other than 1, then we can divide by the common factor, and assume that a and b are coprimes.
So, b√2 = a
Squaring on both sides, we get 2b2 = a2
Therefore, a2 is divisible by 2.
Then, a is divisible by 2.
So, we can write a = 2c for some integer c.
Substituting for a in above, we get 2b2 = 4c2 implies b2 = 2c2
This means that 2 divides b2 and also 2 divides b.
Therefore, a and b have at least 2 as a common factor.
But this contradicts the fact that a and b have no common factors other than 1.
This contradiction has arisen because of our incorrect assumption that √2 is a rational number.
So, we conclude that √2 is an irrational number.
Similarly, we can prove that √3, √5, etc. are all irrational numbers.
Note: 1. The sum and difference of a rational and an irrational number is irrational.
2. The product and quotient of a non-zero rational and irrational number is irrational.
6. If x be a rational number whose decimal
expansion terminates, then we can express x in the form of p/q, where p and q
are co-prime, and the prime factorization of q is of the form 2n5m,
where n, m are non-negative integers.
7. If x = p/q be a rational number such that the
prime factorization of q is of the form 2n5m, where n, m
are non-negative integers, then x has a decimal expansion which is a
terminating decimal.
For example,
3/20 is a terminating decimal because 20 = 22 × 51, which
is of the form 2n5m, where n, m are non-negative
integers.
8. If x = p/q be a rational number such that the
prime factorization of q is not of the form 2n5m, where
n, m are non-negative integers, then x has a decimal expansion which is a
non-terminating repeating (recurring) decimal.
For example,
24/45 is a non-terminating decimal because 45 = 32 × 51,
which is not of the form 2n5m, where n, m are
non-negative integers.