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