Verify the following are composite integers by using FlT:
(a) 4097
(b) 32 767
(c) 2197 [use base 13]
Before we start, it is worth reminding ourselves of FlT and its contrapositive.
FlT says:
$$ ( n \text{ prime } \land n \not \mid a ) \quad \implies \quad a^{n-1} \equiv 1 \pmod n $$
The contrapositive says
$$ a^{n-1} \not \equiv 1 \pmod n \quad \implies \quad (n \text{ composite } \lor n \mid a ) $$
If we know $n \not \mid a$, this reduces to
$$ a^{n-1} \not \equiv 1 \pmod n \quad \implies \quad n \text{ composite } $$
If we know $n$ is an odd integer, then we know $n \not \mid 2$, and so we have the specialised form of Proposition (4.6)
$$ 2^{n-1} \not \equiv 1 \pmod n \quad \implies \quad \text{odd integer } n \text{ composite } $$
(a) Noting that 4097 is an odd integer, and also $2^{12} \equiv 4096 \equiv -1 \pmod {4097}$, we have
$$ \begin{align} 2^{4097-1} & \equiv 2^{4096} \pmod {4097} \\ \\ & \equiv (2^{12})^{341} \times 2^4 \pmod {4097} \\ \\ & \equiv (-1) \times 16 \pmod {4097} \\ \\ & \equiv 4081 \pmod {4097} \\ \\ 2^{4097-1} & \not \equiv 1\pmod {4097} \end{align} $$
So by Proposition (4.6) we conclude 4097 is composite.
(b) Noting that 32767 is an odd integer, and $2^{15} \equiv 32768 \equiv 1 \pmod {32767}$, we have
$$ \begin{align} 2^{32767-1} & \equiv 2^{32766} \pmod {32767} \\ \\ & \equiv (2^{15})^{2184} \times 2^6 \pmod {32767} \\ \\ & \equiv (1) \times 64 \pmod {32767} \\ \\ & \not \equiv 1 \pmod {32767} \end{align} $$
So by Proposition (4.6) we conclude 32767 is composite.
(c) We can immediately see that $13^3=2197$ and so 2197 is composite.