Question: This question was on a test in my cryptography class a couple weeks ago and I haven't been able to figure out a good proof. A hint was given with the question: all natural numbers have unique prime factors. 

Here's an example showing it's true for $P = 11$

$a = 1, b = 1, ab \equiv 1 \pmod P$

$a = 2, b = 6, ab \equiv 1 \pmod P$

$a = 3, b = 4, ab \equiv 1 \pmod P$

$a = 5, b = 9, ab \equiv 1 \pmod P$

$a = 7, b = 8, ab \equiv 1 \pmod P$

$a = 10, b = 10, ab \equiv 1 \pmod P$

the other values of a $(4, 6, 8, 9)$ appear as $b$ values, but it still works. 

Some things I figured out that I'm not sure if they matter. 

If $a = P-1$, then $b = P-1$. $( (P-1)(P-1) \equiv 1 \pmod p )$

Answer: 
Let $S = \{1,2, \dots, p-1\}$ Fix $a \in S$ and consider the function $m\_a: S -> S$ which sends $k \mapsto k\cdot a \pmod p$
We claim that $m\_a$ is injective. Note that if $m\_a(k\_1)=m\_a(k\_2)$ we have $a\cdot k\_1 \equiv a \cdot k\_2 \pmod p $ so $a \cdot (k\_1 - k\_2) \equiv 0 \pmod p$ This means that the product $a \cdot (k\_1 - k\_2)$ is divisible by $p$. As $p$ is prime, $a$ is coprime to $p$, so it must be the case that $k\_1 - k\_2$ is divible by $p$, As $|k\_1 - k\_2| < p$ and $p$ is prime, this can only be the case if $k\_1 - k\_2 = 0$, thus $k\_1 = k\_2$. Now finally as $m\_a$ is an injective function from a finite set to itself, it must be the case that $m\_a$ is surjective, which implies that there is some $b \in S$ such that $a\cdot b \equiv 1 \pmod p$

Note that this proof can be simplified and generalized if you know some basic notions from ring theory: it amounts to the fact that a finite integral domain is a field.
Lets see that, take $a$ in $S $ then as $p $ is prime $(a,p)=1$. Then there exists integers $r,s $ such that $ar+ps=1$ this implies $ps=1-ar $ then $p| 1-ar $ and this is the definition of $1 \equiv ar \pmod p $ and then the b you are looking for is the r we used. This shows such b exists and tells how can you find it. Hope it helps.