Originally Posted by
jimmyjimmyjimmy Hi, I don't know how to do math code or anything to make it look good, but bear with me please.
Given integers a and m,
Suppose a^e == 1 mod m (where == is the congruence sign, ^ raises to a power)
Suppose e is the smallest positive integer for which this is true.
If u>0, show that a^u == 1 mod m if and only if e divides u.
It's easy to show that if e divides u, then a^u == 1 mod m.
I am having a hard time showing the other direction though.
One thing I think that might be useful in the proof is to multiply both sides of a^e == 1 mod m by a^(u-e) to obtain a^u == a^(u-e) mod m. If anyone has any hints, please let me know. Thanks.