(Challenge) Divisors occur in pairs. For instance, the divisors of 18 are (1, 18), (2, 9) and (3, 6).
Question 84 marksMedium
(Challenge) 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?
(i) If j divides n, then so does n÷j, and j×(n÷j)=n. In each pair, the smaller number j satisfies j×j≤n (if both numbers of a pair were larger than this, their product would be more than n).
So we only need to examine the numbers j=1,2,3,… while j×j≤n. Each time j divides n, we write down the pair (j,n÷j). The number of values to examine is the largest whole number whose square is at most n, that is, about n, instead of n.
For 18: 4×4=16≤18 but 5×5=25>18, so we examine only 1, 2, 3, 4 (4 numbers instead of 18) and get the pairs (1, 18), (2, 9), (3, 6). For 825 we examine 1 to 28 (since 28×28=784 and 29×29=841), 28 numbers instead of 825.
(When n is a perfect square, one pair has two equal numbers, for example (6, 6) for 36, and we write that divisor only once.)
(ii) Not without a change. Our gcd algorithm reports the rightmost element of the list of common divisors, which is the gcd only because the lists of divisors are in increasing order. A list written in pairs is not in increasing order: for 18 it is [1, 18, 2, 9, 3, 6].
Checking each divisor of 375 in turn against the second list gives the common divisors [1,3,5,75,15,25]. The rightmost element is 25, but gcd(375,825)=75. So the algorithm, as described, gives a wrong answer.
To make it work, change the last step to "report the largest element of common-divisors" (scan the list keeping the largest so far), or first arrange the divisors in increasing order (write the smaller numbers of the pairs from left to right, then the larger numbers from right to left). With either change the answer is 75, and the algorithm is still correct.