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!
Best Answer
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})$.