(a) Show that $2^{8190} ≡ 1 \pmod {8191}$. What can you say about the number 8191?
(b) Show that $2^{65536} ≡ 1 \pmod {65537}$. What can you say about the number 65537?
(a) From experience we know that 8192 is a power of 2. In fact, $2^{13} = 8192$. And so
$2^{13} \equiv 1 \pmod {8191}$
$ 2^{8190} \equiv (2^{13})^{630} \equiv 1 \pmod {8191}$
This suggests 8191 is a candidate for being a prime.
(b) Similarly, we know that $2^{16}=65536$ and so
$ 2^{16} \equiv -1 \pmod {65537} $
$ 2^{65536} \equiv (2^{16})^{4096} \equiv 1 \pmod {65537} $
This suggests 65537 is a candidate for being a prime.