Proof: Number theory: Prove that if $n$ is composite, then the least $b$ such that $n$ is not $b$-pseudoprime is prime. I'm looking to prove this, but not too sure how:
If $n$ is composite, then the least $b$ such that $n$ is not $b$-psp is prime.
Thanks!

Let $b$ be the minimum such element and assume it is not prime.Then $b=cd$ and $b^{n-1}\not\equiv 1 \bmod n$ . Then $b^{n-1}=c^{n-1}d^{n-1}\not \equiv 1$. So one of $b^{n-1}$ and $c^{n-1}$ is not $1\bmod n$. Contradicting the minimality of $b$.
