Consider the sequence $u_0, u_1, u_2, ...$ defined by $u_0 = 0, u_1 = 1,$ and $u_n = 6u_{n - 1} + 7u_{n - 2}$ for $n \ge 2$. Show that there are no non-negative integers $a, b, c, n$ such that $$ab(a + b)(a^2 + ab + b^2) = c^{2022} + 42 = u_n.$$
Problem
Source: JBMO Shortlist 2022
Tags: number theory, Sequence, recursive, Junior, Balkan, shortlist
27.06.2023 01:25
Super silly question. We find that the characteristic equation of the recursion is $\lambda^2-6\lambda - 7 =0$ with roots $\lambda = -7$ and $\lambda=1$. This together with $u_0=0$ and $u_1=1$ gives \[ u_n = \frac{7^n-(-1)^n}{8}. \]Assume the contrary that such $a,b,c,n$ exists. If $n$ is odd then $7^n-(-1)^n\equiv 8\pmod{16}$, so $u_n$ is odd. This yields $a,b,a+b$ to be all odd, a contradiction. Hence, $n$ is even and we have \[ u_{2k} = \frac{7^{2k}-1}{8} = c^{2022}+42. \]Taking both sides modulo $7$, we get $u_{2k}\equiv -1\pmod{7}$, so $c^{2022}\equiv -1\pmod{7}$. But it is clear $-1$ is not a quadratic residue modulo 7, yielding a contradiction.
27.06.2023 01:35
We can get esily $u_n=\frac{7^n-(-1)^n}{8}$ so we have $8ab(a + b)(a^2 + ab + b^2) = 8(c^{2022} + 42 )= 7^n-(-1)^n$ Consider $mod7$ in $8(c^{2022} + 42 )= 7^n-(-1)^n$ we get $n=2m+1$ so we have: $8ab(a+b)(a^2+ab+b^2) = 7^{2m+1}+1= 8(c^{2022} + 42 )$ But from $mod16$ we have contradiction on the $8ab(a+b)(a^2+ab+b^2) = 7^{2m+1}+1$
01.07.2023 02:08
Mod $7$ and parity are enough, you do not even need to compute the sequence in closed form. (By the way, mod $11$ also works since $ab(a+b)(a^2+ab+b^2) = (a+b)^5 - a^5 - b^5$).
20.04.2024 18:40
More intuitive way for me that doesn't require any recursion: For the sake of contradiction, assume that these numbers do in fact exist. Let $S = ab(a+b)(a^2+ab+b^2) = c^{2022} + 42 = u_{n}$ Claim: $3 \vert S$ Proof: If $3 \vert ab$, we are done. Otherwise, if $3 \vert a + b$ we are also done, but if both of these conditions don't hold, it follows that $ a \equiv b \pmod{3} $. Then, $a^2 + ab + b^2 \equiv a^2 + a^2 + a^2 \equiv 0 \pmod{3}$, and in this case $3 \vert S$ too. $\blacksquare$ We can see that by induction $u_{n} \equiv u_{n \mod 2} \pmod{3}$. Hence, since $3 \vert S = u_{n}$, so it follows that $n$ is even. Note that $n$ is not equal to $0$ because $S > 0$. Claim: $S \equiv -1 \pmod{7}$ Proof: Since $u_{n} = 6u_{n-1} + 7u_{n-2}$, it follows that $u_{n} \equiv -u_{n-1} \pmod{7}$. Then $S = u_{n} \equiv -1 \pmod{7}$, because $n$ is even. From this it follows that $-1 \equiv S \equiv c^{2022} + 42 \equiv c^{2022} \equiv (c^{6})^{337} \pmod{7}$ which is a contradiction because of Fermat's little theorem.
10.11.2024 18:56
$u_n=\frac{7^n-(-1)^n}{8}$ taking $\bmod 7$ gives us that $c^{2022}$ is $-1(\bmod 7)$ but $-1$ is not a quadratic residue for $7$
09.01.2025 08:32
claim:$u_n=\frac{7^n-(-1)^n}{8}$ proof:from coef's we get $t^2-6t-7=0\implies t_1=7,t_2=-1\implies u_n=\frac{7^n-(-1)^n}{8}$ $8ab(a+b)(a^2+ab+b^2)=8(c^{2022}+42)=7^n-(-1)^n$ $\pmod{3}\implies n$ is even which is contradiction with $\pmod{7}$