Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$. Full question: Let $p$ be a prime and let $a$ be an integer such that $1 \leq a < p$. Then there exists a unique natural number $b$ less than $p$ such that $ab \equiv 1 \pmod{p}$.
Looking for the proof. Is Fermat's little theorem necessary?
 A: i expect the proof of Little Fermat requires this fact.
To understand your problem, consider the collection of products $$\{a\times 0, a\times 1, a\times 2, \cdots, a\times (p-1)\}\pmod p$$  No two of these can coincide $\pmod p$  Indeed,  $a\times k\equiv a\times j\pmod p\implies (k-j)a\equiv 0\pmod p$.  Thus $p|(k-j)$ (since $\gcd (a,p)=1$) so $k\equiv j\pmod p$.  Thus our collection contains $p$ distinct classes $\pmod p$, so it must contain all the classes $\pmod p$ exactly once.  In particular, it contains $1\pmod p$ exactly once.
A: Fermat's Little Theorem is not necessary but can be used to give a short proof of existence: take $b=a^{p-2} \bmod p$.
Alternatively, you can use Bézout's identity: $ax+py=1$ and take $b=x \bmod p$.
Uniqueness is simple: $ab \equiv 1 \equiv ab' \bmod p$ implies $a(b-b') \equiv 0 \bmod p$. Multiplying by $b$, we get $b-b' \equiv 0 \bmod p$ and so $b'=b+kp$. If $k\ge 1$, we get $b' > p$. If $k \le -1$, we get $b'<0$. Therefore, for $0 < b'< p$, we must have $k=0$ and so $b'=b$.
A: Let $b_1$ and $b_2$ such that $b_1\not = b_2$ and $0<b_1,b_2<p$ and
$$ab_1\equiv ab_2 \equiv 1 (\bmod p)$$
Then $a(b_1-b_2)\equiv 0 (\bmod p)$. But $\gcd (a,p)=1$ and $0<b_1-b_2<p$
A: Since $p$ is prime and $1\leq a<1$ we have $g.c.d.(a,p)=1$. By euclidean algorithm, there are integers $x,y$ such that $ax+py=1$, and when considering this equation modulo $p$ we get $a\cdot x\equiv 1 \mod p$.
Take any $x$ such that for some $y$, $ax+py=1$. Use division algorithm to get $x=pq+b$ with $0\leq b<p$. Then, $1=ax+py=a(pq+b)+py=ab+p(q+y)\Rightarrow ab\equiv 1 \mod p$.
To prove uniqueness: suppose $b_1,b_2$ are different numbers satisfying $ab_1\equiv 1\equiv ab_2 \mod p$. Then, $$p \text{ divides }ab_1-ab_2=a(b_1-b_2)\Rightarrow p|a \text{ or }p|(b_1-b_2)$$ because $p$ is prime. Now, since $1\leq a<p$, we know that $p\not| a$. So $p|(b_1-b_2)$ and we conclude that $b_1\equiv b_2 \mod p$, which is clearly impossible for $0\leq b_1,b_2<p$ unless $b_1=b_2$.
A: Hint: When does a linear congruence equation $ax\equiv b($mod $m)$ have a solution?
EDIT: If you know the rule regarding division in modular arithmetic, you can find uniqueness.
