If $b$ is a divisor of $a^2 - a + 1$, can $a$ be a divisor of $b^2 - b + 1$ I observed that for $a > 1$, if $b$ is a divisor of $a^2 - a + 1$ then $a$ is not a divisor of $b^2 - b + 1$. This implies that their divisors are mutually exclusive. Is this true in general?
$$
b \mid a^2 - a + 1 \implies a \nmid b^2 - b + 1
$$
I have verified this for $a \le 10^9$.
 A: We restrict our attention to positive integers.
This is a Vieta jumping solution, where we use the existing solution set to find another solution set, and hope to reach the base case or find a contradiction.
We call $(a, b)$ a valid set if $ a \geq b > 0$, $a \mid b^2 - b + 1, b \mid a^2 - a + 1$, and $ a > 1$.
There is a solution $ (1,1)$, which isn't a valid set because $ a \not > 1 $.
We will show that there are no valid sets.
Proof by contradiction. Suppose we have a valid set. Let $ ac = b^2 - b + 1 $.
We will show that $(b, c)$ is also a valid set by checking that it satisfies the conditions.

*

*If $b = 1$, then $ a \mid b^2 - b + 1 = 1$ gives us $ a =1$, so $ b > 1$.

*$ b^2 - b + 1 = ac \equiv 0 \pmod {c}$.

*Since $ac = b^2 - b + 1 > 0$, hence $ c > 0$.

*Since $b^2 > b^2 -b + 1 = ac $, and $ a \geq b$, hence $ b > c $. (This is stronger than the $ b \geq c$ that we need, and we will use this subsequently.)

*$ ac \equiv 1 \pmod{b}$, so $ a^2(c^2 - c + 1 ) \equiv 1 - a + a^2 \equiv 0 \pmod{b}$. Dividing out by $a^2 $ (Since $ \gcd(a, b) = 1$) gives us $ c^2 - c + 1 \equiv 0 \pmod{b}$,

We can repeat the above process to get strictly smaller valid sets (Since $ b > c$).
Let this chain be $ a_1 = a, a_2 = b, a_3 = \frac{a_2^2 - a_2 + 1 } { a_1} , \ldots, a_{i+1} = \frac{ a_i ^ 2  - a_i + 1 }{ a_{i-1}} $. We have:

*

*$ a_i > a_{i+1} > a_{i+2} $

*$a_{i} a_{i+2} = a_{i+1}^2 - a_{i+1} + 1 $
However, there is no strictly decreasing chain of positive integers. Hence, we have a contradiction.

It's not immediately clear to me how to deal with the negative integers. Note that several of the inequalities need not be true.
We have the 3 chains

*

*$1, 1, 1, \ldots$

*$ 1, -1, 1, -1, \ldots $

*$ - 1, -1, -1, \ldots $
I'm not sure if there are other solutions.

