Let $n > 1$ be an odd number, and let $P_n = \{b\pmod{n} : b^{n−1}\equiv 1\pmod{n}\}$ be the set of bases $b$ for which $n$ is a pseudoprime to the base $b$. Prove that $|P_n| = \prod\limits_{p\mid n}\gcd(p−1, n−1)$.
I have found that $|P_n| = \left(\gcd (p-1, n-1)\right)^2$
But how can I conclude that what I found is equivalent to $\prod\limits_{p\mid n}\gcd(p−1, n−1)$. In other words, how does $\left(\gcd (p-1, n-1)\right)^2 = \prod\limits_{p\mid n}\gcd(p−1, n−1)$ ?
NOTE: How I found that $|P_n| = \left(\gcd (p-1, n-1)\right)^2$ is very similar to the answer to this question: Prove that $n$ is a pseudoprime to the base $b$ if and only if $b^d\equiv1 \pmod n$...