The natural number n is said to be good if there are natural numbers a and b that satisfy a+b=n and ab|n2+n+1. (a) Show that there are infinitely many good numbers. (b) Show that if n is a good number, then 7∤.
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?