A positive integer $ m$ is called good if there is a positive integer $ n$ such that $ m$ is the quotient of $ n$ by the number of positive integer divisors of $ n$ (including $ 1$ and $ n$ itself). Prove that $ 1, 2, \ldots, 17$ are good numbers and that $ 18$ is not a good number.
Problem
Source: CGMO 2007 P1
Tags: number theory, prime factorization, number theory unsolved
dgreenb801
26.12.2009 01:20
If $ m$ is an odd prime, then we can let $ n = 8m$.
If $ m = 1$, $ n = 1$
If $ m = 2$, $ n = 8$
If $ m = 4$, $ n = 36$
If $ m = 6$, $ n = 72$
If $ m = 8$, $ n = 80$
If $ m = 9$, $ n = 108$
If $ m = 10$, $ n = 180$
If $ m = 12$, $ n = 240$
If $ m = 16$, $ n = 128$
Let the prime factorization of $ n$ be $ 2^{a_1}3^{a_2}5^{a_3}...p_n^{a_n}$
Note that for any prime $ p$, $ \frac {p^x}{x + 1}$ is minimized when $ x = 1$. So if $ m = 18 = 2 \cdot 3^2$, then since $ 18|n$, $ n$ would have to be at least $ \frac {2^1 \cdot 3^2}{2 \cdot 3} = 3$. Thus, no prime $ k$ greater than $ 11$ can be in the prime factorization of $ n$, or we would have to multiply this by at least $ \frac {k}{2}$ which would make the result greater than $ 18$. If $ 7$ or $ 11$ was in the prime factorization of $ n$, then one of the exponents on the other primes would have to be a multiple of $ 6$ or $ 10$, making the quotient too great. Thus, the quotient is of the form
$ \frac {2^{a_1}3^{a_2}5^{a_3}}{(a_1 + 1)(a_2 + 1)(a_3 + 1)}$
We easily see $ a_3$ is either $ 0$ or $ 1$, or the fraction is too large. If it is $ 1$, then one of the other exponents must be $ 4$, and we can easily check that there is no solution. Thus, the quotient is of the form
$ \frac {2^{a_1}3^{a_2}}{(a_1 + 1)(a_2 + 1)}$.
Since $ a_2$ is at least $ 2$, and also odd, it must be $ 3$, as $ 5$ would make the fraction too large. But we can easily check there is no solution in this case Thus, $ 18$ is not a good number.
But I can't attain $ 14$ or $ 15$. Can anyone show how to get $ 14$ or $ 15$?
pco
26.12.2009 12:01
dgreenb801 wrote: But I can't attain $ 14$ or $ 15$. Can anyone show how to get $ 14$ or $ 15$? $ 14=\frac{252}{18}=\frac{2^2}3\frac{3^2}3\frac 72$ $ 15=\frac{360}{24}=\frac{2^3}{4}\frac{3^2}3\frac 52$