Prove that for any prime $P$, and for any a in the set $S = \{1,2,3,.., P-1\}$, there is a $b$ also in $S$ for which $ab \equiv 1 \pmod p$

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 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.

Answer 2

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.

Answer 3

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$.