Let a be a fixed positive integer and (en) the sequence, which is defined by e0=1 and en=a+n−1∏k=0ekfor n≥1. Prove that (a) There exist infinitely many prime numbers that divide one element of the sequence. (b) There exists one prime number that does not divide an element of the sequence. (Theresia Eisenkölbl)
Problem
Source: 2020 Austrian National Competition for Advanced Students, Part 2 problem 3
Tags: number theory, prime numbers, Sequence, Austria
18.07.2020 18:08
18.07.2020 20:02
Actually, part (a) is also easy to prove without the assumption e_0=1 (although the argument in #2 does not quite work then). But what about part (b)? Is it also true for general (positive) initial values?
19.07.2020 05:42
To address Tintarn: I think one can show (b) for any general initial condition. Here is my argument. Note that e_n-a=e_{n-1}(e_{n-1}-a), thus e_n=e_{n-1}^2-ae_{n-1}+a for n\ge 2. Now, if a prime p and n are such that p\mid e_n (n\ge 2) then p\mid x^2-ax+a for a suitable x, namely p\mid (2x-a)^2-a^2+4a. That is, a^2-4a is a quadratic residue, modulo p. Now, unless a=4, a^2-4a is not a square, and in this case there exists a prime q (in fact infinitely many) for which a^2-4a is a non-residue, thus for any such prime q, q cannot divide any term of the sequence provided q\nmid e_0 and q\nmid e_1=a+1. For a=4, we have e_n = (e_{n-1}-2)^2 for n\ge 2. If p\mid e_n for a suitable n then e_{n-1}\equiv 2\pmod{p}, but as e_{n-1} is a square as well, it follows 2 is a quadratic residue modulo p. There are infinitely many primes p for which 2 is quadratic non-residue (take p\equiv \pm 3\pmod{8}), which also shows no matter what the initialization is, (b) always holds.
16.08.2020 12:14
I have just realised that I forgot to post my solution for part (a).
16.08.2020 21:18
Part a) Suppose only finetely many primes devides some element of the set A=\{e_n|n\ge 0\}.Then only finitelty many primes devide some of the element of set B=\{a_n| a_n=e_0e_1\dots e_n\}.By Kobayashi's theorem there are infinitely many primes devide some of the elements of B+a=\{a_n+a|a_n=e_0e_1\dots e_n\}=B-\{1\}.But it is a contradiction of our initial assumption that the set B has only finitely many primes dividing some elements of B. Hence we are done.\blacksquare For part (b)If a\neq 1 then as e_n\equiv 1\pmod {a} Taking a prime p deviding a we get gcd(e_n,p)= gcd(1,p)=1. If a=1 then as e_n=1+e_0e_1\dots e_{n-1}=1+e_{n-1}(e_{n-1}-1) hence 5 doesn't devide any of e_n as 5 does not devide x^2-x+1.\blacksquare
26.07.2024 16:04
Claim: All terms of the sequence are relatively prime to a. Proof: This is by induction with base case 0. If it is true for everything up to n - 1, then \prod_{k=0}^{n-1} e_k is relatively prime to a, so e_n = a + \prod_{k=0}^{n-1} e_k must also be relatively prime to a. a) If not, then some prime number must divide infinitely many elements of the sequence. Suppose it's p and it divides e_x and e_y for some x < y. Notice that e_y = a + \text{ a multiple of } e_x, so e_y \equiv a\pmod{e_x}, implying that p\mid a, contradiction since \gcd(e_x, a) = 1. b) If a\ne 1, just take any prime divisor of a. Now assume a = 1. We claim that 5 doesn't divide any element of the sequence. Notice that e_n = e_{n-1}^2 - e_{n-1} + 1, but 5 can't divide this.