Let
How many divisors of are strictly smaller than and do not divide ?
, 2016
Solution
A number with prime factorization has
divisors. The number can be factored as , so
If divides then also divides , so all divisors can be sorted into pairs , omitting the number , which would otherwise be paired with itself. In each pair exactly one divisor is smaller than and one is greater than . This implies that the number of divisors of which are strictly smaller than is equal to the number of pairs, which is
Each divisor of also divides , so we have to subtract the number of divisors of smaller than . The number of divisors of which are smaller than and do not divide is therefore equal to
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.