Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^d\equiv1 \pmod n$... Question:

Let $n = pq$ be a product of two distinct odd primes and put $d = \gcd(p − 1, q − 1)$.
  (a) Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^d\equiv  1 \pmod n$. 
  (b) Conclude (using part (a)) that $|Pn| = d^2.$

I got part (a) on my own. I just don't see how I can conclude part (b) with it. Could someone guide me in the right direction?
 A: You've solved (a), so I'll only solve (b).
I.e. you want to find the number of solutions to $x^d\equiv 1\pmod{pq}$. This is equivalent to the system $\begin{cases}x^d\equiv 1\pmod{p}\\ x^d\equiv 1\pmod{q}\end{cases}$. It's enough to prove that if $t\mid p-1$, then $x^t\equiv 1\pmod {p}$ has exactly $t$ solutions. After that, $d^2$ follows from the Chinese Remainder Theorem.

Proof 1:
Let $g$ be a primitive root mod $p$ and let $x\equiv g^k\pmod{p}$. Then $$x^t\equiv 1\pmod{p}\iff g^{kt}\equiv 1\pmod{p}\iff p-1\mid kt$$
$$\iff \frac{p-1}{t}\mid k\iff x\equiv \{g^0,g^{\frac{p-1}{t}},g^{\frac{2(p-1)}{t}},\ldots, g^{\frac{(t-1)(p-1)}{t}}\}\pmod{p},$$
so there are exactly $t$ solutions.

Proof 2:
Lemma: a polynomial of $k$'th degree has at most $k$ zeroes mod $p$.
Proof (I've written it before in another answer, so I've copy-pasted it here): Use induction. $1$'st degree polynomial $ax+b$ with $a\not\equiv 0\pmod{p}$ has at most one root mod $p$ (in fact, exactly one root mod $p$).
If every $k$'th degree polynomial has at most $k$ roots mod $p$, then prove that an arbitrary polynomial $P(x)=a_{k+1}x^{k+1}+\cdots+a_1x+a_0$ with $a_{k+1}\not\equiv 0\pmod{p}$ has at most $k+1$ roots mod $p$. If $P(x)$ has no roots mod $p$, then we're done. Otherwise let $a$ be a root of $P(x)$ mod $p$. Then 
$$P(x)\equiv P(x)-P(a)\equiv a_{k+1}\left(x^{k+1}-a^{k+1}\right)+\cdots+a_1\left(x-a\right)\pmod p$$
Now use the factorization $x^{k+1}-a^{k+1}=(x-a)\left(x^{k}+x^{k-1}a+\cdots+a^{k}\right)$:
$$\equiv (x-a)\left(a_n\left(x^{k}+x^{k-1}a+\cdots+a^{k}\right)+\cdots+a_1\right)\pmod p$$
The other polynomial has $k$'th degree, so by the inductive hypothesis and Euclid's Lemma the arbitrary polynomial $P(x)$ has at most $k+1$ roots mod $p$. $\,\square$
$$x^{p-1}-1=\left(x^d-1\right)\left(x^{p-1-d}+x^{p-1-2d}+\cdots+1\right)$$
By Fermat's Little theorem, the LHS has exactly $p-1$ zeroes mod $p$. By the Lemma and Euclid's Lemma both polynomials on the RHS have exactly $d$ and $p-1-d$ zeroes respectively. $\,\square$
