Maths Olympiad Prep

Track / Stage 6 / 219 of 400 #1219 of 1964

Problem 1219

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

For every integer n3n\geq 3, let sns_n be the sum of all primes (strictly) less than nn. Are there infinitely many integers n3n\geq 3 such that sns_n is coprime to nn?

Russian Competition

The source for this one didn't record the answer, so there is nothing to check what you type against. Work it on paper and mark yourself against the solution below.

Official solution

1. **Define the sequence of primes and the sum sn s_n :**
Let {p1,p2,p3,}={2,3,5,}\{p_1, p_2, p_3, \dots\} = \{2, 3, 5, \dots\} be the ordered set of primes. For every integer n3 n \geq 3 , let sn s_n be the sum of all primes strictly less than n n .

2. Assume the contrary:
Suppose there are finitely many integers n3 n \geq 3 such that sn s_n is coprime to n n . This implies there exists some integer N N such that for all primes p>N p > N , psp p \mid s_p .

3. **Express sp s_p in terms of p p :**
For primes pk+1>N p_{k+1} > N , there exist positive integers ci c_i such that cipk+i=sk+i1 c_i p_{k+i} = s_{k+i-1} for all i1 i \geq 1 . This implies:
ci+1pk+i+1=(ci+1)pk+i c_{i+1} p_{k+i+1} = (c_i + 1) p_{k+i}

4. **Analyze the sequence ci c_i :**
Since pk+i<pk+i+1 p_{k+i} < p_{k+i+1} , the equation ci+1pk+i+1=(ci+1)pk+i c_{i+1} p_{k+i+1} = (c_i + 1) p_{k+i} implies:
ci+1<ci+1 c_{i+1} < c_i + 1
Therefore, ci+1ci c_{i+1} \leq c_i . Since ci c_i is a sequence of positive integers, it must eventually become constant. Let ci=C c_i = C for sufficiently large i i .

5. Derive a contradiction:
For large t t , taking i=tk i = t - k and tk+1 t - k + 1 in the equation ci+1pk+i+1=(ci+1)pk+i c_{i+1} p_{k+i+1} = (c_i + 1) p_{k+i} gives:
Cpt+1=(C+1)pt C p_{t+1} = (C + 1) p_t
and
Cpt+2=(C+1)pt+1 C p_{t+2} = (C + 1) p_{t+1}
Combining these, we get:
C2pt+2=(C+1)2pt C^2 p_{t+2} = (C + 1)^2 p_t
This implies:
pt+12=pt+2pt p_{t+1}^2 = p_{t+2} p_t
which is a contradiction because the sequence of primes is strictly increasing and pt+12pt+2pt p_{t+1}^2 \neq p_{t+2} p_t .

6. Conclusion:
Since our assumption leads to a contradiction, there must be infinitely many integers n3 n \geq 3 such that sn s_n is coprime to n n .

\blacksquare

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