3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Just on an initial reading, your arguement looks good. $\endgroup$
    – QC_QAOA
    Dec 28, 2020 at 5:55
  • $\begingroup$ Conjecture: $a_n\equiv 2\bmod 10$ for any $n\ge 1$ $\endgroup$
    – Raffaele
    Dec 28, 2020 at 17:04
  • $\begingroup$ 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. $\endgroup$
    – Raffaele
    Dec 28, 2020 at 17:19

1 Answer 1

1
$\begingroup$

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...$

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Dec 28, 2020 at 13:09
  • $\begingroup$ @OscarLanzi thanks. I did not check for index consistency for my $t$ and the original $a$ $\endgroup$
    – Will Jagy
    Dec 28, 2020 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.