# Are there infinitely many primes which are factors of no terms in the sequence $a_0 = 4$, $a_{n}=$ $a_{n-1}^{2}-a_{n-1}$?

Problem statement:

Let $$a_{0}=4$$ and define a sequence of terms using the formula $$a_{n}=$$ $$a_{n-1}^{2}-a_{n-1}$$ for each positive integer $$n$$

a) Prove that there are infinitely many prime numbers which are factors of at least one term in the sequence;

b) Are there infinitely many prime numbers which are factors of no term in the sequence?

My attempted proof is as follows:

a) Write $$a_n = a_{n-1} (a_{n-1} - 1)$$. If a prime $$p$$ divides $$a_{n-1}$$ then $$p$$ cannot divide $$a_{n-1} - 1$$, else $$p$$ would divide their difference, $$1$$. So there must exist another prime $$p_1 \ne p$$ such that $$p_1 \mid (a_{n-1} - 1)$$ which implies $$p_1 \mid a_n$$. Similarly, since $$p$$ and $$p_1$$ both divide $$a_n$$, neither can divide $$a_n - 1$$, so $$\exists p_2 \ne p,p_1$$ such that $$p_2 \mid a_{n+1}$$. Continuing in this way we generate an infinite sequence of distinct primes $$(p_k)_k$$ where $$p_k \mid a_{n+k-1}$$.

b) I noticed that if $$a_N \cong 2 \pmod p$$ for some $$N$$, then $$a_n \cong 2 \pmod p$$ for all $$n \ge N$$ by the recurrence relation, since $$2\times(2-1) = 2$$. Clearly such a prime cannot be a divisor of any term in the sequence, for if it were, each term in the sequence thereafter would be congruent to $$0 \pmod p$$. It thus suffices to find infinitely many primes $$p$$ such that $$a_n \cong 2 \pmod p$$ for at least one term in the sequence. If we define a new sequence $$b_n = a_n - 2$$ then this is equivalent to finding infinitely many primes $$p$$ which are factors of at least one term in the sequence $$(b_n)_n$$. This suggests that we could perhaps proceed with a similar argument to that made in part a). The new recurrence relation becomes $$b_n + 2 = (b_{n-1} + 2) (b_{n-1} + 1)$$, or simplifying: $$b_n = b_{n-1}(b_{n-1} + 3)$$. The argument should now be almost identical to that in part a), with the observation that $$p \ne 3$$ becomes the sequence $$(b_n)_n$$ modulo $$3$$ is $$2, 1, 1, 1, \ldots$$.

Is this argument correct? I would be interested in seeing other solutions too, in any case.

• Just on an initial reading, your arguement looks good. Dec 28, 2020 at 5:55
• Conjecture: $a_n\equiv 2\bmod 10$ for any $n\ge 1$ Dec 28, 2020 at 17:04
• Proof of the conjecture above. By induction. $a_0=12\equiv 2\bmod 10$. We have to prove that if $a_n\equiv 2\bmod 10$ then $a_{n+1}\equiv 2\bmod 10$. Indeed $a_{n+1}=a_n^2-a_n$. For the inductive hypothesis $a_n=10k+2$, therefore $a_{n+1}=(10k+2)^2-(10k+2)=100 k^2+30 k+2=10(10k^2+3k)+2$ then $a_{n+1}\equiv 2\bmod 10$. Proved. Dec 28, 2020 at 17:19

the numbers in the sequence are divisible by $$2$$ and $$3$$ but are not divisible by any larger prime $$q$$ with Legendre symbol $$(q,5) = -1.$$

For $$j\ge1$$ We have a sequence $$t_j = 1, 5, 65, 8645, ...$$ which is $$t_{j+1} = t_j (2 t_j + 3)$$ Your sequence numbers are $$a_j =4 t^2 + 6 t + 2$$ and the new multipliers are $$a_{j+1}/a_j = a_j-1 = 4 t^2 + 6t + 1 = (3t+1)^2 - 5 t^2$$ As this $$a_j - 1$$ is primitively represented by $$x^2 - 5 y^2,$$ it cannot be divisible by any prime $$q$$ where $$q \equiv 2,3 \pmod 5$$. Thereby no prime factors $$\equiv 2,3\bmod 5$$ divide any $$a_j$$ except the factors $$2$$ and $$3$$ of $$a_1=12$$.

The first few such multipliers'' $$a_{j+1}/ a_j$$ are $$11$$ $$131$$ $$17291$$ $$298995971$$ $$89398590973228811 = 8779 \cdot 10079 \cdot 1010341471$$ $$7992108067998667938125889533702531 = 29 \cdot 59 \cdot 241 \cdot 2511683491 \cdot 7716660340023314591$$ $$63873791370569400659097694858350356285036046451665934814399129508491 = 109 \cdot 2309 \cdot 1307641 \cdot 1312951 \cdot 4627751 \cdot 19075520521 \cdot 1674514206139655462590242193707851$$

Notice how each prime factor $$p$$ has last (decimal) digit $$1$$ or $$9$$, and are thereby $$p \equiv\pm 1 \pmod{10}$$ so $$p \equiv\pm 1 \pmod{5}$$

Thus no prime $$q > 3$$ appears as a factor when $$q \equiv\pm 3 \pmod{5},$$ that is $$q \equiv\pm 3 \pmod{10},$$ so that the last decimal digit of this $$q$$ is $$3$$ or $$7.$$ These ratios are not divisible by $$7, 13, 17, 23, 37, 43, 47...$$

• Please check my edit. I am finding that your $t$ sequence starts at $j=1$ not $j=0$, so the bar on additional prime factors $\in \{q: (q|5)=-1\}$ applies only after $a_1=12$. Dec 28, 2020 at 13:09
• @OscarLanzi thanks. I did not check for index consistency for my $t$ and the original $a$ Dec 28, 2020 at 15:42