[quote=R.D. Silverman;213619]

Start by proving the following:

Let d = phi(m). If a^e = 1 mod m, and e is the smallest such
integer then e divides d.
.[/quote]
If d=phi(m), so a^d=1(mod m).
And we have a^e=1(mod m).
We know the theorem:
If B=a^b-1, and C=a^c-1 where (B,C)=g then so (b,c)=r.
Where r and g are two integers=/=1.
So:
becuase of:
a^d=1(mod m).
a^e=1(mod m).
Then so (a^d-1,a^e-1)=m then we have (e,d)=v.
For v integer.

[quote=blob100;213756]If d=phi(m), so a^d=1(mod m).
And we have a^e=1(mod m).
We know the theorem:
If B=a^b-1, and C=a^c-1 where (B,C)=g then so (b,c)=r.
Where r and g are two integers=/=1.
So:
becuase of:
a^d=1(mod m).
a^e=1(mod m).
Then so (a^d-1,a^e-1)=m then we have (e,d)=v.
For v integer.[/quote]
I guessed that from here it is really easy so I didn't put the continous.
Here it is:
v</=e by (e,d)=v.
And by the definition of e, g is not smaller than e:
So, we have (e,d)=e.

[QUOTE=blob100;213756]If d=phi(m), so a^d=1(mod m).
And we have a^e=1(mod m).
We know the theorem:
If B=a^b-1, and C=a^c-1 where (B,C)=g then so (b,c)=r.
Where r and g are two integers=/=1.
So:
becuase of:
a^d=1(mod m).
a^e=1(mod m).
Then so (a^d-1,a^e-1)=m then we have (e,d)=v.
For v integer.[/QUOTE]

OK so far. But this does not show that e divides d.

[QUOTE=blob100;213770]I guessed that from here it is really easy so I didn't put the continous.
Here it is:
v</=e by (e,d)=v.
And by the definition of e, g is not smaller than e:
So, we have (e,d)=e.[/QUOTE]

This is not correct. Try my hint: proof by contradiction.
Assume that e does NOT divide d. This give a relation between e and
d. Now apply some known results.

[quote=R.D. Silverman;213781]This is not correct. Try my hint: proof by contradiction.
Assume that e does NOT divide d. This give a relation between e and
d. Now apply some known results.[/quote]
Here is the explanation for the step ("by the deffinition of e"):
By (e,d)=v we have a^(bv)-1 and a^(cv)-1 where bv=e and cv=d.
Let's say cv is not devided by bv. So, (b,c)=1.
Then we may say that if e=cv and m|a^e-1 and m|a^d-1 so: m|a^v-1:
Becuase (b,c)=1.
(a^v-1)(a^v-1)=a^2v-1
...
m|a^nv-1
But by the deffinition of e, the is no such v smaller than it, so v=c.
(The expressing is really bad, but I think it is able to be understood).

[QUOTE=blob100;213874]Here is the explanation for the step ("by the deffinition of e"):
By (e,d)=v we have a^(bv)-1 and a^(cv)-1 where bv=e and cv=d.
[/QUOTE]

What do you mean by "we have a^(bv)-1 and a^(cv)-1".
This statement merely gives two expressions.

[QUOTE]
Let's say cv is not devided by bv. So, (b,c)=1.
Then we may say that if e=cv and m|a^e-1 and m|a^d-1 so: m|a^v-1:
(The expressing is really bad, but I think it is able to be understood).[/QUOTE]

Sorry, but I don't understand it. You are using far too many free
variables. This is a lot of handwaving and does not constitute a proof.
It is a lot of independent (and sometimes incomplete) relationships.
There is nothing to connect your various assertions together.

And [b]nowhere[/b] do I see a statement that states: "Hence, e divides
d".



The problem is to show the following.

Assume that a^d = 1 mod m, and that e is the smallest positive integer
such that a^e = 1 mod m. Prove that e divides d. You have not done
so. And you have ignored my hint.

[QUOTE=R.D. Silverman;213876]What do you mean by "we have a^(bv)-1 and a^(cv)-1".
This statement merely gives two expressions.



Sorry, but I don't understand it. You are using far too many free
variables. This is a lot of handwaving and does not constitute a proof.
It is a lot of independent (and sometimes incomplete) relationships.
There is nothing to connect your various assertions together.

And [b]nowhere[/b] do I see a statement that states: "Hence, e divides
d".

[/QUOTE]

May I suggest the following: You need a really good proof based course
in old-fashioned geometry in order to learn how to do proofs. Since
we don't have time for such a course (and no blackboard for me to stand
in front of), let's try the following.

Write your proof in the following form:

Assertion Justification
--------- -----------

Assertion 1 Reason 1
Assertion 2 Reason 2
...
...
etc.

Each assertion must consist of a true statement (not just an expression)
and you must give a reason why the assertion is true. The reason
may be a reference to a theorem that has already been coverered, it
may be a reference to a previous assertion, or it may be a reference to
some given condition in the statement of the problem.

Here is your problem: All variables may be assumed to be positive integers.
If a^d = 1 mod m, and e is the smallest value such that a^e = 1 mod m,
prove that e divides d.

I will get you started: Assume that e does NOT divide d.

Here is the first step:

Assertion
(1) Since e does not divide d, and e < d we may write d = k*e + alpha,
where alpha is less than e.

Reason (1) : The division algorithm.

(You need not prove this, but I will give the proof) I will let you supply
the reasons for each step. This is a proof by contradiction.


Suppose k*e is the largest multiple of e less than d.

Asuume alpha > e. Then we may replace alpha by (e + x) for some positive
integer x.

Hence, d = k*e + (e+x) = e(k+1) + x.

But e(k+1) is larger than e*k, contradicting the assumption that k*e is the
largest multiple of e less than d. Thus, alpha < e. QED

[quote=R.D. Silverman;213879]May I suggest the following: You need a really good proof based course
in old-fashioned geometry in order to learn how to do proofs. Since
we don't have time for such a course (and no blackboard for me to stand
in front of), let's try the following.

Write your proof in the following form:

Assertion Justification
--------- -----------

Assertion 1 Reason 1
Assertion 2 Reason 2
...
...
etc.

Each assertion must consist of a true statement (not just an expression)
and you must give a reason why the assertion is true. The reason
may be a reference to a theorem that has already been coverered, it
may be a reference to a previous assertion, or it may be a reference to
some given condition in the statement of the problem.

Here is your problem: All variables may be assumed to be positive integers.
If a^d = 1 mod m, and e is the smallest value such that a^e = 1 mod m,
prove that e divides d.

I will get you started: Assume that e does NOT divide d.

Here is the first step:

Assertion
(1) Since e does not divide d, and e < d we may write d = k*e + alpha,
where alpha is less than e.

Reason (1) : The division algorithm.

(You need not prove this, but I will give the proof) I will let you supply
the reasons for each step. This is a proof by contradiction.


Suppose k*e is the largest multiple of e less than d.

Asuume alpha > e. Then we may replace alpha by (e + x) for some positive
integer x.

Hence, d = k*e + (e+x) = e(k+1) + x.

But e(k+1) is larger than e*k, contradicting the assumption that k*e is the
largest multiple of e less than d. Thus, alpha < e. QED[/quote]

I know the old fashioned geometry way of proving.

I'll try proving it by geometry style:
We know:
1)(a,m)=1
2)a^d=1(mod m)
3)a is of order e modulo m.
4)a^e=1(mod m) by (3).

The proof.
m|a^e-1 and m|a^d-1.
[B]Theorem:[/B]
If we have (a^x-1,a^y-1)=n, we have n|a^g-1 where (x,y)=g.
For x,y integers, n,g integers with relationships to x and y.

Therefore g<e or equals to e.
If g<e then exists m|a^g-1.
But by the [U]deffinition[/U] of e, there is no such a g smaller than e, so it equals to e.
And d=gb for b integer.
We agreed g=e so d=be.

Please tell me where the problem in my proof is.

[QUOTE=blob100;213889]I'll try proving it by geometry style:
We know:
1)(a,m)=1
2)a^d=1(mod m)
3)a is of order e modulo m.
4)a^e=1(mod m) by (3).

The proof.
m|a^e-1 and m|a^d-1.
[B]Theorem:[/B]
If we have (a^x-1,a^y-1)=n, we have n|a^g-1 where (x,y)=g.
For x,y integers, n,g integers with relationships to x and y.
[/QUOTE]

OK to here. GCD(a^x-1, a^y-1) = a^GCD(x,y) - 1.

[QUOTE]

Therefore g<e or equals to e.
[/QUOTE]

Disconnect. Non sequitur.

Since you have not said what x or y is, we do not know what g is.
All we know is that x and y, and hence g are abitrary integers.
You have not related them to e or d in any way.

Therefore the assertion that e >= g is meaningless. You have [b]not
defined[/b] g.


And you are still not FOLLOWING MY ADVICE. Do a simple PROOF
BY CONTRADICTION.

[quote=R.D. Silverman;213892]OK to here. GCD(a^x-1, a^y-1) = a^GCD(x,y) - 1.



Disconnect. Non sequitur.

Since you have not said what x or y is, we do not know what g is.
All we know is that x and y, and hence g are abitrary integers.
You have not related them to e or d in any way.

Therefore the assertion that e >= g is meaningless. You have [B]not [/B]
[B]defined[/B] g.


And you are still not FOLLOWING MY ADVICE. Do a simple PROOF
BY CONTRADICTION.[/quote]

I'll define the theorem again (and x,y):
For x,y and a 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.
So g is deffined as the the greatest common devisor of x and y.

I'll prove the first theorem by contradiction after I'll complete the current proof.