[quote=R.D. Silverman;214540]Start by using what we have discussed so far to prove that
any factor of a^p+1, (other than (a+1)) is of the form 2kp+1.

Use the fact that if a^n = 1 mod N, then n divides phi(N). [We just
proved this!]


Then look at (2^(2^n) + 1). Deduce that any factor must be of the
form k(2^{n+1}) + 1. Now note that this number is 1 mod 8 for n
sufficiently large (ask yourself: how large)

Now ask: what do we know about a relationship between 2 and primes
that are 1 mod 8? Then apply a theorem of Euler concerning this
relationship.[/quote]

Every prime of the form 8k+1 have a quadratic residue class 2.

[QUOTE=blob100;214544]Every prime of the form 8k+1 have a quadratic residue class 2.[/QUOTE]

Yes!

Let p=2^(n+2)k+1.
By Euler's croterion we have p|2^(2^(n+1))-1
And we have: 2^(2^(n+1))-1=(2^(2^n)-1)(2^(2^n)+1).
So if the factors of 2^(2^(n+1))-1 are of the from 2^(n+2)k+1, then the factors of 2^(2^n)+1 are of the form 2^(n+2)k+1.

[QUOTE=blob100;214646]Let p=2^(n+2)k+1.
By Euler's croterion we have p|2^(2^(n+1))-1

And we have: 2^(2^(n+1))-1=(2^(2^n)-1)(2^(2^n)+1).
So if the factors of 2^(2^(n+1))-1 are of the from 2^(n+2)k+1, then the factors of 2^(2^n)+1 are of the form 2^(n+2)k+1.[/QUOTE]

No. And you have an incorrect application of Euler's Criterion.
If p = k * 2^(n+1) + 1, then we must have

2^{(p-1)/2} = 1 mod p. ==> 2^{k*2^(n+1)} - 1 is divisible by p.

But this is going in the wrong direction. Start simply by assuming that

2^2^n + 1 = 0 mod p, and p= 1 mod 8 and nothing more.

Let M be the multiplicative residue group of p.
We say the large of the group M is #M=p-1.
We say p-1=8x.
And a^2=2(mod p) for some a.

I think (and don't know how to explain):
The order of a^2-2 in M is 2^(n+2),
By lagrange's theorem, we have 2^(n+2)|#M=p-1
So p=2^(n+2)k+1.

I didin't have time to write everything explained and deffined, but I wanted to write it
now becuase I won't be able to use the computer in the next days.

[QUOTE=blob100;214774]Let M be the multiplicative residue group of p.
We say the large of the group M is #M=p-1.
We say p-1=8x.
And a^2=2(mod p) for some a.

I think (and don't know how to explain):
The order of a^2-2 in M is 2^(n+2),
By lagrange's theorem, we have 2^(n+2)|#M=p-1
So p=2^(n+2)k+1.

I didin't have time to write everything explained and deffined, but I wanted to write it
now becuase I won't be able to use the computer in the next days.[/QUOTE]

No. The entire problem is [b]REALLY[/b] much simpler than you are
making it.

The factor q of 2^2^n+1 is 1 mod 8. Therefore 2 is a quadratic residue.
Thus, by Euler's Criterion 2^{(q-1)/2} = 1 mod q. But the order of
an element must divide the order of the group.

Whereas for 2^p-1 = 0 mod q, we get that p divides q-1, Here we
have that p must divide (q-1)/2 because 2 is a quadratic residure.

I think you can finish from here.

[quote=R.D. Silverman;214801]

I think you can finish from here.[/quote]

I just cannot solve it.
Everything till now was with your hints, advises.
When a problem is given to me, I need to solve it by myself.
I can't, and it took too much time.
can you please show me the rest of the solvement?

Is this the direction?:
2^(q-1/2)=1(mod 2^p-1).

[QUOTE=blob100;214930]I just cannot solve it.
Everything till now was with your hints, advises.
When a problem is given to me, I need to solve it by myself.
I can't, and it took too much time.
can you please show me the rest of the solvement?
[/QUOTE]

No

[QUOTE]
Is this the direction?:
2^(q-1/2)=1(mod 2^p-1).[/QUOTE]

Would anyone else like to try?

The last step is trivial.

[quote=R.D. Silverman;214937]No



Would anyone else like to try?

The last step is trivial.[/quote]
What do you mean by "no"?
I guess your not going to show the solvement.

Maybe using this theorem?:
If we have:
a,b positive itegers,
We write:
2^a-1=A, 2^b-1=B.
If we have (a,b)=g
We have (A,B)=G
For 2^g-1=G.

:: 2^(q-1/2)=1(mod q)
And 2^p=1(mod q)
So 2^g=1(mod q)
Where g=((q-1)/2,p).
But the largest common devisor must be p becuase it is a prime.
So 2 is of order p modulo q.

[QUOTE=blob100;214938]What do you mean by "no"?
I guess your not going to show the solvement.

q.[/QUOTE]

The word "no" was in the wrong place. It should have followed the
next statement.

[quote=R.D. Silverman;214945]The word "no" was in the wrong place. It should have followed the
next statement.[/quote]
OK.