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: 
It's easy to check that the values of $f(x)=ax$ are distinct for $x \in \{0,...,p-1\}$

So there is a unique $b$ with the property $f(b)=1$.
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.