Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There was a final school exam in Russia recently, "Unified State Exam", that has the following problem in it's most complex chapter, "C":

C6: Find all numbers that end with "$0$" (decimal notation, of course) and have exactly fifteen natural divisors including "$1$" and the number itself.

What could be the solution that involves only school math?

share|improve this question
2  
..Is $\displaystyle\sigma_0(n)=\prod_{p\mid n}(1+v_p(n))$ school-ie enough? –  anon Jul 1 '12 at 6:04
    
End with "$0$" means that the number must have at least have one divisor of $2$ and one divisor of $5$. The rest follows from the divisor function. –  Eugene Jul 1 '12 at 6:04
    
What's that (sorry for being so dumb)? I mean, that product formula? –  mbaitoff Jul 1 '12 at 6:04

1 Answer 1

up vote 6 down vote accepted

We sort of need the link between prime factorization and the number of positive divisors. If $n$ has the prime factorization $p_1^{a_1}\cdots p_k^{a_k}$ then the number of positive factors of $n$ is $\prod (a_i+1)$. In particular the number of divisors is odd iff $n$ is a perfect square.

The fact that the number of divisors is odd iff our number is a perfect square can also be done in a formula-free way by a pairing argument. Any divisor $d$ of $n$ can be paired with the divisor $n/d$, which is different from $d$ unless $d=\sqrt{n}$.

Since $n$ ends in $0$ it has $2$ and $5$ and possibly others as prime factors. But $15$ gives very few possibilities: just two $2$'s and four $5$'s, or the other way around.

Remark: High school level? Hard to decide. Certainly every high school student who takes contests seriously is familiar with these facts. And, at least in the fairly recent past, Russian high school students took contests very seriously.

share|improve this answer
    
Looks like the most school-bound solution. –  mbaitoff Jul 1 '12 at 6:12
    
The number of positive factors is 15, which is 1*3*5. So, there are no more than 3 prime factors of $n$. Two of them are 2 and 5. How to prove that there's no third divisor? –  mbaitoff Jul 1 '12 at 6:16
1  
Baaw, got it. $1=(a_i+1)$. Thus, $a_i=0$. –  mbaitoff Jul 1 '12 at 6:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.