Let $e$ and $n$ be positive integers. Suppose $e$ and $φ(n)$ are relatively prime. Prove if $x^e ≡ 1\bmod(n)$, then $x ≡ 1\bmod(n)$

Question

My thoughts so far:

Since $φ(n)$ is always even, $e$ must be odd $\implies e$ can be written as $2d + 1$. $\implies x^{2d+1} - 1 = kn$

However, I don't know how to proceed from here. Any tips?

Answer 1

Well we know $x^{\phi(n)}\equiv 1\mod n$, so we can use that, since now we know for all positive integers $a,b$ that $$(x^{\phi(n)})^a(x^e)^b\equiv1\mod n$$ which can be rewritten to $$x^{a\phi(n)+be}\equiv1\mod n$$

for every $a,b$. Now since $\phi(n)$ and $e$ are coprime, we can find $a,b$ such that $a\phi(n)+be=1$, and so if we pick those, the congruence reads

$$x\equiv 1\mod n$$

exactly what we wanted.