Challenge 11: Sequence of Primes

[Office_Shredder]

Consider the following sequence:
a₁ = p, where p is a prime number.
a_n+1 = 2a_n+1

Prove there is no value of p for which every a_n is a prime number, or make me look dumb and construct a counterexample.

 

[Citan Uzuki]

First, it follows easily by induction on n that for each n, $a_n = 2^{n-1}(p+1) - 1$. By Euler's theorem $2^{p-1} \equiv 1 \mod p$, and so $a_p = 2^{p-1}(p+1) - 1 \equiv p+1 - 1 \equiv 0 \mod p$, so $p \vert a_p$, but $p \neq a_p$, so $a_p$ is not prime. Q.E.D.

 

[Boorglar]

This works except when p = 2 because Euler's Theorem applies only when p is relatively prime with 2. But for that case, I checked and $a_6$ = 95 is composite.

 

[Citan Uzuki]

Ah yes, good catch. Thanks for patching that hole.

 

[Office_Shredder]

You can check p=2 a bit easier because a₂ = 5 and you can just apply the odd case starting from there. Nice solution Citan! Are there any other ways of solving it?

 

[johnqwertyful]

An extension. How often are the sequences prime until the pth term?
For example 3, 7, 15 is prime until term 3. 5, 11, 23, 47, 95 is prime until the term 5.
But 7 isn't prime until term 7.