Question continued: Hint: Consider $ord_{q}(2)$. Similarly, prove that if $r$ is a prime factor of $2^{2^{k}}+ 1 $ then $r\equiv1 (\mod \space 2^{k+1})$

I think I have the first part, however I didn't really make use of the hint, so I would greatly appreciate if someone could give me some direction if my proof is not valid. I am also a little stuck on the 2nd part of the question, so if someone could give me some direction, it would be greatly appreciated!

Here is my answer to the first part:

We have that $2^{p}\equiv1 (\mod \space q)$ and since $q$ is prime and $q\nmid 2$,

by FLT, $2^{q-1}\equiv1 (\mod \space q)$

Then by euclidean algorithm, we have that $d = ap + b(q-1) $ for some integers $a,b$

$\implies 2^{d}\equiv1(\mod \space q)$

If we assume $p ,(q-1)$ are not multiples of each other, then $d = ap + b(q-1) = 1$ (since $q$ is prime and $q\nmid 2$ and $p$ is prime)

$\implies 2\equiv 1 (\mod \space q)$, which is a contradiction.

So $p\mid (q-1) \implies q\equiv1(\mod \space p) $

Is this proof correct? I have not used the hint, but how would I go about doing that?

I wanted to use the same strategy with the 2nd part of the question, and I have that:

$2^{2^{k}}\equiv-1 (\mod \space r)$, and similarly by FLT, since $r$ is prime and $r\nmid 2$,

$2^{r-1}\equiv1(\mod \space r)$

But I am not sure how to proceed after that. The $-1$ throws me off a bit. Any direction would be greatly appreciated!!

Thanks in advance!

  • 1
    $\begingroup$ You have used the hint, when you apply FLT to powers of $2$ modulo $q$. $\endgroup$ Aug 17, 2013 at 12:01
  • $\begingroup$ To the question in your first paragraph (is that what you call the second part?) you can look at this question. $\endgroup$ Aug 17, 2013 at 12:30

1 Answer 1


Firstly $r\ne 2$.

You have that $2^{2^{k}}\equiv-1(mod~r)$.

Now square both sides and we have that $2^{2^{k+1}}\equiv 1 (mod~r)$

Hence if $ord_r(2)$ is the order of $2$ wrt $r$ , then it divides $2^{k+1}$ and does not divide $2^k$. Therefore $ord_r(2)=2^{k+1}$ and $ord_r(2)|r-1$ which gives us that $r\equiv 1 (mod~2^{k+1})$.

  • $\begingroup$ hi, thanks very much for your answer. It is helpful. The only part I don't really understand is when you say $ord_r(2)$ divides $2^{k+1}$ but not $2^k$. My understanding is that, $ord_r(2)$ is the number $j$ such that $2^{j}\equiv1(mod \space r)$. I'm having trouble connecting how $j$ divides $2^{k+1}$. Thanks again. $\endgroup$ Aug 17, 2013 at 12:44
  • 1
    $\begingroup$ @mathstudent: $ord_r(2)$ is the smallest positive integer $j$ with the property that $2^j\equiv1\pmod r$. A basic property (follows from a study of cyclic groups) is that all integers $j$ with that property are multiples of the smallest. $\endgroup$ Aug 17, 2013 at 17:21
  • $\begingroup$ @JyrkiLahtonen - Thanks, i'm still not really understanding. If I can use an example to help me understand, let's say we evaluate the of $ord_{41}(2)$ which is $20$. This implies that $2^{20}\equiv1 (mod\space 41)$. So how does $20|2^{k+1}$? What is $k$?. Thanks so much. $\endgroup$ Aug 17, 2013 at 23:48
  • $\begingroup$ @mathstudent: There is no such $k$. So this means that $41$ cannot be a factor of any number of the form $2^{2^k}+1$. $\endgroup$ Aug 18, 2013 at 5:08
  • 1
    $\begingroup$ @mathstudent: The logic goes as follows. We assume that a prime $r$ is a factor of $2^{2^k}+1$. Because $2^{2^{k+1}}\equiv1$, we see that $ord_r(2)$ is a factor of $2^{k+1}$. Because $2^{2^k}\not\equiv1$, $ord_r(2)$ is not a factor of $2^k$. Therefore $ord_r(2)=2^{k+1}$. But $ord_r(2)$ is also always a factor of $r-1$, so... $\endgroup$ Aug 19, 2013 at 4:59

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.