Inverses Modulo N

Suppose that we have the following congruence, and we want to solve for $x$: $$ax \equiv b \pmod{n}$$ Well, let's think about what we would do if this were just a standard equality and not a congruence: $$x = ba^{-1}$$ We would typically write this as $\frac{b}{a}$, but the idea is the same. We multiplied by $a^{-1}$ on both sides. Could we do a similar thing for congruence?

Indeed, we can! In general, in a group $G$ with identity element $e$, the inverse of an element $f$ is the element $f^{-1}$ such that $f^{-1}\cdot f = f\cdot f^{-1} = e$. Thus, in congruence modulo $n$, the inverse of a number $a$ is the number $a^{-1}$ such that: $$aa^{-1} \equiv 1 \pmod{n}$$

However, you may start to see a problem here. How about the inverse of $4$ modulo $10$? Since $4$ and $10$ are both even, there is no integer that can be multiplied by $4$ to leave a remainder of $1$ modulo $10$. Thus, $4$ has no inverse modulo $10$. This can be easily extended to the following important fact:

If $(a,n)>1$, then $a$ has no inverse modulo $n$.

Our intuition tells us that, if $(a,n)=1$, then $a$ should have an inverse modulo $n$. (As an exercise, check this for $a=1, 3, 7, 9$ and $n=10$. Can you always find an inverse?) It turns out that this is true, but we can say something stronger:

If $(a,n)=1$, then $a$ has a unique inverse modulo $n$.

To prove this, consider the set ${a, 2a, 3a, ..., (n-1)a}$. We will prove that this set is an "almost-complete" residue class modulo $n$, meaning that it contains every remainder modulo $p$ except $0$ exactly once.

It is clear that none of the elements in the set is congruent to $0$ modulo $n$. Assume, for the sake of contradiction, that $ai\equiv aj \pmod{n}$ for $0\lt j\lt i\lt n$. Then, $a(i-j)\equiv 0 \pmod{n}$, which is a contradiction. Therefore, all of the elements ${a, 2a, 3a, ..., (p-1)a}$ are distinct modulo $n$. Thus, since these $n-1$ elements can only occupy $n-1$ residue classes, each residue class must be occupied exactly once.

It follows that there is a unique $x$ such that $1\le x\le n-1$ and $ax\equiv 1 \pmod{n}$. Therefore, $a$ has a unique inverse modulo $n$.

Let $p$ be a prime, and $x$ be the inverse of $a$, which is not divisible by $p$. Find $x$ in terms of $a$ and $p$.

Hint: Fermat's Little Theorem.

This is generalization of the previous one. Let $n$ be co-prime to $a$ and $x$ be the inverse of $a$ modulo $n$. Express $x$ as a function of terms of $a$ and $n$.

Hint: Euler-Fermat Theorem.