Olympiad Maths Prep

Track / Stage 6 / 327 of 400 #1327 of 2000

Problem 1327

National olympiad, first round
Number theory Difficulty 6.6 Find the answer

For a positive integer mm, let φ(m)\varphi(m) be the number of positive integers kmk \le m such that kk and mm are relatively prime, and let σ(m)\sigma(m) be the sum of the positive divisors of mm. Find the sum of all even positive integers nn such that
n5σ(n)2φ(n) \frac{n^5\sigma(n) - 2}{\varphi(n)}
is an integer.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Define the functions and the problem statement:
- Let φ(m) \varphi(m) be the Euler's totient function, which counts the number of positive integers up to m m that are relatively prime to m m .
- Let σ(m) \sigma(m) be the sum of the positive divisors of m m .
- We need to find the sum of all even positive integers n n such that
n5σ(n)2φ(n) \frac{n^5 \sigma(n) - 2}{\varphi(n)}
is an integer.

2. **Express n n in terms of its prime factors:**
- Let n=2ap1a1p2a2pkak n = 2^a p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} where pi p_i are odd primes.
- The Euler's totient function for n n is:
φ(n)=φ(2a)φ(p1a1)φ(p2a2)φ(pkak) \varphi(n) = \varphi(2^a) \varphi(p_1^{a_1}) \varphi(p_2^{a_2}) \cdots \varphi(p_k^{a_k})
Since φ(2a)=2a2a1=2a1 \varphi(2^a) = 2^a - 2^{a-1} = 2^{a-1} for a1 a \geq 1 , and φ(piai)=piaipiai1 \varphi(p_i^{a_i}) = p_i^{a_i} - p_i^{a_i-1} .

3. Analyze the divisibility condition:
- We need n5σ(n)2φ(n) \frac{n^5 \sigma(n) - 2}{\varphi(n)} to be an integer.
- Consider the 2-adic valuation v2 v_2 of φ(n) \varphi(n) :
v2(φ(n))=(a1)+v2(φ(p1a1))+v2(φ(p2a2))++v2(φ(pkak)) v_2(\varphi(n)) = (a-1) + v_2(\varphi(p_1^{a_1})) + v_2(\varphi(p_2^{a_2})) + \cdots + v_2(\varphi(p_k^{a_k}))
Since pi p_i are odd primes, v2(φ(piai))=0 v_2(\varphi(p_i^{a_i})) = 0 . Thus,
v2(φ(n))=a1 v_2(\varphi(n)) = a - 1

4. **Evaluate v2(n5σ(n)2) v_2(n^5 \sigma(n) - 2) :**
- For n=2ap1a1p2a2pkak n = 2^a p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} , n5σ(n) n^5 \sigma(n) is even, so n5σ(n)2 n^5 \sigma(n) - 2 is odd.
- Therefore, v2(n5σ(n)2)=1 v_2(n^5 \sigma(n) - 2) = 1 .

5. Set up the inequality:
- We need v2(n5σ(n)2)v2(φ(n)) v_2(n^5 \sigma(n) - 2) \geq v_2(\varphi(n)) :
1a1 1 \geq a - 1
This implies:
a2 a \leq 2

6. **Consider possible values of a a and k k :**
- If a=1 a = 1 , then n=2p n = 2p where p p is an odd prime.
- If a=2 a = 2 , then n=4 n = 4 .

7. Evaluate specific cases:
- For n=2p n = 2p :
φ(2p)=p1,σ(2p)=(1+2)(1+p)=3(p+1) \varphi(2p) = p-1, \quad \sigma(2p) = (1+2)(1+p) = 3(p+1)
We need:
(2p)53(p+1)2p1 to be an integer \frac{(2p)^5 \cdot 3(p+1) - 2}{p-1} \text{ to be an integer}
Simplifying:
96p6+96p52p1 \frac{96p^6 + 96p^5 - 2}{p-1}
This implies p1 p-1 must divide 190. Possible values of p1 p-1 are 2, 10, 190, giving p=3,11,191 p = 3, 11, 191 .

- For n=4 n = 4 :
φ(4)=2,σ(4)=1+2+4=7 \varphi(4) = 2, \quad \sigma(4) = 1 + 2 + 4 = 7
We need:
45722=71662=3583 which is an integer \frac{4^5 \cdot 7 - 2}{2} = \frac{7166}{2} = 3583 \text{ which is an integer}

8. **Sum the valid n n values:**
- Valid n n values are 2,4,6,22,382 2, 4, 6, 22, 382 .
- Sum: 2+4+6+22+382=416 2 + 4 + 6 + 22 + 382 = 416 .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.