SK 2015 Q20
20. The number \(N = 3^{16} - 1\) has a divisor of 193. It also has some divisors between 75 and 85 inclusive. What is the sum of these divisors?
Senior Kangaroo 2015, Question 20. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: 247
First factorise \(N\) twice using the difference of two squares i.e.
\(N = 3^{16} - 1 = (3^8 - 1)(3^8 + 1) = (3^4 - 1)(3^4 + 1)(3^8 + 1) = 80 \times 82 \times (3^8 + 1)\). This shows that both 80 and 82 are divisors of \(N\) in the required range. The question tells us that 193 is a divisor of N and, since 193 is prime, it must be a divisor of \(3^8 + 1 = 81 \times 81 + 1 = 6562\). Now observe that \(6562 = 2 \times 3281\) and that \(3281 \div 193 = 17\). Therefore \(N = 80 \times 82 \times 2 \times 17 \times 193\) or \(N = (2^4 \times 5) \times (2 \times 41) \times 2 \times 17 \times 193\).
Next consider the integers from 75 to 85 inclusive to see which could be divisors of \(N\). Because \(N\) has no prime factors of 3 or 7, we know that 75, 77, 78, 81 and 84 are not divisors of \(N\) while the initial argument established that 80 and 82 are divisors of \(N\). Both 79 and 83 are prime and \(76 = 4 \times 19\) so, since \(N\) does not have a prime factor of 79, 83 or 19, these must also be excluded. This only leaves 85 to be considered. Note that \(85 = 5 \times 17\) and both 5 and 17 are prime factors of \(N\) so 85 is a divisor of \(N\). Hence the divisors of \(N\) in the required range are 80, 82 and 85 with sum 247.
Solution © UK Mathematics Trust, from the SK 2015 solutions.