Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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

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

share|improve this answer
    
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
1  
@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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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