Proof by contradiction:
[B]Proposition:[/B]
If (a,m)=1 and a is of order e modulo m, then if
a^d=1(mod m)
we have e|d.

[B]Theorem:[/B]
If x,y and a are positive integers we write:
a^x-1=X and a^y-1=Y.
Then if (x,y)=g,
we have (X,Y)=G
where G=a^g-1.

For the proposition:
We have m|D=a^d-1 and m|E=a^e-1,
Then (D,E)=G
Where G=a^g-1
Where g=(e,d) (positive integer).
So, becuase we have m|D and m|E, we have m|G.
Reason: G is the largest common devisor of E and D, and m is a common devisor.

Now, let's assume e isn't a devisor of d.
We can express a^d-1 as a^gn-1
For specified n positive integer.
And express a^e-1 as a^gk-1
For specified k positive integer.
We have a common devisor of E and D which is m.
Becuase e isn't a devisor of d, we agree g=\=e and g<e.
But if g<e then m|a^g-1 which doesn't suttisfy the definition of e.
So we must agree g=e a^d-1=a^en-1. d=en.

[QUOTE=blob100;213898]Proof by contradiction:
[B]Proposition:[/B]
If (a,m)=1 and a is of order e modulo m, then if
a^d=1(mod m)
we have e|d.

[B]Theorem:[/B]
If x,y and a are positive integers we write:
a^x-1=X and a^y-1=Y.
Then if (x,y)=g,
we have (X,Y)=G
where G=a^g-1.

For the proposition:
We have m|D=a^d-1 and m|E=a^e-1,
Then (D,E)=G
Where G=a^g-1
Where g=(e,d) (positive integer).
So, becuase we have m|D and m|E, we have m|G.
Reason: G is the largest common devisor of E and D, and m is a common devisor.

Now, let's assume e isn't a devisor of d.
We can express a^d-1 as a^gn-1
For specified n positive integer.
And express a^e-1 as a^gk-1
For specified k positive integer.
We have a common devisor of E and D which is m.
Becuase e isn't a devisor of d, we agree g=\=e and g<e.
But if g<e then m|a^g-1 which doesn't suttisfy the definition of e.
So we must agree g=e a^d-1=a^en-1. d=en.[/QUOTE]

Much better. But a [b]much[/b] simpler proof is available.

Give: a^d = a^e = 1 mod m . Assume e does not divide d.
therefore d = k*e + alpha for some k and for alpha < e.
But now we have by direct substitution a^(k*e + alpha) = 1 mod m.
Whence a^(ke) * a^alpha = 1 mod m.
But a^(k*e) = 1 mod m because a^e = 1 mod m. Thus, a^alpha = 1 mod m, in contradiction to the assumption that e is the smallest such
integer. QED

[QUOTE=R.D. Silverman;213900]Much better. But a [b]much[/b] simpler proof is available.

Give: a^d = a^e = 1 mod m . Assume e does not divide d.
therefore d = k*e + alpha for some k and for alpha < e.
But now we have by direct substitution a^(k*e + alpha) = 1 mod m.
Whence a^(ke) * a^alpha = 1 mod m.
But a^(k*e) = 1 mod m because a^e = 1 mod m. Thus, a^alpha = 1 mod m, in contradiction to the assumption that e is the smallest such
integer. QED[/QUOTE]

Now use this result to show that if 2^p+1 is divisible by q, then q = 2kp+1
for some k.

[quote=R.D. Silverman;213901]Now use this result to show that if 2^p+1 is divisible by q, then q = 2kp+1
for some k.[/quote]
Proof:
[B]Proposition:[/B]
If 2^p-1 is divisible by q then q=2kp+1.
For some k.

[B]Theorem:[/B]
2^(q-1)=1(md q).

We have 2^p=1(mod q).
We agree q-1 or p is must be devisor of the other one.
So: q-1=sp or p=s(q-1) for some s.
But p=\=s(q-1) becuase there is [B]no such[/B] s(q-1) prime number, and q-1 is [B]even[/B] so s(q-1) must be even (we remember that 2^n-1 is not devided by even numbers).
So q=sp+1.
If s is odd then sp+1 is even, so q won't be a prime number.
So we have q=2kp+1.

[QUOTE=blob100;214004]Proof:
[B]Proposition:[/B]
If 2^p-1 is divisible by q then q=2kp+1.
For some k.

[B]Theorem:[/B]
2^(q-1)=1(md q).

We have 2^p=1(mod q).
We agree q-1 or p is must be devisor of the other one.
So: q-1=sp or p=s(q-1) for some s.
But p=\=s(q-1) becuase there is [B]no such[/B] s(q-1) prime number, and q-1 is [B]even[/B] so s(q-1) must be even (we remember that 2^n-1 is not devided by even numbers).
So q=sp+1.
If s is odd then sp+1 is even, so q won't be a prime number.
So we have q=2kp+1.[/QUOTE]

This good, but is better expressed as:

2^p = 1 mod q
Hence p must divide q-1 (byt the result we just proved)
Hence q-1 = kp ==> q = kp+1
k must be even and we get q = 2k'p + 1.

Now, apply this result to 2^2^n + 1 AND also use the facts that
2 is the base and and any divisor must be 1 mod 8 for n >= 2.

[quote=R.D. Silverman;214015]This good, but is better expressed as:

2^p = 1 mod q
Hence p must divide q-1 (byt the result we just proved)
Hence q-1 = kp ==> q = kp+1
k must be even and we get q = 2k'p + 1.

Now, apply this result to 2^2^n + 1 AND also use the facts that
2 is the base and and any divisor must be 1 mod 8 for n >= 2.[/quote]
I have a question:
Am I needed to use the group theory here (lagrange's theorem)?

[QUOTE=blob100;214040]I have a question:
Am I needed to use the group theory here (lagrange's theorem)?[/QUOTE]

If one considers the set of (non-zero) integers modulo a prime, it forms
a group under multiplication. So the results we have just proved are
results from group theory, even though they are not expressed in terms
of the language of groups. --> The order of an element divides the
order of the group. This is a corrolary of Lagrange's Theorem (which states
that the size of a sub-group divides the size of the group).

Thus, a^(p-1) = 1 mod p is a theorem of group theory.
a^e = 1 mod p --> e divides (p-1) is a theorem of group theory.

The group is the set of units modulo a prime.

[quote=R.D. Silverman;214053]If one considers the set of (non-zero) integers modulo a prime, it forms
a group under multiplication. So the results we have just proved are
results from group theory, even though they are not expressed in terms
of the language of groups. --> The order of an element divides the
order of the group. This is a corrolary of Lagrange's Theorem (which states
that the size of a sub-group divides the size of the group).

Thus, a^(p-1) = 1 mod p is a theorem of group theory.
a^e = 1 mod p --> e divides (p-1) is a theorem of group theory.

The group is the set of units modulo a prime.[/quote]

I deffinietly don't know how to solve this problem.

[quote=R.D. Silverman;213498]Shall we tackle problem 2?

Start with:

Let p be prime. any prime factor q of 2^p+1 is of the form q = 2kp+1.

Do you know how to show this? If 2^p+1 = 0 mod q, then 2^p = -1 mod q,
whence 2^(2p) = 1 mod q. Do you know any theorems about the order
of an element modulo a prime? Shanks' book will have discussed this.

Now, for 2^2^n + 1, it is easily seen that any factor must be of the form

2k(2^n) +1) by result above. We want to show that the factor must be of
the form 2k(2^(n+1) ) + 1. We know that this prime is 1 mod 8.
Now ask yourself: what relation is known between the prime 2, and primes
that are 1 mod 8? Now consider a certain result due to Euler.[/quote]

Why does the factor is of the form 2k(2^n) +1) by the result above,
I tought any factor of 2^n-1 is of the form 2kn+1 just if n is a prime number.
Primes that are 1 mod 8, are always of the form 2^(n+2)k+1.

We see that (1+2^(2^(n-1)))^2=2^(1+(2^(n-1)))(mod p).
We say: 2^(1+(2^(n-1))) is a quaratic residue of p.
1+2^(n-1)=2m+1.
2 Is a quadratic residue of p becuase an odd power of 2 is a qaudratic residue of p.
So we have a^2=2(mod p) for some integer a.

[QUOTE=blob100;214537]Why does the factor is of the form 2k(2^n) +1) by the result above,
I tought any factor of 2^n-1 is of the form 2kn+1 just if n is a prime number.
Primes that are 1 mod 8, are always of the form 2^(n+2)k+1.[/QUOTE]

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.