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.)

Need another hint? Click here.

Click here for the complete solution.