LAST EDITED ON Feb-12-01 AT 04:17 PM (EST)

Well, you should start somewhere. Forget about unwieldy numbers like 31, 43, etc. Think of smaller ones: 3, 7, 9, 13, 17, 19. The importance of trying by hand some examples can't be overestimated. I'll give one example: 21. 21 has four divisors: 1, 3, 7, 21. Two end in 1 (or 9) and two end in 3 or 7. Take another example: 273. 273 = 3·7·13. 273 has the following divisors: 1, 3, 7, 13, 21, 39, 91, 273. Of these, 4 end in 1 or 9, another 4 end in 3 or 7.

Let's also try 4641 = 3·7·13·17. 4641 has the following factors: 1, 3, 7, 13, 17, 21, 39, 51, 91, 119, 221, 273, 357, 663, 1547, 4641. (Check this. First take factors 3, 7, 13, 17 one by one. Then by twos, then by threes.) Of these 8 end in 1 or 9, and 8 end in 3 or 7.

I suggest you also consider, say, 819 = 3·3·7·13.

What's important is to understand that every pair of factors, of which one ends in 3 and the other in 7, produces a factor that ends in 1 - just take their product. But there may be factors that end in 1 that can't be obtained in this manner. 11 is one example.

Let N1, N3, N7, N9 be the number of factors of a given number that end respectively in 1, 3, 7, and 9. Then, because of the previous paragraph

N1 /gifs/ge.gif"] N3·N7.

How can you obtain factors that end in 9? You may take by twos either factors that end in 3 or factors that end in 7. There are N3·(N3 - 1)/2 of the first kind and N7·(N7 - 1)/2 of the second. Thus we obtain that

N9 N3·(N3 - 1)/2 + N7·(N7 - 1)/2.

We may add up the two inequalities:

N1 + N9 N3·N7 + N3·(N3 - 1)/2 + N7·(N7 - 1)/2.

Or written a little differently (check this):

N1 + N9 (N3 + N7)·(N3 + N7 - 1)/2

Look at the function y = x(x - 1)/2. Can you compare it to x? I.e., when x(x - 1)/2 x?. I claim that this happens for x3. You can prove this algebraically or drawing the graph of f. This means that, provided

N3 + N7 3,

we indeed have

N1 + N9 3 + N7.

If N3 + N7 < 3, you can check by hand (as in the starting paragraphs) that the inequality remains true.

P.S. I wonder whether your teacher had in mind anything of that sort, or I missed a simpler approach. If and when you learn that the problem may be solved in a simpler way, I would appreciate your posting it to the forum. Thank you.