Proving that $45$ is composite using Fermat's Little Theorem

Question

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.

Answer 1

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

Answer 2

Hint $\,\ 3^2\mid 45\mid 3^{45}\!-\!3\,\Rightarrow\, 3^2\mid 3,\,$ contradiction.

---

Remark $\ $ The above show that the modulus $\,n\,$ must be $\,\rm\color{#0a0}{squarefree}.\,$ It's an easy part of

Theorem $ $ (Korselt's Carmichael Criterion) $\ $ For $\rm\:1 < e,n\in \Bbb N\:$ we have

$$\rm \forall\, b\in\Bbb Z\!:\ n\mid b^e\!-b\ \iff\ n\ \ is\ \ \color{#0a0}{squarefree},\ \ and \ \ \color{#c00}{p\!-\!1\mid e\!-\!1}\ \, for\ all \ primes\ \ p\mid n\quad $$

Proof $\ $ See this answer.

Answer 3

Actually, guessing is a perfectly sensible thing to try for a problem like this. In general, for most (but not all!) composite numbers $n$, $b^n\not\equiv b$ mod $n$ for most (but again not all) numbers $b$. In particular, it makes sense to just try a small number, like $b=2$, and see what happens. The trick is to organize the calculation so as to minimize the amount of arithmetic that needs to be done. In this case, one path that works (using $45\cdot3=135$) is

$$\begin{align} 2^7&=128\equiv-7\\ 2^{14}&\equiv(-7)^2=49\equiv4\\ 2^{42}&\equiv4^3=64\equiv19\\ 2^{45}&\equiv8\cdot19=152\equiv17\not\equiv2 \end{align}$$