Given that $n$ and $r$ are positive integers. Suppose that \[ 1 + 2 + \dots + (n - 1) = (n + 1) + (n + 2) + \dots + (n + r) \]Prove that $n$ is a composite number.
Problem
Source: Indonesia Mathematical Olympiad (INAMO) 2019 Problem 01
Tags: number theory, primes
02.07.2019 10:58
Oops forgot the case $n=1$ my bad. It’s added in the end now
02.07.2019 11:11
Using the sum of series, we have, $$(n+r)(n+r+1)=n(n-1)+n(n+1)$$After algebraic calculations, we get, $$\implies (r+2n)(r+1)=3n$$then, $r+1 \geq 3$. If $r=2$ $$n^2-n=4n+6 \implies n=6$$which is composite. If $r+1>3$, then also $n$ is composite. So, we are done.
02.07.2019 11:36
My solution is as follow: We have \[ n(n - 1) = 2rn + r(r + 1) \]\[ n^2 - n = 2rn + r^2 + r \]Notice that if $n = 1$, then $RHS > LHS = 0$. Now, suppose that $n$ is a prime, then we have \[ 2n^2 = (n + r)(n + r + 1) \]Suppose $n = 2$, since $GCD(n + r, n + r + 1) = 1$, then we have $n + r = 1$ or $n + r + 1 = 1$. Both of which is impossible. Suppose $n > 2$, since $GCD(n + r, n + r + 1) = 1$, then we have either $n + r$ or $n + r + 1$ must be 2. But we have $n \ge 3$. Thus, we are hence finished,
02.07.2019 11:54
oi, tanya nomor 2 dong
03.07.2019 15:52
The relation is equivalent with $\frac{n(n-1)}{2}=nr+\frac{r(r+1)}{2}$, or $n(n-1-2r)=r(r+1)$. Since $n$ divides LHS so $n$ divides RHS as well. Assuming $n$ is prime, therefore $n|r$ or $n|r+1$. This means, $r\ge n-1$. So, there are at least $n-1$ terms (from $n+1$ to $n+r$) in RHS, same as LHS. Simple comparison gives us contradiction.
03.07.2019 16:59
Case $n=1$ already covered; now suppose $n$ is prime. Again, using some of series, $(n-1)n=r(2n+r+1)$. Because $n$ is prime, then $n|r(r+1)$, implying $n|r$ or $n|r+1$. Both imply $n\leq r+1$ (or $n-1\leq r)$. Then $r(2n+r+1)\leq rn$ and $n+r+1\leq 0$, absurd.
20.08.2023 04:33
if $n=1$ automatically rhs is bigger now assume that $n = p$ for some prime $1+....+(p-1) = \frac{p(p-1)}{2}$ $(p+1)+....+(p+r) = rp+\frac{(r)(r+1)}{2}$ $p(p-1) = 2rp+r(r+1)$ $p(p-1) = r(2p+r+1)$ Case 1 $p \mid r$ $p(p-1) = 2kp^2+kp(kp+1) \geq 2p^2+p(p+1)$ $p-1 \geq 3p+1$ contradiction since it implied $p \leq -1$ Case 2 if $p\mid r+1$ $r+1= kp$ $p(p-1) = (kp-1)(2p+kp)$ $(p-1) = (kp-1)(2+k)$ $(p-1) = (kp-1)(2+k) \geq (p-1)(2+k)$ $1\geq 2+k$ $k\leq -1$
25.11.2023 04:48
If $n=1$, we have that \[0 = (n+1)+\dots + (n+r)\]clearly, the RHS is positive which is a clear contradiction. Thus, $n \geq 2$. By way of contradiction, assume $n=p$ for a prime $p$, for some $r \in \mathbb{N}$. Then, \begin{align*} 1+2+\dots + (p-1) &= (p+1) + (p+2) + \dots + (p+r)\\ \frac{p(p-1)}{2} &= \frac{r(2p+r+1)}{2}\\ p(p-1) &= r(2p+r+1) \end{align*}So, $p \mid r$ or $p \mid 2p+r+1$. This allows us to separate into two cases. Case 1 : $p \mid r$. This means, $r \geq p$. But then, \[p(p-1)=r(2p+r+1) \geq p(3p+1)\]But, for all $p \geq 2$, clearly $p-1<3p+1$ so the above inequality is a clear contradiction implying that there exists no such $p,r$ for this case. Case 2 : $p \mid 2p+r+1$. This means, $2p+r+1 \equiv 0 \pmod{p}$ which gives us that $r \equiv -1 \pmod{p}$. Thus, $r \geq p-1$. Note that this gives us \[p(p-1)=r(2p+r+1)\geq (p-1)(2p+p-1+1)=3p(p-1)\]which is impossible for all primes $p \geq 2$. Thus, there exists no working $p,r$ in this case too. Thus, we see that $n$ cannot be prime and indeed $n$ must be a composite number as claimed.
19.10.2024 08:00
Clearly, $n=1$ doesn't work. FTSOC, let $n$ be a prime. Now, we have $r|n(n-1)$, and $n|r(r+1)$. Since $n$ is a prime, and $r<n$, we have that $g.c.d(n,r)=1$. Thus, $r|n-1$, and $n|r+1$. The only possible value here for $r=n-1$. Substituting this value into the given equation, we see that there are no solutions. Thus, $n$ must be a composite number.