Think and Reflect(Page no 39)
Q1. See if you can complete the argument about grouping by units, tens, hundreds, ... to justify why the addition algorithm works.
Answer:
Every number is a sum of groups of units, tens, hundreds, and so on.
For example, 473 = 4 hundreds + 7 tens + 3 units, and 695 = 6 hundreds + 9 tens + 5 units. Adding two numbers means adding the corresponding groups separately: units with units, tens with tens, hundreds with hundreds. If the units group has 10 or more, those 10 units form 1 ten, which is carried to the tens group. The same idea applies to tens, hundreds, etc. Because the place-value system is based on groups of 10, this carrying keeps the total value unchanged. Thus adding digit by digit from right to left gives the same result as counting all the dots together.
Q2. How would you modify the algorithm to add two decimal fractions?
Answer:
Modify the addition algorithm as follows:
- Write the numbers one below the other so that the decimal points are aligned. This automatically aligns units, tenths, hundredths, etc.
- If the numbers have different numbers of decimal places, pad the shorter one with zeros on the right so that both have the same number of decimal places.
- Add the digits column by column from right to left, including the carry, exactly as in whole-number addition.
- Place the decimal point in the answer directly below the decimal points in the question.
- If a final carry remains, write it to the left of the sum.
Exercise Set 11.1
Q1. Add two 4-digit numbers using the steps we have written down. Make sure you follow the steps precisely; do not perform any action that is not explicitly mentioned. Are you able to obtain the correct result?
Answer:
Example: Add 4732 + 6958.
- Write the numbers one below the other, aligned from right to left:
4732 +6958 ------
- Add the rightmost digits: 2 + 8 = 10. Write 0 below, carry 1.
- Next column: 3 + 5 + 1 = 9. Write 9, carry 0.
- Next column: 7 + 9 + 0 = 16. Write 6, carry 1.
- Next column: 4 + 6 + 1 = 11. Write 1, carry 1.
- No more digits. Carry is 1, so write 1 to the left of the bottom row.
Result: 4732 + 6958 = 11690.
Yes, by following the steps exactly, we obtain the correct result.
Q2. What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Answer:
Yes, the steps handle it correctly. Write the 3-digit number below the 5-digit number so that the rightmost digits are aligned. Treat the missing places in the 3-digit number as 0.
Example: 12345 + 678. Write it as:
12345 +00678 -------
Now add column by column from the right: 5 + 8 = 13, write 3, carry 1; 4 + 7 + 1 = 12, write 2, carry 1; 3 + 6 + 1 = 10, write 0, carry 1; 2 + 0 + 1 = 3, write 3, carry 0; 1 + 0 + 0 = 1, write 1. Result: 13023.
Q3. Why is it important to align the columns from right to left?
Answer:
Aligning from right to left ensures that digits with the same place value are added together: units with units, tens with tens, hundreds with hundreds, and so on. If the columns are not aligned, we may add units to tens or tens to hundreds, which gives a wrong answer. The rightmost digit is always the units digit, so aligning from the right fixes all place values correctly.
Q4. In Step 3, why cannot the value of carry be more than 1?
Answer:
In any column, we add two single digits and the previous carry. The maximum possible sum is 9 + 9 + 1 = 19. Therefore the carry to the next column can be at most 1. It cannot be 2 or more because even the largest possible column sum is less than 20.
Q5. What happens if we do not include the fifth step in the algorithm above? Give examples where the algorithm will work correctly and where it will fail to work.
Answer:
If we omit Step 5, the final carry is not written. The algorithm works correctly when there is no final carry. It fails when there is a final carry.
- Works correctly: 23 + 45. Units: 3 + 5 = 8, write 8, carry 0. Tens: 2 + 4 + 0 = 6, write 6. No final carry. Answer 68. Correct.
- Fails: 99 + 1. Units: 9 + 1 = 10, write 0, carry 1. Tens: 9 + 0 + 1 = 10, write 0, carry 1. If we stop and do not write the final carry, we get 00, not 100. So the algorithm fails.
Think and Reflect
Q1. Try to execute the algorithm to compute the divisors of 15, 135, and 775. How does the amount of work increase as the numbers grow?
Answer:
Using the algorithm “check each j from 1 to n and add j if it divides n”:
- divisors(15) = [1, 3, 5, 15]
- divisors(135) = [1, 3, 5, 9, 15, 27, 45, 135]
- divisors(775) = [1, 5, 25, 31, 155, 775]
The algorithm checks 15, 135, and 775 numbers respectively. As the number grows, the number of checks grows in direct proportion to the value of n. So the work increases roughly linearly with n. If the number of digits increases by one, the work becomes about 10 times as much.
Exercise Set 11.2
Q1. Suppose List 1 and List 2 are two lists of numbers in increasing order. (i) Write an algorithm to find elements in List 1 that are not present in List 2. (ii) Write an algorithm to find elements in List 2 that are not present in List 1.
Answer:
(i) Elements in List 1 not in List 2:
- Start with an empty list result.
- For each number x in List 1:
- Check whether x is present in List 2.
- If x is not present in List 2, add x to result.
- Report result.
(ii) Elements in List 2 not in List 1:
- Start with an empty list result.
- For each number y in List 2:
- Check whether y is present in List 1.
- If y is not present in List 1, add y to result.
- Report result.
Q2. Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Answer:
An efficient algorithm uses the relation lcm(m,n) = (m × n) / gcd(m,n).
- Compute g = gcd(m,n) using Euclid’s division algorithm.
- Compute lcm = (m × n) / g.
- Report the lcm.
Alternatively, start with the larger number and keep adding it to itself until the result is divisible by the other number. That common multiple is the lcm.
Q3. Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6). (i) If we write out divisors in pairs, how many numbers do we have to examine between 1 and n to find all the divisors of n? (ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?
Answer:
(i) We only need to examine numbers from 1 up to the square root of n. Each divisor pair has one factor less than or equal to the square root of n. So instead of checking all n numbers, we check about the square root of n numbers.
(ii) Not directly. The original gcd algorithm depends on the lists of divisors being in increasing order so that the rightmost common divisor is the gcd. If we list divisors in pairs, they may not be in increasing order. We would need to sort the lists or keep track of the largest common divisor while checking. With that modification, the method can still work.
Exercise Set 11.3
Q1. How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1?
Answer:
The list of divisors of n would be in decreasing order. In the original gcd algorithm, we iterate through the divisors of m in increasing order and check whether each one appears in the divisors of n. The membership check does not depend on the order of the second list. Therefore, the list of common divisors would still be in increasing order if the divisors of m are increasing. So the gcd result remains the same. However, if both lists were built in decreasing order, the common-divisors list would be decreasing, and we would need to take the leftmost element instead of the rightmost element.
Q2. What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1?
Answer:
If we start from min(m,n) and go downwards to 1, the first common divisor we find is the greatest common divisor. So we can stop immediately when we find it. This is more efficient than scanning upwards, because we do not have to check all the smaller numbers. For example, for m = 6, n = 12, start from 6: 6 divides both, so gcd(6,12) = 6 immediately.
End-of-Chapter Exercises
Q1. Compute the following using the improved version of Euclid's algorithm. (i) gcd(375, 825) (ii) gcd(51000, 81000) (iii) gcd(1789287, 237656) (iv) gcd(2587392, 157656)
Answer:
(i) gcd(375, 825)
825 = 375 × 2 + 75
375 = 75 × 5 + 0
So, gcd(375, 825) = 75.
(ii) gcd(51000, 81000)
81000 = 51000 × 1 + 30000
51000 = 30000 × 1 + 21000
30000 = 21000 × 1 + 9000
21000 = 9000 × 2 + 3000
9000 = 3000 × 3 + 0
So, gcd(51000, 81000) = 3000.
(iii) gcd(1789287, 237656)
1789287 = 237656 × 7 + 125695
237656 = 125695 × 1 + 111961
125695 = 111961 × 1 + 13734
111961 = 13734 × 8 + 2089
13734 = 2089 × 6 + 1200
2089 = 1200 × 1 + 889
1200 = 889 × 1 + 311
889 = 311 × 2 + 267
311 = 267 × 1 + 44
267 = 44 × 6 + 3
44 = 3 × 14 + 2
3 = 2 × 1 + 1
2 = 1 × 2 + 0
So, gcd(1789287, 237656) = 1.
(iv) gcd(2587392, 157656)
2587392 = 157656 × 16 + 64896
157656 = 64896 × 2 + 27864
64896 = 27864 × 2 + 9168
27864 = 9168 × 3 + 360
9168 = 360 × 25 + 168
360 = 168 × 2 + 24
168 = 24 × 7 + 0
So, gcd(2587392, 157656) = 24.
Q2. Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.
Answer:
Let m = qn + r, where r = m mod n. So 0 ≤ r < n.
If d divides both m and n:
Then d divides m − qn = r. So d divides both n and r = m mod n.
Conversely, if d divides both n and r = m mod n:
Then d divides qn + r = m. So d divides both m and n.
Hence the set of common divisors of m and n is exactly the same as the set of common divisors of n and m mod n. Therefore their gcd is the same.
Q3. Write an algorithm prime(n) to check if n is prime. (Hint: A prime number p has exactly two distinct factors, 1 and p. Can you make use of divisors(n) to write out prime(n)?)
Answer:
Algorithm prime(n):
- Compute the list of divisors of n using the algorithm divisors(n).
- If the list contains exactly two numbers, namely 1 and n, then report “n is prime”.
- Otherwise report “n is not prime”.
Example: divisors(13) = [1, 13], so 13 is prime. divisors(15) = [1, 3, 5, 15], so 15 is not prime.
Q4. Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers. (Hint: Compute divisors(n) and then filter out the primes in this list.)
Answer:
Algorithm primedivisors(n):
- Compute the list of divisors of n using divisors(n).
- Start with an empty list prime-divisors.
- For each divisor d in divisors(n):
- Check whether d is prime using the algorithm prime(d).
- If d is prime, add d to prime-divisors.
- Report prime-divisors.
Example: For n = 18, divisors(18) = [1, 2, 3, 6, 9, 18]. Filtering primes gives primedivisors(18) = [2, 3].
Q5. We can also find the gcd of two numbers by computing prime factorisation of both the numbers. Try to write an algorithm to compute the prime factorisation of a number. (i) The prime factorisation of 180 is 22 × 32 × 51. How would you represent this? (ii) How would you compare the prime factorisations of two numbers?
Answer:
Algorithm to compute prime factorisation of n:
- Start with the number n.
- Start with an empty list factors.
- For each divisor d from 2 to n:
- While d divides n, add d to factors and replace n by n/d.
- Report factors.
(i) Representation of 180 = 22 × 32 × 51:
Represent it as a list of pairs (prime, exponent):
[(2, 2), (3, 2), (5, 1)]
(ii) Comparing two prime factorisations:
Write both factorisations using the same set of primes. For each prime, compare the exponents.
- For gcd, take the minimum exponent of each prime and multiply them.
- For lcm, take the maximum exponent of each prime and multiply them.
- Two numbers are equal if their prime factorisations have exactly the same primes with the same exponents.