Maths Olympiad Prep

Library / /12 of 63

Number theory Difficulty 6.3 National olympiad Prove it Japan

Suppose a positive integer has the property that the sum of the remainders when its factors are divided by 44 equals 10001000. Determine all positive integers having this property.

Solution

For a positive integer nn, let us denote by S(n)S(n) the sum of all the positive factors of nn whose remainder when divided by 44 is not equal to 22. Let us first determine S(n)S(n).
Suppose the prime factorization of nn is given by
2mp1m1pkmk(p1,,pk are distinct odd primes, m0,m1,,mk1). 2^m p_1^{m_1} \cdots p_k^{m_k} \quad (p_1, \ldots, p_k \text{ are distinct odd primes, } m \ge 0, m_1, \ldots, m_k \ge 1).
Since the fact that an integer has a remainder 22 when divided by 44 is equivalent to the fact that it is divisible by 22 only once, we can see that S(n)S(n) is the sum of all numbers of the form
2lp1l1pklk(where 0lm,1l1,0l1m1,,0lkmk). 2^l p_1^{l_1} \cdots p_k^{l_k} \quad (\text{where } 0 \le l \le m, 1 \ne l \ne 1, 0 \le l_1 \le m_1, \ldots, 0 \le l_k \le m_k).
Consequently, S(n)S(n) equals
l=0,l1m2ll1=0m1p1l1lk=0mkpklk. \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 mm,
f(2,m)=l=0,l1m2l;f(p,m)=l=0mpl(when p is a prime 2). f(2, m) = \sum_{l=0, l \ne 1}^{m} 2^l; \quad f(p, m) = \sum_{l=0}^{m} p^l \quad (\text{when } p \text{ is a prime } \ne 2).
Then, if n=2mp1m1pkmkn = 2^m p_1^{m_1} \cdots p_k^{m_k}, we have S(n)=f(2,m)f(p1,m1)f(pk,mk)S(n) = f(2, m)f(p_1, m_1) \cdots f(p_k, m_k). In order to determine positive integers nn for which S(n)=1000S(n) = 1000, let us first determine the pairs (p,m)(p, m), where pp is a prime and mm is a positive integer for which f(p,m)f(p, m) is a factor of 10001000.

When p=2p=2, we get that if m9m \ge 9, then f(2,m)f(2,9)=1021f(2, m) \ge f(2, 9) = 1021. So, it is sufficient to consider the cases for m8m \le 8, and we can conclude that f(2,1)=1f(2, 1) = 1, f(2,2)=5f(2, 2) = 5, f(2,6)=125f(2, 6) = 125 are the only cases which give a factor of 10001000 for f(2,m)f(2, m).
When 3p313 \le p \le 31, we can similarly check that f(3,1)=4f(3, 1) = 4, f(3,3)=40f(3, 3) = 40, f(7,1)=8f(7, 1) = 8, f(19,1)=20f(19, 1) = 20 are the only cases for this range of primes pp for which f(p,m)f(p, m) is a factor of 10001000.
When p32p \ge 32, we get if m2m \ge 2 f(p,m)f(m,2)=1+p+p21+32+322>1000f(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=1m=1 only for this range of pp, and we get f(199,1)=200f(199, 1) = 200, f(499)=500f(499) = 500 as the only possibilities for a factor of 10001000.
Finally, we search for combinations of these values of f(p,m)f(p, m)'s which yield the product 10001000, and we find that the desired answer is given by 26×71=4482^6 \times 7^1 = 448 and 22×1991=7962^2 \times 199^1 = 796.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.