Prove that if $a$ modulo $n$ has order $k$ then so does the inverse of $a$ modulo $n$ have order $k$.
By definition of order, we have $ a^k \equiv 1 \pmod n $ where $k$ is the least positive $j$ such that $ a^j \equiv 1 \pmod n $. Factorising gives us $ a \times a^{k-1} \equiv 1 \pmod n $ which means the inverse of $a$ modulo $n$ is $a^{k-1}$.
To show that $k$ is also the order of $a^{k-1}$, we need to show both
- $(a^{k-1})^k \equiv 1 \pmod n$ and $\gcd(a^{k-1},n)=1$
- $k$ is the least positive integer $j$ such that $(a^{k-1})^j \equiv 1 \pmod n$
That $\gcd(a^{k-1},n)=1$ is true follows from $\gcd(a,n)=1$. We continue,
$$ \begin{align} (a^{k-1})^k & \equiv (a^{k})^k \times (a^{k})^{-1} \pmod n \\ \\ & \equiv (1)^k \times (1)^{-1} \pmod n \\ \\ & \equiv 1 \pmod n \end{align} $$
For the purpose of contradiction, assume $g < k$ is the order of $a^{k-1}$. This means
$$ \begin{align} (a \times a^{k-1})^g & \equiv (1)^g \pmod n \\ \\ a^g \times (a^{k-1})^g & \equiv 1 \pmod n \\ \\ a^g \times (1)^g & \equiv 1 \pmod n \\ \\ a^g & \equiv 1 \pmod n \end{align} $$
This suggests $k$ is not the order of $a$ since $k<g$. This contradicts the given $k$ as the order of $a$ modulo $n$. And so the assumption $g < k$ is not true, and $k$ is the least positive integer $j$ such that $(a^{k-1})^j \equiv 1 \pmod n$. That is, $k$ is the order of $a^{k-1}$ modulo $n$.
And so $k$ being the order of $a$ modulo $n$ implies $k$ is also the order of the inverse of $a$ modulo $n$.