Verified step-by-step solutions for your class notes.
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.