How can you prove that the set of positive divisors of any (positive) integer n contains at least as many elements ending with 1 or 9 as elements ending with 3 or 7 ?

For example, the divisors of 63 are 1, 3, 7, 9, 21, 63 ; so 3 divisors end with 1 or 9 , and 3 divisors end with 3 or 7 .

For another example, the divisors of 441 are 1, 3, 7, 9, 21, 49, 63, 147, 441 ; so 5 divisors end with 1 or 9 , and 4 divisors end with 3 or 7 .

Hint 1

One way to think about this problem is to count all the divisors with different weights: Count those ending with 1 or 9 with weight +1 , those ending with 3 or 7 with weight -1 , and any other divisors with weight 0 . Then we want to show the total weight is always non-negative.

To formalize this, let's define a weight function:

If d is a divisor of n , define w(d) = +1 if d ends in 1 or 9, define w(d) = -1 if d ends in 3 or 7, and w(d) = 0 otherwise. Then we want to show

(Are we really any better off, or is this just empty formalism? We don't know yet, but sums over all divisors are very widely used in number theory, so it is a promising formalization.)

Hint 2

This problem is about factors and divisors, so it is natural to wonder if it is possible to infer the value of w(d) from the values of w at the divisors of d. If so, we might hope to get some kind of recursive proof. Try some examples; do you see any patterns?

Need another hint? Click here.

Click here for the complete solution.