Email Us
Email us for a quick response...
|
Here, in this chapter we will know about two very important properties of positive integers namely
(i) The Euclid’s division algorithm and (ii) The Fundamental Theorem of Arithmetic. | ||||||||||||||||||||
| Algorithm
An algorithm is a set of instructions designed to perform a specific task. In another way, we can say, it is a step-by-step solution to a problem. This can be a simple process, such as multiplying two numbers, or a complex operation,
such as solving a problem with all operations.
Example: What is 23 divided by 4. Algorithm:
How many times does 4 go into 23?
The answer is 5 with a remainder of 3. 23 = 4 × 5 + 3 And of course, the answer is 5 with a remainder of 3.
Euclidean division, and algorithms to compute it, are fundamental for many questions concerning integers, such as the Euclidean algorithm for finding the HCF of two integers, and modular arithmetic, for which only remainders are considered. The operation consisting of computing only the remainder is called the modulo operation, and is used often in both mathematics and computer science.
Algorithms are used in many branches of science. Computers use algorithms all the time.
The word algorithm comes from the name
of the 9th century Persian mathematician
al-Khwarizmi. In fact, even the word ‘algebra’
is derived from a book, he wrote, called Hisab
al-jabr w’al-muqabala.
| ||||||||||||||||||||
| Euclid’s Division Algorithm
According to Euclid’s division algorithm, any positive integer a (the dividend) can be divided by another positive integer b (the divisor) in such a way that it leaves a quotient q and a remainder r that is smaller than b (the divisor).
a (Dividend) = b (Divisor) × q (Quotient) + r (Remainder)
A fundamental property is that the quotient and the remainder exist and are unique, under some conditions.
| ||||||||||||||||||||
| Euclid’s Division Lemma
The basis of the Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm. HCF is the largest number which exactly divides two or more positive integers.
That means, both the integers a and b are exactly divisible by the HCF of both the integers.
A lemma is a proven statement used for proving another statement.
Find the HCF of 15 and 36.
| ||||||||||||||||||||
| Theorem (Euclid’s Division Lemma)
Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Let us see how the algorithm works.
Suppose we need to find the HCF of the integers 65 and 28.
Notice that, in both the cases remainder has become zero, and we cannot proceed any further.
So, we can say that the HCF of 65 and 28 is the divisor at this stage, i.e., 1.
Here, one more thing to remember
HCF of 65 and 28 = HCF 28 and 9 = HCF of 9 and 1.
To obtain the HCF of two positive integers, say a and b, with a > b, 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 ≤ r < b.
Step 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 (a, b) = HCF (b, r) where the symbol HCF (a, b) denotes the HCF of a and b, etc.
Example: Find the HCF of 4173 and 17773 using Euclid’s algorithm.Solution:
Although Euclid’s Division Algorithm is stated for only positive integers, but it can be
extended for all integers except zero, i.e., b ≠ 0.
| ||||||||||||||||||||
| The Fundamental Theorem of Arithmetic
In your earlier classes, you have seen that any natural number can be written as a product of its prime factors.
Can any natural number be obtained by multiplying prime numbers? Let us try.
Write any prime numbers, say 2, 3, 5, 7, 11, 13, 17, 19, 23,...etc in the above blue background white box.
Now observe, we will always get a positive integer. In this way, we will get an infinite collection of
numbers, all the primes and all possible products of primes.
Now, the question is – can we produce all the composite numbers this way?
For example, let us find the prime factorization of 320
From the above factor tree, 320 = 2 × 2 × 2 × 2 × 2 × 2 × 5 = 26 × 5
Is there any other way that expresses the number 320 as the product of prime. Of course, no. We can only change the order in which the prime factors occur.
For example, the prime factorization can be written as: 320 = 26 × 5 or 5 × 26
But the set of prime factors (and the number of times each factor occurs) is unique.
That is, 320 can have only one possible prime factorization, with six factors of 2 and one factor of 5.
This leads us to a conjecture that every composite number can be
written as the product of powers of primes. This is the Fundamental Theorem of Arithmetic.
| ||||||||||||||||||||
| Theorem: Fundamental Theorem of Arithmetic
Every composite number can be expressed ( factorised) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.
The Fundamental Theorem of Arithmetic says that every composite number can be factorised as a product of primes in a
‘unique’ way, except for the order in which the primes occur.
That is, given any composite number there is one and only one way to write it as a product of primes,
as long as we are not particular about the order in which the primes occur. So, for
example,
2 × 3 × 5 × 7 × 11 = 11 × 3 × 5 × 7 × 2
or any other possible order in which these primes are written. This fact is also stated in the
following form:
The prime factorisation of a natural number is unique, except for the order
of its factors.
In general, given a composite number x, we factorise it as x = p1 p2 p3 ... pn, where p1, p2, p3..., pn are primes and written in ascending order,
p1 ≤ p2 ≤ p3 ≤. . .≤ pn.
If we combine the same primes, we will get powers of primes.
Writing the primes in ascending order makes the factorization unique.
| ||||||||||||||||||||
| Application of The Fundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic has many applications, both within mathematics and in other fields. Let us look at some examples.
Example. Consider the numbers 4n, where n is a natural number. Check whether
there is any value of n for which 4n ends with the digit zero.
Solution:
If the number 4n, for any n, were to end with the digit zero, then it would be divisible by 5. That is, the prime factorisation of 4n
would contain the prime 5. This is not possible because 4n = (2)2n; so the only prime in the factorisation of 4n is 2.
So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are no other primes in the factorisation of 4n. So, there is no natural number n for which 4n ends with the digit zero.
Example. Consider the numbers 5n, where n is a natural number. Check whether
there is any value of n for which 5n ends with the digit 2.
Solution:
If the number 5n, for any n, were to end with the digit 2, then it would be divisible by 2. That is, the prime factorisation of 5n
would contain the prime 2. This is not possible because 5n = (5)n; so the only prime in the factorisation of 5n is 5.
So, there is no natural number n for which 5n ends with the digit 2.
Example. Find the LCM and HCF of 5 and 20 by the prime factorisation method.
Solution:
We have : 4 = 22 and 20 = 2 × 2 × 5 = 22 × 51.
HCF(4, 20)= 2 and LCM(4, 20) = 2 × 2 × 5
The product of any two positive integers is equal to the product of their H. C. F. and L. C. M.
In general, any two positive integers a and b
LCM (a, b) × HCF (a, b) = a × b
LCM (a, b) = a × b/HCF (a, b) HCF (a, b) = a × b/LCM (a, b) a = LCM (a, b) × HCF (a, b)/b b = LCM (a, b) × HCF (a, b)/a | ||||||||||||||||||||
|
Example: : Find the HCF of 84 and 520 by the prime factorisation method. Hence, find their LCM. Solution:
The prime factorisation of 84 and 520 gives :
84 = 2 × 2 × 3 × 7 = 22 × 3 × 7 520 = 2 × 2 × 2 × 5 × 13 = 23 × 5 × 13 Therefore, the HCF of these two integers is 22 = 4. By using formula, LCM(84,520) = 84 × 520/HCF(84, 520) = 84 × 520/4 = 10920∴ LCM(84,520) = 10920 | ||||||||||||||||||||
| Practice Time
Find and write.
| ||||||||||||||||||||
| Irrational Numbers
A number ‘ℙ’ is called an irrational number, if it cannot be written in the form of
p/q ,
where p and q are integers and q ≠ 0. For example, 0.10110111,
√3
,
√5
,
√6
,
√7
,
√11
, π.....etc.
If m is a positive integer which is not a perfect square, then √m is an irrational number. For example,
√2, √3, √5, √6, √7...etc.
If m is a positive integer which is not a perfect cube, then ∛m is an irrational number. For example,
∛2, ∛3, ∛4, ∛5, ∛6...etc.
22 = 4 and √4 = 2
−22 = 4 and √4 = −2
Here, the symbol √, we assume that it is the positive square root of the number.
| ||||||||||||||||||||
| Irrational Numbers On The Number Line
Let us see how we can locate some of the irrational numbers on the number line.
√2 on the number line.
Consider a square ABCD, with each side 1 unit in length.
By the Pythagoras theorem.
CB2 = CD2 + BD2
CB2 = 12 + 12
CB2 = 1 + 1
CB2 = 2
CB = √2
Transfer square ABCD onto the number line making sure that the vertex C coincides with zero.
Using a compass with centre C and radius CB, draw an arc intersecting the number line at the point P.
CP = √2
∴ P corresponds to √2 on the number line.
| ||||||||||||||||||||
| √3 on the number line.
Draw a right-angled triangle ABC on the number line making sure that the vertex A and C coincides with 0 and 1, with base and altitude 1 unit in length.
By the Pythagoras theorem.
AB2 = AC2 + BC2
AB2 = 12 + 12
AB2 = 1 + 1
AB2 = 2
AB = √2
Now, draw BD ⊥ AB such that BD = 1 unit.
Join D to A.
New triangle ADB is a right angled triangle.
∴ By the Pythagoras theorem.
AD2 = AB2 + BD2
AD2 = (√2)2 + 12
AD2 = 2 + 1
AD2 = 3
AD = √3
Using a compass with centre A and radius AD, draw an arc intersecting the number line at the point P.
AP = √3
∴ P corresponds to √3 on the number line.
| ||||||||||||||||||||
| √5 on the number line.
In the same way, you can locate √n for any positive integer n, after √n − 1 has been located.
| ||||||||||||||||||||
| Theorem
Let p be a prime number. If p divides a2, then p divides a, where a is a positive integer.
Proof:
Let the prime factorisation of a be as follows :
Now, we are given that p divides a2. Therefore, from the Fundamental Theorem of Arithmetic, it follows that p is one of the prime factors of a2.
However, using the uniqueness part of the Fundamental Theorem of Arithmetic, we realise that the only
prime factors of a2 are p1 p2. . . pn.
So p is one of p1 p2. . . pn.a = p1 p2. . . pn, where p1,p2, . . ., pn are primes, not necessarily distinct. Therefore, a2 = ( p1 p2 . . . pn)( p1 p2 . . . pn) = p12p22. . . pn2. Now, since a = p1 p2. . . pn, p divides a. | ||||||||||||||||||||
|
Now, we will prove that √2 , √3 , √5 and, in general, √p is irrational, where p is a prime. One of the theorems, we use in our proof, is the Fundamental Theorem of Arithmetic.
| ||||||||||||||||||||
| Theorem
√2 is irrational.
The proof is based on a technique called ‘proof by contradiction’.
Proof:
Let us assume, to the contrary, that √2 is rational. So, we can find integers r and s (≠ 0) such that √2 = r/s .Suppose r and s have a common factor other than 1. Then, we divide by the common factor to get √2 = a/b where a and b are coprime.So, b√2 = a. Squaring on both sides and rearranging, we get 2b2 = a2. Therefore, 2 divides a2. Now, by above Theorem, it follows that 2 divides a. So, we can write a = 2c for some integer c. Substituting for a, we get 2b2 = 4c2, that is, b2= 2c2. This means that 2 divides b2, and so 2 divides b (using above Theorem with p = 2). 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 rational. So, we conclude that √2 is irrational. | ||||||||||||||||||||
|
Example. Prove that √3 is irrational.
Solution:
Let us assume, to the contrary, that √3 is rational.
That is, we can find integers a and b (≠ 0) such that √3 = 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 coprime. So, b√3 = a. Squaring on both sides, and rearranging, we get 3b2 = a2. Therefore, a2 is divisible by 3, and by above Theorem, it follows that a is also divisible by 3. So, we can write a = 3c for some integer c. Substituting for a, we get 3b2 = 9c2, that is, b2 = 3c2. This means that b2 is divisible by 3, and so b is also divisible by 3 (using above Theorem with p = 3). Therefore, a and b have at least 3 as a common factor. But this contradicts the fact that a and b are coprime. This contradiction has arisen because of our incorrect assumption that √3 is rational. So, we conclude that √3 is irrational. Example. Show that 5 – √3 is irrational.
Solution:
Let us assume, to the contrary, that 5 – √3 is rational.
That is, we can find coprime a and b (b ≠ 0) such that 5 − √3 = a/b .Therefore, 5 − a/b = √3Rearranging this equation, we get 5 √3 = 5 – a/b = 5b − a/b Since a and b are integers, we get 5 – a/b is rational, and so √3 is rational.But this contradicts the fact that √3 is irrational. This contradiction has arisen because of our incorrect assumption that 5 – √3 is rational. So, we conclude that 5 3 - is irrational. Example. Show that 3√2 is irrational
Solution:
Let us assume, to the contrary, that 3√2 is rational.
That is, we can find coprime a and b (b ≠ 0) such that 3√2 = a/b .Rearranging, we get √2 = a/3b .Since 3, a and b are integers, a/3b is rational, and so √2 is rational.But this contradicts the fact that √2 is irrational. So, we conclude that 3√2 is irrational. | ||||||||||||||||||||
| Rational Numbers and Their Decimal Expansions
As we know, rational numbers have either a terminating decimal expansion or a non-terminating repeating decimal expansion.
Here in this section, we will study exactly when the decimal expansion of
p/q
is terminating and when it is non-terminating repeating(or recurring). We do so by considering several examples.
| ||||||||||||||||||||
| Terminating Decimal Numbers
If the decimal expression of p/q have a finite number of digits after the decimal point, then the decimal so obtained is called a terminating decimal. For example,
1/2 = 0.5 = 0.5 x 10/10 = 5/101 = 5/2 x 5 = 1/2
1/4 = 0.25 = 0.25 x 100/100 = 25/102 = 52/22 x 52 = 1/4
3/2 = 1.5 = 1.5 x 10/10 = 15/101 = 2 x 5/2 x 5 = 3/2
9/8 = 1.125 = 1.125 x 1000/1000 = 1125/103 = 32 x 53/23 x 53 = 9/8
In these types of expression, the digits after decimal point ends. It is also called an exact decimal numbers. The number of digits after the decimal point of these numbers is countable.
When you express it as rational numbers, you see a common pattern that is both the numerator and the denominator are coprime the denominator has powers of 10. Further, when you do prime factorisation of the denominator, you will see that it only has powers of 2, or powers of 5 or both.
Any real number which has a decimal expansion that terminates can be expressed as a rational number whose denominator is a power of 10. Also the only prime factors of 10 are 2 and 5. So, cancelling out the common factors between the numerator and the denominator, we find that this real number is a rational number of the form ,
p/q
where the prime factorisation of q is of the form 2n5m, and n, m are some non-negative integers.
If
p/q is a rational number, then its decimal expansion will terminate if it satisfies the following conditions :
(i) The H.C.F of p and q is 1.
(ii) q can be expressed as a prime factorisation of 2 and 5 i.e q=2n5m where n, m are some non-negative integers.
| ||||||||||||||||||||
| Theorem
Let x be a rational number whose decimal expansion terminates. Then x can be expressed in the form
p/q , where p and q are coprime, and the prime factorisation of q is of the form 2n5m, where n, m are non-negative integers.
Consider the following examples:
| ||||||||||||||||||||
|
The converse of the above theorem is also true and it can be stated as follows:
Theorem
Let x =
p/q be a rational number, such that the prime factorisation of q is of the form 2n5m, where n, m are non-negative integers. Then x has a
decimal expansion which terminates.
Consider the following examples:
So, these examples show us how we can convert a rational number of the form
p/q , where q is of the form 2n5m, to an equivalent rational number of the form
a/b , where b is a power of 10. Therefore, the decimal expansion of such a rational number
terminates.
| ||||||||||||||||||||
| Non - Terminating Decimal Numbers
If the decimal expression of p/q have an infinite number of digits after the decimal point, then the decimal so obtained is called a non - terminating decimal. For example,
1/3 = 0.33333......
1/7 = 0.14285714...
1/9 = 0.111111....
(i) Recurring Decimal Numbers
(ii) Non - Recurring Decimal Numbers
| ||||||||||||||||||||
| Recurring Decimal Numbers
If the decimal expression of
p/q
has a digit or set of digits that repeat at regular intervals after the decimal point, then the decimal so obtained is called a recurring or repeating decimal.
In non-terminating but repeating decimal expansion, you will find that the prime factorization of denominator has factors other than 2 and 5.
For example,
7/6 = 1.166666666666...... = 7/2 x 3
5/7 = 0.714285714285...... = 5/7
4/3 = 1.333333333333...... = 2 x 2/3
6/7 = 0.857142857142...... = 3 x 2/7
22/7 = 3.142857142857...... = 11 x 2/7
59/56 = 1.053571428571428...... = 59/23 x 7
7/6 = 1.166666666666...... = 1.16
5/7 = 0.714285714285...... = 0.714285
4/3 = 1.333333333333...... = 1.3
6/7 = 0.857142857142...... = 0.857142
22/7 = 3.142857142857...... = 3.142857
59/56 = 1.053571428571428......= 1.053571428
(i) Pure Recurring Decimal Numbers
(ii) Mixed Recurring Decimal Numbers
Pure Recurring Decimal Numbers are those decimal numbers in which the decimal part is repeated endlessly. For example,
5/7 = 0.714285714285...... = 0.714285
4/3 = 1.333333333333...... = 1.3
6/7 = 0.857142857142...... = 0.857142
22/7 = 3.142857142857...... = 3.142857
7/6 = 1.166666666666...... = 1.16
| ||||||||||||||||||||
|
If
p/q is a rational number, then its decimal expansion will be of recurring type if it satisfies the following conditions :
(i) The H.C.F of p and q is 1.
(ii) q can not be expressed as a prime factorisation of 2 and 5 i.e q=2n5m where n, m are some non-negative integers.
| ||||||||||||||||||||
| Theorem
Let x =
p/q be a rational number, such that the prime factorisation of q is not of the form 2n5m, where n, m are non-negative integers. Then, x has a decimal expansion which is non-terminating repeating (recurring).
Consider the following examples:
| ||||||||||||||||||||
| Practice Time
Without actually performing the long division, state whether the following rational
numbers will have a terminating decimal expansion or a non-terminating repeating decimal
expansion: (Write terminating or repeating only.)
| ||||||||||||||||||||
Email us for a quick response...