Let a and n be positive integers with a n and let m be the

Let a and n be positive integers with a < n, and let m be the smallest positive integer such that a^m is equivalent to a mod n. Prove that a^x is equivalent to a^y mod n if and only if x is equivalent to y mod m.

Solution

a and n be positive integers with a < n.

Let m be the smallest positive integer such that a^m a (mod n)

Let, x y (mod m)

So, m | (x – y)

Or, x – y = km for some positive integer k.

Since, a^m a (mod n)

We get by properties of congruence modulo, (a^m)^k a^k (mod n)

Now, (a^m)^k = a^mk = a^{x – y}

a^{x – y} a^k (mod n)

Therefore, a^x is equivalent to a^y mod n (Proved)