Japan Mathematical Olympiad

For a positive integer $n$, let us denote by $S(n)$ the sum of all the positive factors of $n$ whose remainder when divided by $4$ is not equal to $2$. Let us first determine $S(n)$. Suppose the prime factorization of $n$ is given by $$2^m{p}_1^{m_1}\cdots p_k^{m_k}(p_1,\dots ,p_k\text{ are distinct odd primes, }m\ge 0,m_1,\dots ,m_k\ge 1).$$ Since the fact that an integer has a remainder $2$ when divided by $4$ is equivalent to the fact that it is divisible by $2$ only once, we can see that $S(n)$ is the sum of all numbers of the form $$2^l{p}_1^{l_1}\cdots p_k^{l_k}(\text{where }0\le l\le m,1\ne l\ne 1,0\le l_1\le m_1,\dots ,0\le l_k\le m_k).$$ Consequently, $S(n)$ equals $$\sum _{l=0,l\ne 1}^m{2}^l\sum _{l_1=0}^{m_1}{p}_1^{l_1}\cdots \sum _{l_k=0}^{m_k}{p}_k^{l_k}.$$ (Note that because of the distributive law the number of terms in each sum corresponds to the number of possible values for each of the exponents.) For the sake of simplicity, let for each non-negative integer $m$, $$f(2,m)=\sum _{l=0,l\ne 1}^m{2}^l;f(p,m)=\sum _{l=0}^m{p}^l(\text{when }p\text{ is a prime }\ne 2).$$ Then, if $n=2^m{p}_1^{m_1}\cdots p_k^{m_k}$, we have $S(n)=f(2,m)f(p_1,m_1)\cdots f(p_k,m_k)$. In order to determine positive integers $n$ for which $S(n)=1000$, let us first determine the pairs $(p,m)$, where $p$ is a prime and $m$ is a positive integer for which $f(p,m)$ is a factor of $1000$.

When $p=2$, we get that if $m\ge 9$, then $f(2,m)\ge f(2,9)=1021$. So, it is sufficient to consider the cases for $m\le 8$, and we can conclude that $f(2,1)=1$, $f(2,2)=5$, $f(2,6)=125$ are the only cases which give a factor of $1000$ for $f(2,m)$. When $3\le p\le 31$, we can similarly check that $f(3,1)=4$, $f(3,3)=40$, $f(7,1)=8$, $f(19,1)=20$ are the only cases for this range of primes $p$ for which $f(p,m)$ is a factor of $1000$. When $p\ge 32$, we get if $m\ge 2$ $f(p,m)\ge f(m,2)=1+p+p^2\ge 1+32+32^2>1000$. So, it is enough to check the cases for $m=1$ only for this range of $p$, and we get $f(199,1)=200$, $f(499)=500$ as the only possibilities for a factor of $1000$. Finally, we search for combinations of these values of $f(p,m)$'s which yield the product $1000$, and we find that the desired answer is given by $2^6\times 7^1=448$ and $2^2\times 199^1=796$.