(a) Let $\gcd (a, n) = 1$. Prove that
$$ a^{−1} \equiv a^{\phi(n)−1} \pmod n $$
(b) Let $\gcd (a, n) = 1$. Show that the solution of the linear congruence
$$ ax \equiv b \pmod n $$
is given by
$$ x \equiv ba^{\phi(n)−1} \pmod n $$
(a) Since $\gcd(a,n)=1$, we can use Euler's Theorem
$$ a^{\phi(n)} \equiv 1 \pmod n $$
Factorising the LHS we have
$$ a \times a^{\phi(n)-1} \equiv 1 \pmod n $$
By the definition of inverse, we have $a \times a^{-1} \equiv 1 \pmod n$, and so
$$ a^{-1} \equiv a^{\phi(n)-1} \pmod n $$
(b) Since $\gcd(a,n)=1$ we can use Euler's Theorem
$$ a^{\phi(n)} \equiv 1 \pmod n $$
Multiplying both sides by $b$ and also factorising $a^{\phi(n)}$ as above gives us
$$ a \times \bigl ( a^{\phi(n)-1} \times b \bigr ) \equiv b \pmod n $$
And so, by comparison, we can see the solution of the linear congruence $ax \equiv b \pmod n$ is
$$ x \equiv ba^{\phi(n)−1} \pmod n $$