# Let $p$ be a prime and $q$ a prime divisor of $2^{p} -1$. Use Fermat's Little Theorem to prove that $q\equiv 1 (\mod \space p)$

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!!

-
You have used the hint, when you apply FLT to powers of $2$ modulo $q$. –  Kevin Carlson Aug 17 '13 at 12:01
To the question in your first paragraph (is that what you call the second part?) you can look at this question. –  Jyrki Lahtonen Aug 17 '13 at 12:30

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

-
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. –  JackReacher Aug 17 '13 at 12:44
@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. –  Jyrki Lahtonen Aug 17 '13 at 17:21
@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. –  JackReacher Aug 17 '13 at 23:48
@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$. –  Jyrki Lahtonen Aug 18 '13 at 5:08
@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... –  Jyrki Lahtonen Aug 19 '13 at 4:59