In other words, we needed only two reduction steps to get to the final answer. Check that this would happen for any similar problem of the form gcd(2k + 1, 2).
Step-by-step solution
Idea: An odd number 2k + 1 always leaves remainder 1 when divided by 2, whatever k is. So the first reduction always gives gcd(2, 1), and the second always gives gcd(1, 0).
- For a natural number k, 2k + 1 ≥ 3 > 2, so no reversal is needed. 2k + 1 = k × 2 + 1, so dividing by 2 leaves remainder 1: (2k + 1) mod 2 = 1. First reduction: gcd(2k + 1, 2) → gcd(2, 1).1 mark
- 2 mod 1 = 0. Second reduction: gcd(2, 1) → gcd(1, 0). Now n = 0, so the answer is 1.½ mark
- Neither step depends on k, so every problem of this form needs exactly two reductions. Examples: gcd(7, 2) → gcd(2, 1) → gcd(1, 0); gcd(1001, 2) → gcd(2, 1) → gcd(1, 0). (With subtraction, gcd(1001, 2) would need about 500 steps.)½ mark
Answer to write in the exam
2k + 1 = k × 2 + 1 ⇒ (2k + 1) mod 2 = 1
gcd(2k + 1, 2) = gcd(2, 1)
2 mod 1 = 0 ⇒ gcd(2, 1) = gcd(1, 0)
n = 0 ⇒ answer 1
∴ Always two reductions, for every k; gcd(2k + 1, 2) = 1
Common mistakes that cost marks
- Checking a few values of k only (gcd(7, 2), gcd(9, 2)) and stopping. The question says “any” problem of this form, so show the remainder is 1 for every k.
- Writing (2k + 1) mod 2 = k (the quotient) instead of 1 (the remainder).
- Counting the final “report the answer” step as a third reduction.
How this can come in the exam
Assertion (A): gcd(2k + 1, 2) = 1 for every natural number k.
Reason (R): 2k + 1 leaves remainder 1 when divided by 2.
- Both A and R are true, and R is the correct explanation of A.
- Both A and R are true, but R is not the correct explanation of A.
- A is true but R is false.
- A is false but R is true.
Show answer
(A) Both A and R are true, and R is the correct explanation of A.
By R, gcd(2k + 1, 2) = gcd(2, 1) = gcd(1, 0) = 1. R explains A.
Try one yourself
Show that, for any natural number k, the division algorithm finds gcd(3k + 1, 3) in two reductions. What is the gcd?
Show answer
(3k + 1) mod 3 = 1 → gcd(3, 1); 3 mod 1 = 0 → gcd(1, 0). Two reductions; the gcd is 1.
More questions like this
- The above modified algorithm can be carried out concisely using the “long division” method given by Indians at least from the time of Āryabhaṭa. We illustrate the method through the following examples—
- Compute the following using the improved version of Euclid’s algorithm.
- Assume that m ≥ n. Verify that d divides m and n if and only if d divides both n and m mod n.
- 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)?) - 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.)