If x is invertible mod n prove that the order of x mod n is

If x is invertible mod n, prove that the order of x mod n is the same as the order of the inverse of x mod n. Use n = 155150096071 and phi(n) = 155148967944 to factor n.

Solution

E6: Let the order of x be n such that xⁿ = e.

Now we need to show that (x^-1)ⁿ = e

Consider (x^-1)ⁿ = e (x^-1)ⁿ

=> (x^-1)ⁿ = xⁿ(x^-1)ⁿ

=> (x^-1)ⁿ = (x x^-1)ⁿ

=> (x^-1)ⁿ = eⁿ

=> (x^-1)ⁿ = e

Thus the order of x^-1 is n.

Therefore the order of x and its inverse is same.