# For $k>3$ does there exist an odd prime $q_k$ such that $p_k=2^kq_k+1$ is prime and $p_k$ divides $a_k=\dfrac{3^{2^{k-1}}+1}{2}$?

Question: For $k>3$ does there exist an odd prime $q_k$ such that $p_k=2^kq_k+1$ is prime and $p_k$ divides $a_k=\dfrac{3^{2^{k-1}}+1}{2}$?\

If $k=3$ the answer is Yes because for $q_3=5$ we get $p_3=a_3=41$. \

$a_4=3281=17\cdot 193$ but neither $17=2^4\cdot 1+1$ nor $193=2^4\cdot 12+1$ qualifies to be $p_4$ because $1$ and $12$ are not (odd) prime numbers.\

$a_5,a_6$ and $a_7$ turn out to be prime numbers, so, the answer to the question is No (see the recursive definition below). $a_8$ has $61$ digits and none of its factors qualifies to be $p_8$. Unfortunately $a_9$ has approximately $121$ digits and $a_{10}$ has approximately 243 digits. I would like to see a proof for the No answer for $k>3$ or see the condition on $k$ for which the answer is Yes.\

There is also a recursive definition for $a_k$ : $a_2=5,a_k=2^k(a_2\cdots a_{k-1})+1,k>2,$ which makes it very clear why $k=3$ is a Yes answer. ($a_1$ doesn't really matter but a meaningful definition for it is $a_1=2.$)

This isn't a complete answer, but a heuristic argument which seems to indicate that (as Christian Elsholtz suggests), there is no serious obstacle to there being infinitely many such triples. For ease of notation, I'll just write $p$ and $q$ for odd primes $p$ and $q$ such that $p = 2^{k}q+1$ and $p$ divides $\frac{3^{2^{k-1}}+1}{2}$, where $k >3.$ Notice that $3$ has multiplicative order $2^{k}$ in the multiplicative group $\left( \mathbb{Z}/p\mathbb{Z} \right)^{\times}.$ In particular, $3$ is a quadratic non-residue (mod $p$). Since $p \equiv 1$ (mod $4$), we must have $p \equiv 2$ (mod 3). If $k$ is even,we conclude that we have $p \equiv 2^{k}+1$ (mod $3.2^{k}$) while if $k$ is odd, we have $p \equiv 2^{k+1}+1$ (mod $3.2^{k}$). Hence when $k$ is even, we have $q \equiv 1$ (mod $3$) and when $k$ is odd, we have $q \equiv 2$ (mod $3$). Note also that $3^{q}$ is a quadratic non-residue (mod $p$) since $q$ is odd.

Hence one procedure for producing triples $(k,q,p)$ (which does produce all solutions) is as follows: Choose an integer $k > 3.$ Choose a prime $q \equiv 2^{k}$ (mod $3$). If $p = 2^{k}q + 1$ is also prime, check whether $3$ lies in the cyclic subgroup generated by $3^{q}$ in $\left( \mathbb{Z}/p\mathbb{Z} \right)^{\times}.$ If it does, then $(k,q,p)$ is a solution. If not, it isn't. The justification for the last step is that given that the previous criteria are satisfied, $3^{q}$ has multiplicative order exactly $2^{k}$ in $\left(\mathbb{Z}/p\mathbb{Z} \right)^{\times}$ so is a generator of the (cyclic) Sylow $2$-subgroup of the multiplicative group $\left(\mathbb{Z}/p\mathbb{Z} \right)^{\times}.$ On the other hand, if $(k,q,p)$ is a solution, then $3$ must have multiplicative order exactly $2^{k}$ in $\left(\mathbb{Z}/p\mathbb{Z} \right)^{\times}.$ Hence it must be a power (in the unique Sylow $2$-subgroup of that group) of the generator $3^{q}.$ In fact, if $3$ is a power of $3^{q}$ at all, it is necessarily a generator of that Sylow $2$-subgroup, since $3^{q}$ is already a generator.

• Thank you very much for the insight. It was very helpful. – Yusuf Gurtas May 22 '15 at 14:50

One can do higher $k$ without factoring these integers. A search for small factors finds:

$k=11$: $3^{2^{10}}+1$ is divisible by $59393=29 \cdot 2^{11} +1$.

$k=12$: $3^{2^{11}}+1$ is divisible by $790529= 193 \cdot 2^{12}+1$.

The table below gives many more such factors, in the format $\{k, p, q\}$.

$\{11, 59393, 29\}, \{12, 790529, 193\}, \{20, 13631489, 13\}, \{22, 155189249, 37\}, \{29, 12348030977, 23\}, \{45, 15586676835352577, 443\}, \{50, 7881299347898369, 7\}, \{55, 180143985094819841, 5\}, \{81, 26596368031521841843535873, 11\}, \{124, 3466626613007060596533128813211138654209, 163\}, \{127, 850705917302346158658436518579420528641, 5\}, \{140, 43207693822153082336725454153256200417837057, 31\},$ Now omitting the long integer $q$:

$\{267, 17\},\{320, 7\}, \{360, 367\}, \{371, 197\}, \{393, 281\}, \{711, 89\}, \{898, 499\}, \{1000, 13\}$.

I would thus expect that for infinitely many $k$ such prime factors exist.

Related, but not exactly your question, is Pepin' test for Fermat primes. http://en.wikipedia.org/wiki/P%C3%A9pin%27s_tes

• Thank you very much for your quick response. It was very helpful. – Yusuf Gurtas May 22 '15 at 14:49