Prove that there is an integer $n>10^{2018}$ such that the sum of all primes less than $n$ is relatively prime to $n$. (R. Salimov)
Problem
Source: ARO 2018, regional olympiad, 11.8
Tags: number theory, relatively prime, prime numbers
29.03.2022 17:41
pavel kozlov wrote: Prove that there is an integer $n>10^{2018}$ such that the sum of all primes less than $n$ is relatively prime to $n$. (R. Salimov) Isn't this obvious? Since there are infinitely many primes, just take a prime $p > 10^{2018}$ and it satisfies the conditions. One might argue that it's possible for the sum of all primes below $p$ to equal $p$, but then choose a $p$, such that the sum of primes below $p$ is even, which will be always co-prime to $p$.
29.03.2022 17:48
why can't it be a multiple of $p$ also it's not obvious at all that there even exist arbitrarily large primes $p$ with the sum of the primes $< p$ even
29.03.2022 17:52
IAmTheHazard wrote: why can't it be a multiple of $p$ also it's not obvious at all that there even exist arbitrarily large primes $p$ with the sum of the primes $< p$ even Oh yes, forgot about the case when the sum may become a multiple of $p$.
29.03.2022 18:02
pavel kozlov wrote: Prove that there is an integer $n>10^{2018}$ such that the sum of all primes less than $n$ is relatively prime to $n$. (R. Salimov) Choose $p$ is a prime number big enough. Denote $p_1,...,p_k$ are prime numbers which are less than $p$ ( $p_1 < p_2 < ...<p_k$). If gcd($p_1+p_2+...+p_k$,$p$)=1 then we are done. Else, $$ p | p_1+p_2+..p_k$$$$ \Rightarrow kp=(p_1+...+p_k) < \dfrac{p(p+1)}{4}$$with $k$ is a positive integer. $$\Rightarrow k < [ \dfrac{p+1}{4} ] $$Take $q$ is the smallest prime which is bigger than $p$. $$\Rightarrow T= p_1 + p_2 +...+p_k + p=p.([ \dfrac{p+1}{4}] +1)$$Because $ q > [ \dfrac{p+1}{4}] +1 $ $\Rightarrow $ gcd($T,q$)=1. Thus, we can choose $n=q$.
29.03.2022 18:29
Romanian Stars Of Math 2021 (this is the original source, the romanians copied it from ARO regional) https://artofproblemsolving.com/community/c6h2504967p21170699
02.07.2023 00:18
Also Brazil Ibero Test 2018 Problem 2
08.02.2024 14:25
You can just take two sufficiently large consecultive primes $p_k<p_{k+1}$ (defining $p_1 < p_2 < \dots < p_{k-1}$ to be all the primes less than $p_k$) because, supposing there isn't such $n$, we have that $gcd(p_k, p_1+p_2+\dots +p_{k-1})>1 \implies gcd(p_k, p_1+p_2+\dots +p_{k-1})=p_k \implies p_k|p_1+p_2+\dots +p_{k-1} \implies p_k|p_1+p_2+\dots +p_{k-1}+p_k$, analogously we have that $p_{k+1}|p_1+p_2+\dots +p_{k-1}+p_k$, but $gcd(p_k,p_{k+1})=1 \implies p_kp_{k+1}|p_1+p_2+\dots +p_{k-1}+p_k$, so $p_kp_{k+1} \leq p_1+p_2+\dots +p_{k-1}+p_k < \underbrace{p_k+p_k+\dots +p_k+p_k}_{k \text{ times}} = kp_k < p_k^2 \implies p_kp_{k+1}<p_k^2 \implies p_{k+1}<p_k$ which is a contradiction!
08.02.2024 15:43
Legendary problem Let $S_i=\sum p_j, j \leq i$. Then, we know $S_i=p_{i+1}.k_i$, for $k_i \in \mathbb{Z_{+}}$. But notice that $$S_{i+1}=p_{i+2}.k_{i+1}=S_i+p_{i+1}=p_{i+1}.(k_i + 1)$$. If $k_{i+1} \geq k_i + 1$, then $p_{i+1}\geq p_{i+2}$, which is an absurd. Thus, $k_i$ is a non-increasing sequence of positive integers, so it eventually becomes constant. Let $c$ be this constant. Finishing: substituting $k_i=k_{i+1}=c$ in the above expression: $(c+1)p_{i+1}=p_{i+2}.c \to c | p_{i+1}$, which implies that $c=p_{i+1}$ (absurd for big enough $i$) or $c=1$, which is also obviously fake.
09.02.2024 07:22
Let $S_n, p_n$ be the sum of the $n$-th smaller primes and the $n$-th smaller prime, respectively. Assume for the sake of contradiction that the problem statement is false; then $p_np_{n+1} \mid S_n~ (*)$ for all $n$ large. By the prime number theorem, $p_n$ is asymptotically equal to $n\log n$ and therefore by $(*)$ we have $S_n =o({[n\log n]}^2)$; absurd because clearly $S_n=O(n^2\log n)$