[Math] Is the modulus of an exponent always $\phi(n)$ in a modulo $n$ expression

modular arithmetictotient-function

According to this proof, given an expression $$x^e\pmod n$$ the modulus of the exponent $e$ is $\phi(n)$.

From Euler's Theorem, I know that $$x^{\phi(n)}\equiv 1\pmod n$$ holds true iff $x$ is coprime with $n$.

Is it is always the case that the exponent in a$\mod n$ expression is $\phi(n)$, or does this only apply when $x$ and $n$ are coprime ?

If it only applies when $x$ and $n$ are coprime then does that mean that $e$ can only be reduced when $x$ and $n$ are coprime?

Best Answer

When $(x, n) = 1$, we have two different concepts:

  • $\phi(n)$ is a number such that for any $x$ coprime to $n$, $x^{\phi(n)} \equiv 1 \pmod{n}$
  • $r = \operatorname{ord}_n(x)$ is the smallest positive integer such that $x^r \equiv 1 \pmod{n}$

Note that $r \mid \phi(n)$ is always true, but this does not mean $r = \phi(n)$. If you have some $e$ such that $x^e \equiv 1 \pmod{n}$, then you can say $r \mid e$ and also $(e, \phi(n)) \geq r$, but that's about it.

Perhaps you would also be interested in the fact that $x^e \equiv x^{e \pmod{r}} \equiv x^{e \pmod{\phi(n)}} \pmod{n}$, which is a consequence of the facts above. Note that none of the points above are valid if $(x, n) \neq 1$; in such a case, $x^e \equiv 1 \pmod{n}$ has no solutions.

Related Question