We define a sequence of positive integers $a_1,a_2,a_3,\dots$ as follows: Let $a_1=1$ and iteratively, for $k =2,3,\dots$ let $a_k$ be the largest prime factor of $1+a_1a_2\cdots a_{k-1}$. Show that the number $11$ is not an element of this sequence.
Problem
Source: Germany 2018, Problem 5
Tags: number theory, Sequence, Prime factor, primes
17.06.2018 11:22
Note that $a_2=2,a_3=3,a_4=7$.so if for some $k,a_k=11$,then $a_1 \dots a_{k-1} +1=5^a 11^b$. taking modulo 3 and 4 gives that $a,b$ are both odd.Looking modulo 7: $$5^{2n+1} \equiv 5,-1,3 \mod 7 ; 11^{2n+1} \equiv 4^{2n+1} \equiv 1,2,4 \mod 7$$We should have $5^{2n+1} 11^{2m+1} \equiv 1 \mod 7$ which is impossible. so such a $k$ does not exist.
17.05.2023 15:33
Cleary, if a prime number appears once, it can appear never again, since $a_k\nmid 1+a_1\cdot\ldots\cdot a_k\cdot\ldots$. Claim: 5 never appears in that sequence. Proof. Ftsoc, say $a_k=5$ for some $k$. Then $p\nmid S=1+a_1\cdot a_2\cdot\ldots\cdot a_{k-1}$ for any prime $p>5$ and also $2,3\nmid S$, as they are the 2nd and 3rd term of the sequence. Hence we must have $S=5^n$ for some $n\ge 1$ and thus $5^n-1=a_1\cdot a_2\cdot a_{k-1}$. But this is a contradiction, as the left side is divisible by $4$, while the right isn't. \square Similarly, if $a_k=11$ is part of that sequence, then $11^n-1=a_1\cdot\ldots\cdot a_k$. Now the left side is divisble by 10, but the right isn't, as $5$ is not part of the sequence.