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?

Hint 3

Take for example 63 = 7 * 9 . The w values are w(63) = -1, w(7) = -1, w(9) = 1 , and w(63) = w(7) * w(9) . Another example: 21 = 3 * 7 . The w values are w(21) = 1, w(3) = -1, w(7) = -1 , and w(21) = w(3) * w(7) . See if you can prove in general that w(r * s) = w(r) * w(s) . The number theory jargon for this is that w is "totally multiplicative". (A plain "multiplicative" function is one for which this multiplication rule holds whenever r and s are relatively prime; this is more common that the "totally multiplicative" case, so it gets the shorter name.)

Hint 4

This is proved by cases.

If r is even or divisible by 5 , then w(r) = 0 , but also r * s will be even or divisible by 5 and so w(r * s) = 0 .
If r and s both end in 1 or in 9 , their product ends in 1 or 9 ( 9 * 9 = 81), so w(r * s) = w(r) * w(s) in this case.
If r and s both end in 3 or 7 , their product ends in 1 or 9 (3 * 3 = 9, 3 * 7 = 21), so again w(r * s) = w(r) * w(s) .
If one of r and s ends in 1 or 9 with the other ending in 3 or 7 , their product ends in 3 or 7 ( 1 * 3 = 3 , 1 * 7 = 7 , 9 * 3 = 27 , 9 * 7 = 63), so it is true in this case too.

This result implies that the w value can be calculated based on the prime decomposition of the number; for example, w(63) = w(3)^2 * w(7) . Think about how to use this fact to write the sum over all divisors in a different way, involving the prime divisors of n.

The Rest of the Solution

The sum over all divisors can be written as a product over primes. For example,

example product for n = 63

And in general if

then we have

sum w(d) written as factor

because each integer d has a unique factorization into primes. Now we're nearly done! The key observation is that each term in this product is non-negative. Why? Because each w(p_i) is either 1 (and that sum is clearly positive) or -1 (and that sum is either 1 or 0 , depending on the number of terms, and so is always non-negative), or 0 (that sum is 1 ). The whole product contains only non-negative terms, and so is non-negative.

Quadratic Residues

This proof doesn't explain the apparently special status of 1 and 9 compared to 3 and 7 . Why are there more 1 and 9 divisors than 3 and 7 divisors instead of the other way around, or instead of being random?

Because we are only looking at the last digit of each divisor, we are essentially working modulo 10. Working to a general modulus m we say that the number n is a quadratic residue modulo m if there is an integer x such that

and if there is no such integer we say that n is a quadratic nonresidue modulo m. You can figure out all the quadratic residues just by forming the squares of all numbers reduced to that modulus, and then the nonresidues are anything left over; for example, modulo 10 the residues are 0, 1, 4, 5, 6, 9 and the nonresidues are the remaining classes, 2, 3, 7, 8. One thing we notice is that our excess classes 1 and 9 are both quadratic residues while our other classes 3 and 7 are nonresidues. Coincidence?

The theory of quadratic residues modulo a prime is much nicer than the theory for a general modulus, and most of the results are for prime moduli. One very important property for a prime modulus is that the product of any two residues or of any two nonresidues is a residue, while the product of a residue and a nonresidue is a nonresidue. This is exactly the property that we verified in Hint 4 for our weights! It's true that 10 is not a prime, but its quadratic residue properties are almost the same as they are for its prime divisor 5.

So the special status of divisors ending in 1 and 9 is that they are squares modulo 10.

References

You can read Johannes's original question here.
Quadratic residues are discussed in nearly every general number theory book, for example, An Introduction to the Theory of Numbers 5th edition, by G. H. Hardy and E. M. Wright, Oxford University Press, 1979, Chapter 6, and Elementary Number Theory by Edmund Landau, AMS Chelsea reprint, 1966, Part I Chapter VI.