Verified step-by-step solutions for your class notes.
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: Let's add 4567 and 8924 using the algorithm:
1. Align right to left:
4567
+ 8924
2. Rightmost digits: 7 + 4 = 11. More than 10. Write 1. Carry = 1.
3. Next column (tens): 6 + 2 + 1 (carry) = 9. Less than 10. Write 9. Carry = 0.
4. Repeat (hundreds): 5 + 9 + 0 = 14. More than 10. Write 4. Carry = 1.
5. Repeat (thousands): 4 + 8 + 1 (carry) = 13. More than 10. Write 3. Carry = 1.
6. No more digits on left. Step 5: Carry is 1, so write 1 to the left.
Result: 13491. Yes, the correct result is obtained.
What happens if you add a 5-digit number to a 3-digit number. Do our steps handle this situation correctly?
Answer: Our steps, as strictly written, do not explicitly mention what to do when one number runs out of digits while the other still has digits left. To handle this correctly, we must assume that the missing columns of the 3-digit number are filled with leading zeros so that the "add the two digits" instruction in Step 3 still applies.
Why is it important to align the columns from right to left?
Answer: Aligning from right to left ensures that digits of the same place value (units with units, tens with tens, hundreds with hundreds) are added together. If aligned left to right, we might mistakenly add thousands to hundreds or tens, resulting in an incorrect sum.
In Step 3, why cannot the value of carry be more than 1?
Answer: The maximum single digit is 9. If we add two 9s and a previous carry of 1, the maximum possible sum in any column is $9 + 9 + 1 = 19$. Since 19 is less than 20, the tens digit (which becomes the new carry) can never exceed 1.
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: Step 5 adds the final leftover carry to the front of the answer.
Where it works correctly: It works for $32 + 45 = 77$. The final column is $3 + 4 = 7$ (carry 0). Since carry is not 1, Step 5 wouldn't trigger anyway.
Where it fails: It fails for $85 + 42$.
- Units: $5 + 2 = 7$, carry = 0.
- Tens: $8 + 4 + 0 = 12$. Write 2, carry = 1.
Without Step 5, the algorithm ends and gives the answer as 27 instead of 127.
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) Algorithm for elements in List 1 not in List 2:
1. Start with an empty list called 'difference-list'.
2. For each number x in List 1:
If x does not appear in List 2, add x to 'difference-list'.
3. Report 'difference-list'.
(ii) Algorithm for elements in List 2 not in List 1:
1. Start with an empty list called 'difference-list'.
2. For each number y in List 2:
If y does not appear in List 1, add y to 'difference-list'.
3. Report 'difference-list'.
Describe an algorithm to compute the least common multiple (lcm) of two numbers.
Answer:
Algorithm to find lcm(m, n):
1. Set a variable 'multiple' to the value of the larger number between m and n.
2. Check if 'multiple' is divisible by the smaller number.
3. If it is divisible, report 'multiple' as the lcm.
4. If it is not divisible, add the larger number to 'multiple' and repeat Step 2.
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 (i.e., $\sqrt{n}$). For every divisor $d \le \sqrt{n}$, its pair is $n/d$.
(ii) The original gcd algorithm assumes the generated divisor lists are in strictly increasing order to simply pick the "rightmost" element at the end. If we append both $d$ and $n/d$ at the same time, the list won't be strictly increasing unless we sort it afterwards. If we sort it, the algorithm works perfectly; if not, we must modify the last step to search the entire common-divisors list for the maximum value rather than just taking the rightmost element.
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 would be generated in strictly decreasing order instead of increasing order. Consequently, the list of common divisors would also be in decreasing order. Therefore, Step 5 of the original algorithm would need to change: instead of reporting the rightmost element (which would now be 1), it must report the leftmost element (the first and largest common divisor found).
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 work backwards to 1, the very first common divisor we encounter will be the greatest common divisor. This drastically improves efficiency because we can stop the loop immediately upon finding the first number that divides both m and n, rather than scanning all the way to $min(m,n)$ and constantly updating the most-recent-common-divisor.
Compute the following using the improved version of Euclid's algorithm (Āryabhaṭa's Division Algorithm).
Answer: Using repeated division to find the remainder ($m \mod n$):
(i) gcd(375, 825):
825 ÷ 375 = 2 remainder 75.
375 ÷ 75 = 5 remainder 0.
gcd = 75.
(ii) gcd(51000, 81000):
81000 ÷ 51000 = 1 remainder 30000.
51000 ÷ 30000 = 1 remainder 21000.
30000 ÷ 21000 = 1 remainder 9000.
21000 ÷ 9000 = 2 remainder 3000.
9000 ÷ 3000 = 3 remainder 0.
gcd = 3000.
(iii) gcd(1789287, 237656):
1789287 ÷ 237656 = 7 remainder 125695.
237656 ÷ 125695 = 1 remainder 111961.
125695 ÷ 111961 = 1 remainder 13734.
111961 ÷ 13734 = 8 remainder 2089.
13734 ÷ 2089 = 6 remainder 1200.
2089 ÷ 1200 = 1 remainder 889.
1200 ÷ 889 = 1 remainder 311.
889 ÷ 311 = 2 remainder 267.
311 ÷ 267 = 1 remainder 44.
267 ÷ 44 = 6 remainder 3.
44 ÷ 3 = 14 remainder 2.
3 ÷ 2 = 1 remainder 1.
2 ÷ 1 = 2 remainder 0.
gcd = 1.
(iv) gcd(2587392, 157656):
2587392 ÷ 157656 = 16 remainder 64896.
157656 ÷ 64896 = 2 remainder 27864.
64896 ÷ 27864 = 2 remainder 9168.
27864 ÷ 9168 = 3 remainder 360.
9168 ÷ 360 = 25 remainder 168.
360 ÷ 168 = 2 remainder 24.
168 ÷ 24 = 7 remainder 0.
gcd = 24.
Assume that $m \ge n$. Verify that $d$ divides $m$ and $n$ if and only if $d$ divides both $n$ and $m \mod n$.
Answer: Let $m \mod n = r$. By the division algorithm, we can write $m = qn + r$, where $q$ is the quotient. Therefore, $r = m - qn$.
Part 1 (Forward): Assume $d$ divides $m$ and $n$. Then $m = ad$ and $n = bd$ for some integers $a, b$. Substituting these into $r = m - qn$, we get $r = ad - q(bd) = d(a - qb)$. Since $(a - qb)$ is an integer, $d$ divides $r$ (which is $m \mod n$). So, $d$ divides both $n$ and $m \mod n$.
Part 2 (Backward): Assume $d$ divides $n$ and $r$ ($m \mod n$). Then $n = xd$ and $r = yd$ for some integers $x, y$. Substituting these into $m = qn + r$, we get $m = q(xd) + yd = d(qx + y)$. Since $(qx + y)$ is an integer, $d$ divides $m$. So, $d$ divides both $m$ and $n$.
Write an algorithm prime(n) to check if n is prime.
Answer:
Algorithm prime(n):
1. Let list-of-divisors be the list obtained by computing divisors(n).
2. Count the number of elements in list-of-divisors.
3. If the count is exactly 2, report "Prime".
4. Otherwise, report "Not Prime".
Write an algorithm primedivisors(n) to compute the list of divisors of n that are prime numbers.
Answer:
Algorithm primedivisors(n):
1. Let list-of-divisors be the list obtained by computing divisors(n).
2. Start with an empty list called 'prime-divisors-list'.
3. For each number x in list-of-divisors:
Execute prime(x) (from Exercise 3).
If prime(x) reports "Prime", add x to 'prime-divisors-list'.
4. Report 'prime-divisors-list'.
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 $2^2 \times 3^2 \times 5^1$. How would you represent this?
(ii) How would you compare the prime factorisations of two numbers?
Answer:
Algorithm for Prime Factorisation of n:
1. Create an empty list called 'factors'.
2. Set $d = 2$ (the smallest prime).
3. While $n > 1$:
If $n$ is divisible by $d$:
Add $d$ to 'factors'.
Set $n = n / d$.
Else:
Increase $d$ by 1.
4. Report 'factors'.
(i) Representation: It can be represented as a list of base-exponent pairs (e.g., [(2, 2), (3, 2), (5, 1)]) or just a flat list of primes [2, 2, 3, 3, 5].
(ii) Comparing factorisations to find GCD: To find the GCD, identify the prime bases that appear in both factorisations. For each common prime base, take the minimum of the exponents it has in the two representations. Multiply these resulting prime powers together to get the GCD.
Once this website finishes loading, every single subject, branch, chapter, and global search is already stored inside your browser's memory.