Problems & Puzzles: Puzzles

Puzzle 1129 OEIS A137990 Alain Rochelli sent on Jan 23, 2023 the following puzzle Related to A137990, "a(n) is the least prime p of the form c*3^n+1 with c not divisible by 3" (n>=0). Q1 : Can you verify by computation that a(n) is also the least prime such that 3^(n+1), but not 3^(n+2), divides 2^(a(n)-1)-1 ? Q2 : Can you get an explanation (proof) of this? Among other things, use recursive reasoning. Are there more primes of this form?

---

From April 29 to May 5, contributions came from Emmanuel Vantieghem, Adam Stinchcombe and  Oscar Volpatti

***

 Emmanuel wrote:

***

Adam wrote:

You can prove this using the binomial theorem, by expanding 2^(an-1) = (3-1)^(c*3^n) = sum( (c*3^n  C  k * (-1)^(c*3^n-k)*(3)^k, k=0 to c*3^n).  Ignore the +1/-1 term which doesn't influence divisibility.  The first term is 1 which gets subtracted off in 2^(an-1)-1.  The next term is c*3^n/1*3^1 which is divisible by 3^(n+1) because c is rel prime to 3.  The next term is (c*3^n)(c*3^n-1)/(1*2)*3^2 which is divisible by 3^(n+2).  The next term shows you need to be careful because you get a 3 in the denominator, (c*3^n)(c*3^n-1)(c*3^n-2/(1*2*3)*3^3, divisible by 3^(n+2).  Et cetera.   You have to worry about the factors of 3 that show up in the denominator k! versus the numerator 3^k.  How many factors of 3 in (k!)?  Sum(floor(k/3^t,t=1..infinity)) which is smaller than Sum(k/3^t,t=1..infinity) which is a geometric series that converges to (k/3)/(1-1/3) =k/2.  You pick up n factors of 3 in 3^n, you pick up k factors of 3 in 3^k, and you lose at most k/2 in the denominator.  You inspect small k (above) and then the rest of the terms have >=n+2 factors of 3 as k gets big.

***

Oscar wrote:

About puzzle 1129, Alan Rochelli was right, but only for n>0.

Let's explicitly define his new sequence b(n), with n>=0: 

b(n) is the least prime such that 3^(n+1), but not 3^(n+2), divides 2^(b(n)-1)-1.

It is possible to prove that b(n) is also the least ODD prime of the form c*3^n+1 with c not divisible by 3.

 

The proof uses a known theorem:
 

if g is a primitive root modulo prime p, and if g^(p-1) is not congruent to 1 modulo p^2, then g is also a primitive root modulo all powers p^k.

Number g=2 is a primitive root modulo prime p=3;
 

congruence relation  2^2 == 4 != 1 mod 9   holds too;

therefore 2 is also a primitive root modulo all powers 3^k.

In other words, power 3^k divides Mersenne number M(x) = 2^x-1 if and only if x itself is divisible by Phi(3^k) = 2*3^(k-1).

 

Let's go back to sequence b(n).

3^(n+1) divides 2^(b(n)-1)-1, so 2*3^n divides b(n)-1;

3^(n+2) doesn't divide 2^(b(n)-1)-1, so 2*3^(n+1) doesn't divide b(n)-1;

therefore b(n)-1 = d*2*3^n, with d not divisible by 3.

It must be d = 3*q+1 or d = 3*q+2, so that b(n) has one of the following forms:

(6*3^n)*q+(2*3^n+1),

(6*3^n)*q+(4*3^n+1).

In both cases we have a linear polynomial which produces primes for infinitely many values of variable q, by Dirichlet's theorem on arithmetic progressions.

 

Let's compare Alan Rochelli's sequence with OEIS A137990:

prime b(n) is of the form c*3^n+1 with c = 2*d, so that b(n) is forced to be odd.
 

But, for n>0, a(n) is forced to be an odd prime too, because it must be greater than prime 2:

a(n) >= 1*3^n+1 > 1*3^0+1 = 2.

Therefore identity a(n) = b(n) always holds for n>0.

But it doesn't hold for n = 0, because a(0) = 2 while b(0) = 3.

 

***