Algorithms · 4 marks

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) Only the numbers j with j × j ≤ n, that is, from 1 up to √n (for 18, only 1, 2, 3, 4). (ii) Not as described: the pair list (1, 18, 2, 9, 3, 6, …) is not in increasing order, so the rightmost common divisor need not be the gcd. Report the largest common divisor instead, or put the list in order first.

Step-by-step solution

Idea: If j divides n, so does n ÷ j, and one of the two is at most √n. So finding the small partner of each pair finds the big one too. But the gcd algorithm relied on the lists being in increasing order.

(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?

If j divides n, then n = j × (n ÷ j), so n ÷ j is also a divisor: its partner.
In each pair, the smaller number is at most √n: if both were bigger than √n, their product would be bigger than √n × √n = n.1 mark
So we only need to examine j = 1, 2, 3, … while j × j ≤ n, that is, up to √n. Each j that divides n gives the pair (j, n ÷ j). That is about √n numbers instead of n.½ mark
Example: n = 18, √18 ≈ 4.2. Examine 1, 2, 3, 4: 1 → (1, 18), 2 → (2, 9), 3 → (3, 6), 4 does not divide. Only 4 checks instead of 18. (If n is a perfect square, e.g. 36, the pair (6, 6) gives just one divisor.)½ mark

Only the numbers from 1 to √n (those j with j × j ≤ n); each divisor j found gives its partner n ÷ j. For 18, only 1, 2, 3, 4.

(ii) If we list out the divisors in pairs, will our gcd algorithm still work in the manner we have described?

Our gcd algorithm reports the rightmost element of the list of common divisors. That is the greatest only because the divisor lists were in increasing order.½ mark
Listed in pairs, the divisors are not in increasing order: 18 gives 1, 18, 2, 9, 3, 6. For 375 the pair list is [1, 375, 3, 125, 5, 75, 15, 25].½ mark
Run the algorithm for gcd(375, 825) with this list: keep each number that also divides 825. Common divisors come out as [1, 3, 5, 75, 15, 25]. The rightmost is 25, but gcd(375, 825) = 75. So the algorithm does not work as described.½ mark
Fix: report the largest element of common-divisors instead of the rightmost, or rearrange the divisors in increasing order first (write the small members of the pairs in order, then the large members in reverse: 1, 2, 3, 6, 9, 18).½ mark

No, not in the same manner: the pair list is not in increasing order, so the rightmost common divisor may not be the greatest (for 375 and 825 it gives 25 instead of 75). Taking the largest common divisor, or sorting first, fixes it.

(i) Only about √n numbers: those j with j × j ≤ n. (ii) No, not as described, because the pair list is not in increasing order; we must take the largest common divisor (or sort the list) instead of the rightmost.

Check: Pairs of 18 found from j = 1 to 4: 1 × 18 = 2 × 9 = 3 × 6 = 18 ✓. 375 ÷ 75 = 5 and 825 ÷ 75 = 11, so 75 (not 25) is the gcd ✓.

Answer to write in the exam

(i)

If j divides n, so does n ÷ j (pair: j × (n ÷ j) = n).

Smaller member of each pair ≤ √n (else product > n).

So examine only j = 1, 2, …, with j × j ≤ n (about √n numbers).

e.g. n = 18: examine 1, 2, 3, 4 → (1, 18), (2, 9), (3, 6)

∴ Only the numbers from 1 to √n need to be examined.

(ii)

gcd algorithm reports the rightmost common divisor; correct only if the lists are increasing.

Pair listing: 1, 18, 2, 9, 3, 6, … is not increasing.

e.g. 375 → [1, 375, 3, 125, 5, 75, 15, 25]; common with divisors of 825 → [1, 3, 5, 75, 15, 25]

Rightmost = 25, but gcd(375, 825) = 75 ✗

∴ No, not as described; report the largest common divisor, or sort the list first.

Common mistakes that cost marks

Answering “n ÷ 2 numbers” (half of n). Checking up to √n is enough, which is far fewer for large n.
In (ii), saying the algorithm fails because some divisors are missed. All divisors are still found; the problem is only their order.
Counting the middle divisor of a perfect square twice (6 in 36 = 6 × 6).

How this can come in the exam

MCQ (1 mark)

To find all the divisors of 400 by pairs, the largest number that must be examined is

Show answer

(A) 20
√400 = 20. Every divisor above 20 is the partner of one below 20.

Try one yourself

List the divisors of 72 in pairs. How many numbers did you examine?