3
$\begingroup$

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.$)

$\endgroup$
2
$\begingroup$

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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.