Using Fermats little theorem

Question

I'm given that $p,q$ are prime and b is prime to $(p-1)(q-1)$ (their gcd is 1) also $d$ is the inverse of $b$ modulo $(p-1)(q-1)$ I have to prove that $x^{bd}=x(mod$ $p)$, for every integer $x\in[1,2,3,..p-1]$

So far I've done:

Since b and d are inverse modulo $(p-1)(q-1)$ $\Rightarrow bd\equiv 1(mod(p-1)(q-1))\Rightarrow bd-1=k(p-1)(q-1), k\in\mathbb{Z}$

$bd=1+k(p-1)(q-1) \Rightarrow x^{bd}=xx^{k(p-1)(q-1)}$

I'm pretty sure that I have to use fermats little theorem now but I'm not sure how as I'm not that familiar with modular operations and the theorem.. Any ideas?

Answer 1

Fermat's little theorem tells you that $x^{p-1} = 1\ (\text{mod}\ p)$, so you know that $x^{k(p-1)(q-1)} = (x^{p-1})^{k(q-1)} = 1^{k(q-1)} = 1\ (\text{mod}\ p)$.

Answer 2

Given $p,q \in \mathbb{P}$ and $b \rightarrow \gcd(b, \varphi(pq))=gcd(b, (p-1)(q-1))=1$

Also $d$ is given such that it is the inverse of $b$:

$bd \equiv 1 \pmod{\varphi(pq))}$

The realm of exponents works $\pmod{\varphi}$ so we have the following equivalences:

$x^{bd} \equiv x^{b(b^{-1})} \equiv x^1 \equiv x \pmod {pq}$