Show that a number $n(n+1)$ where $n$ is positive integer is the sum of 2 numbers $k(k+1)$ and $m(m+1)$ where $m$ and $k$ are positive integers if and only if the number $2n^2+2n+1$ is composite.
Problem
Source: Romanian 2018 TST Problem 2 Day 2
Tags: number theory, quadratic reciprocity, Sum of Squares, composite numbers
25.05.2020 18:49
Claim 01. All prime divisors of $2n^2 + 2n + 1$ must be $1$ modulo $4$. $\textit{Proof.}$ Let $p$ be such prime divisor, then $p | 2n^2 + 2n + 1 | (2n + 1)^2 + 1$, where the conclusion follows. Now, \[ (2k + 1)^2 + (2m + 1)^2 = 2((2n + 1)^2 + 1) \]The number of solutions to the above equation in integers $x$ and $y$ is equal to $4d(N)$ where $N = (2n+1)^2 + 1$. The equality $2N = (2n+1)^2 + 1$ provides us eight solutions of $(x,y)$, so the above equation has a solution in positive integers $k$ and $m$ if and only if $d(N) > 2$, that is, if and only if $N$ is composite. For more information, https://artofproblemsolving.com/community/q2h1815883p12114677
11.02.2022 18:11
IndoMathXdZ wrote: Claim 01. All prime divisors of $2n^2 + 2n + 1$ must be $1$ modulo $4$. $\textit{Proof.}$ Let $p$ be such prime divisor, then $p | 2n^2 + 2n + 1 | (2n + 1)^2 + 1$, where the conclusion follows. Now, \[ (2k + 1)^2 + (2m + 1)^2 = 2((2n + 1)^2 + 1) \]The number of solutions to the above equation in integers $x$ and $y$ is equal to $4d(N)$ where $N = (2n+1)^2 + 1$. The equality $2N = (2n+1)^2 + 1$ provides us eight solutions of $(x,y)$, so the above equation has a solution in positive integers $k$ and $m$ if and only if $d(N) > 2$, that is, if and only if $N$ is composite. For more information, https://artofproblemsolving.com/community/q2h1815883p12114677 I think the equation is totally wrong