I am trying to prove that $45$ is composite using Fermat's Little Theorem. I am given a hint which states: "Find an integer $b$ such that $b^{45} \not \equiv b \pmod{45}$ and explain why this implies that $45$ cannot be prime."
If I understand, the reason that finding such a $b$ would be sufficient to show that $45$ is composite is because this would demonstrate the contrapositive of Fermat's Little Theorem insofar as if $a^p \not \equiv a\pmod{p}$ then $p$ is not a prime.
I have first tried finding such a $b$ but I'm simply guessing and that doesn't seem like the best approach to this. Any help would be appreciated on how to proceed.
Best Answer
Well, to find a satisfactory $b$, we can make use of our knowledge of the decomposition $45=3^2\times 5$.
This means if we pick $b=3\times5=15$, then we would have $b^n\equiv0\pmod{45}$ for any $n\ge 2$ (in particular for $n=45$).
[Added for clarity]
More explicitly, note that $15^2=3^2\times5^2=45\times 5$. Hence if $n\ge2$, then $$15^n\equiv 15^2\times15^{n-2}\equiv 45\times 5\times 15^{n-2}\equiv 0\pmod {45}$$
Perhaps making use of the known factorization is in some sense cheating. In that case, you can just say $15^2=225=5\times 45$, and so $15^2\equiv 0\pmod{45}$, and then use $$15^n\equiv 15^2\times15^{n-2}\equiv 0\times15^{n-2}\equiv0\pmod{45}$$
However, our motivation for looking at the number $15$ does come from us already knowing the factorization of $45$.