Maths Olympiad Prep

Library / /19 of 24

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Netherlands

A positive integer nn is called divisor primary if for every positive divisor dd of nn at least one of the numbers d1d-1 and d+1d+1 is prime. For example, 88 is divisor primary, because its positive divisors 11, 22, 44, and 88 each differ by 11 from a prime number (22, 33, 55, and 77, respectively), while 99 is not divisor primary, because the divisor 99 does not differ by 11 from a prime number (both 88 and 1010 are composite).
Determine the largest divisor primary number.

Solution

Suppose nn is divisor primary. Then nn cannot have an odd divisor d5d \ge 5. Indeed, for such a divisor, both d1d-1 and d+1d+1 are even. Because d1>2d-1 > 2, these are both composite numbers and that would contradict the fact that nn is divisor primary. The odd divisors 11 and 33 can occur, because the integer 33 itself is divisor primary.

Because of the unique factorisation in primes, the integer nn can now only have some factors 22 and at most one factor 33. The number 26=642^6 = 64 and all its multiples are not divisor primary, because both 63=7963 = 7 \cdot 9 and 65=51365 = 5 \cdot 13 are not prime. Hence, a divisor primary number has at most five factors 22. Therefore, the largest possible number that could still be divisor primary is 325=963 \cdot 2^5 = 96.

We now check that 9696 is indeed divisor primary: its divisors are 11, 22, 33, 44, 66, 88, 1212, 1616, 2424, 3232, 4848, and 9696, and these numbers are next to 22, 33, 22, 33, 55, 77, 1111, 1717, 2323, 3131, 4747, and 9797, which are all prime. Therefore, the largest divisor primary number is 9696. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.