Prove that for every natural number $k$, at least one of the integers \[ 2k-1, \quad 5k-1 \quad \text{and} \quad 13k-1\]is not a perfect square.
Problem
Source: Cyprus 2022 Junior TST-3 Problem 1
Tags: number theory, Perfect Square
CT17
26.03.2022 23:47
If $k$ is even, then $2k-1$ cannot be a perfect square. If $k\equiv 3\pmod{4}$, $k\equiv 5\pmod{16}$, or $k\equiv 9\pmod{16}$, then $5k-1$ cannot be a perfect square. If $k\equiv 1\pmod{16}$ or $k\equiv 13\pmod{16}$, then $13k-1$ cannot be a perfect square. As we have exhausted all residues modulo $16$, we are done.
sd1006627
27.03.2022 00:00
With process of elimination, if $k$ is $1$, then $2k-1$ would be a perfect square. If $k$ is $13$, then $5k-1$ can't be a perfect square. Looking closely at the wording at least one of the integers can't be a perfect square for any natural number $k$. So, our answer is $13k-1$
MarkBcc168
27.03.2022 05:35
IMO 1986/1
the_mathmagician
15.08.2022 03:42
sd1006627 wrote: With process of elimination, if $k$ is $1$, then $2k-1$ would be a perfect square. If $k$ is $13$, then $5k-1$ can't be a perfect square. Looking closely at the wording at least one of the integers can't be a perfect square for any natural number $k$. So, our answer is $13k-1$ What this a proof your answer doesn't even make sense
We proceed with a proof by contradiction. Assume that all three are squares. We see that $2k-1$ implies that the square is odd. Since the quadratic residues modulo $4$ are $0, 1$, if the value is a square it must be $1 \pmod 4$. So we can write for a nonnegative integer $n$, $k=4n+1$. Substituting for $5k-1$ and $13k-1$, we find that $20n+4$ and $52n+12$ are both squares. Dividing both expressions by $4$, which preserves the property that this value is a square, we get $5n+1$ and $13n+3$. But these two values differ by $8n+2$, which is $2 \pmod 4$, which means that one of the two must not be a square, contradiction.