Conditions of solution

Question

Let $p=2^{2m+1}-2^{m+1}+1$ be a prime number, where $m\geq1$ is an integer. Under which conditions can we say that $(kp+1) \mid 2^{4m+2}$, where $k\geq 1$ is a positive integer?

Answer 1

As Gerhard says, $m=1$ works giving $p=5$ and $k=3$. I claim that this is the only time it happens.

Let $m\geq2$ be an integer, and set $p=2^{2m+1}-2^{m+1}+1$. I don't care if $p$ is prime or not, but note at this point that $p\geq25$ is odd.

Let's try and work out the multiplicative order of 2 mod $p$. Surprisingly (to me), this can be computed exactly (which is actually what motivated me to type this result in). Powers of $2$ from $2^1$ up to $2^{2m}$ are clearly in $[2,p-1]$, so the order of $2$ isn't in this range.

Next note that $2^{2m+1}=2^{m+1}-1$ mod $p$, again in $[2,p-1]$, as are $2^{2m+2},\ldots,2^{3m}=2^{2m}-2^{m-1}$ (all equalities are congruences mod $p$ here, I'm working mod $p$).

This doesn't look like it's going anywhere, but let's press on. We have $2^{3m+1}=2^{2m+1}-2^m$ which is congruent to $2^{m+1}-2^m-1=2^m-1$. If $m$ were $1$ then this would be $1$, but I've assumed $m\geq2$ so again this is in the range $[2,p-1]$. Let's press on!

We have $2^{3m+2}$, $2^{3m+3}$ etc all in $[2,p-1]$, up to $2^{4m+1}=2^{2m}-2^m$. Next we have $2^{4m+2}$ and this equals $2^{2m+1}-2^{m+1}=-1$ mod $p$. Hence $2^{4m+2}$ is congruent to $-1$ mod $p$ and the order of $2$ mod $p$ is at least $4m+3$ (because I have explicitly verified that $2^d$ is not $1$ mod $p$ for $1\leq d\leq 4m+2$). But on the other hand it also must divide $8m+4$ because $(-1)^2=1$ mod $p$, and the only divisor of $8m+4$ strictly greater than half of $8m+4$ is $8m+4$.

We conclude that for $m\geq2$ there is no solution to $2^t$ congruent to $1$ mod $p$ with $t\leq 4m+2$ and this is just another way of saying that no $k$ exists.

I must say I'm slightly surprised that one can compute the exact order of $2$ mod $p$ here. Maybe I've seen some similar trick with Mersenne primes once before (maybe in the algorithm they use to check if a large Mersenne number is prime?)

Note finally that if $x=2^m$ then $p=2x^2-2x+1$, so $4x^4+1=(2x^2-2x+1)(2x^2+2x+1)$ is a multiple of $p$ and hence $4x^4$ is congruent to $-1$ mod $p$, which is a simpler proof that $2^{4m+2}$ is $-1$ mod $p$, but all we can deduce from this simpler argument is that the order of $2$ mod $p$ is $4$ times an odd divisor of $2m+1$; as far as I can see one has to go through the above rigmarole to compute the true order.