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.
I’m not sure if the Euclidean algorithm works here (but I could be wrong).
Do you know group theory? The problem is very simple if you consider the multiplicative group of the units of the ring of integers modulo Then if is the smallest positive integer such that this means has order in – and the rest is just group theory.