The natural number $n$ is said to be good if there are natural numbers $a$ and $b$ that satisfy $a + b = n$ and $ab | n^2 + n + 1$. (a) Show that there are infinitely many good numbers. (b) Show that if $n$ is a good number, then $7 \nmid n$.
Problem
Source: INAMO Shortlist 2015 N8
Tags: number theory, Diophantine Equations, infinitely many solutions, Indonesia
15.05.2019 01:31
(a) Note that, if $d=(a,b)$ then since $d\mid n$, we obtain that $d\mid 1$. Thus, $a$ and $b$ are coprime. Now, $ab\mid n^2+n+1 \iff a\mid n^2+n+1$ and $b\mid n^2+n+1$. Next, $n^2+n+1= a^2+2ab+b^2+a+b+1$. Hence, the condition we have is $a\mid b^2+b+1$ and $b\mid a^2+a+1$. Thus, it suffices to show there exists infinitely many $(a,b)$ pairs with this property, which can be proven by a standard Vieta jumping argument.
16.05.2019 04:04
Here is a sketch for (b). The Vieta jumping argument described above shows that all solutions $(a, b)$ are generated from $(1, 1).$ This gives that the first few solutions are $(1, 1), (3, 1), (13, 3), (61, 13), (291, 61).$ It's easy to show by induction that the sequence $\{a_i\}$ given by $1, 3, 13, 61, 291, \cdots$ is generated by the recurrence relation $a_{n+3} = 6a_{n+2} - 6a_{n+1} + a_n.$ Taking this relation modulo $7$, we can rearrange it into $a_{n+3} + a_{n+2} \equiv a_{n+1} + a_n$. Therefore, we know that $a_n + a_{n+1}$ is always either equivalent mod $7$ to $a_0 + a_1 = 4$ or $a_1 + a_2 = 16$ modulo $7$, neither of which is a multiple of $7$. We are now done.
16.05.2019 06:25
@above one can also just note that the vieta jumping process implies $\frac{n^2 + n + 1}{ab}$ is constant, and for $(1, 1)$ it is $7$, hence $7 \mid n^2 + n + 1 \implies 7 \nmid n$.
02.05.2024 17:57
By Vieta Jumping we claim that $n^2 + n + 1 = 7ab$
24.08.2024 07:37
excuse me, but can you explain the steps of the vieta jumping?