# Solution

$\require{AMSsymbols}$

Verify using fast exponentiation that the congruence $$2^{52632} \equiv 1\pmod{52633}$$ is true. Can you conclude $52633$ is a prime number?

First we verify the congruence given with fast exponentiation

To do this, we need to express $2^{52632}$ as a product of factors coming from $2, 2^2, 2^4, 2^8, 2^{16}, 2^{32}, \ldots$

In such a product, the exponents on the factors used would have to sum to $52632$. Further, since each of these exponents is itself a power of $2$, finding the exponents we need is equivalent to converting $52632$ to base $2$ and looking at where the $1$'s are.

Recall, we can convert $52632$ to base $2$ efficiently by successively dividing by two and discarding (but keeping track of) the remainders:

$$\begin{array}{rcl} 52632 &=& 2 \cdot 26316 + 0\\ 26316 &=& 2 \cdot 13158 + 0\\ 13158 &=& 2 \cdot 6579 + 0\\ 6579 &=& 2 \cdot 3289 + 1\\ 3289 &=& 2 \cdot 1644 + 1\\ 1644 &=& 2 \cdot 822 + 0\\ 822 &=& 2 \cdot 411 + 0\\ 411 &=& 2 \cdot 205 + 1\\ 205 &=& 2 \cdot 102 + 1\\ 102 &=& 2 \cdot 51 + 0\\ 51 &=& 2 \cdot 25 + 1\\ 25 &=& 2 \cdot 12 + 1\\ 12 &=& 2 \cdot 6 + 0\\ 6 &=& 2 \cdot 3 + 0\\ 3 &=& 2 \cdot 1 + 1\\ 1 &=& 2 \cdot 0 + 1 \end{array}$$

Reading the remainders found above from the bottom to the top, we find

$$52632 = 110011011011000_2$$

Note that the rightmost digit of this base $2$ expansion corresponds to $2^0$, and the leftmost digit corresponds to $2^{32768}$. Realizing that each $1$ corresponds to a power of $2$ that we will use, tells us that

$$2^{52632} = 2^{32768} \cdot 2^{16384} \cdot 2^{2048} \cdot 2^{1024} \cdot 2^{256} \cdot 2^{128} \cdot 2^{16} \cdot 2^8$$

Now we turn our attention to finding these powers of $2 \pmod{52633}$, which we can accomplish by successive squaring and reduction $\pmod{52633}$:

$$\begin{array}{rcccl} 2^1 &\equiv& 2\\ 2^2 &\equiv& 2^2 &\equiv& 4\\ 2^4 &\equiv& 4^2 &\equiv& 16\\ 2^8 &\equiv& 16^2 &\equiv& \fbox{256}\\ 2^{16} &\equiv& 256^2 &\equiv& 65536 &\equiv& \fbox{12903}\\ 2^{32} &\equiv& 12903^2 &\equiv& 166487409 &\equiv& 9230\\ 2^{64} &\equiv& 9230^2 &\equiv& 85192900 &\equiv& 32706\\ 2^{128} &\equiv& 32706^2 &\equiv& 1069682436 &\equiv& \fbox{21977}\\ 2^{256} &\equiv& 21977^2 &\equiv& 482988529 &\equiv& \fbox{28121}\\ 2^{512} &\equiv& 2812^2 &\equiv& 790790641 &\equiv& 32449\\ 2^{1024} &\equiv& 32449^2 &\equiv& 1052937601 &\equiv& \fbox{14436}\\ 2^{2048} &\equiv& 14436^2 &\equiv& 208398096 &\equiv& \fbox{24049}\\ 2^{4096} &\equiv& 24049^2 &\equiv& 578354401 &\equiv& 22997\\ 2^{8192} &\equiv& 22997^2 &\equiv& 528862009 &\equiv& 5625\\ 2^{16384} &\equiv& 5625^2 &\equiv& 31640625 &\equiv& \fbox{8192}\\ 2^{32768} &\equiv& 8192^2 &\equiv& 67108864 &\equiv& \fbox{1789}\\ \end{array}$$

Finally, we multiply the desired powers (which have boxes around them above) together -- two at a time, reducing each product $\pmod{52633}$, so that our numbers don't get too big:

$$\begin{array}{rcl} 2^{52632} &\equiv& 256 \cdot 12903 \cdot 21977 \cdot 28121 \cdot 14436 \cdot 24049 \cdot 8192 \cdot 1789\\ &\equiv& 39922 \cdot 21977 \cdot 28121 \cdot 14436 \cdot 24049 \cdot 8192 \cdot 1789\\ &\equiv& 26317 \cdot 28121 \cdot 14436 \cdot 24049 \cdot 8192 \cdot 1789\\ &\equiv& 40377 \cdot 14436 \cdot 24049 \cdot 8192 \cdot 1789\\ &\equiv& 24530 \cdot 24049 \cdot 8192 \cdot 1789\\ &\equiv& 11306 \cdot 8192 \cdot 1789\\ &\equiv& 37305 \cdot 1789\\ &\equiv& 1 \end{array}$$

This verifies the calculation given in the question above.

As for the rest of the question, recall that Fermat's Little Theorem guarantees that if $p$ is prime, and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$, but the reverse is not always true. Just because

$$2^{52632} \equiv 1 \pmod{52633}$$

we can't be assured that $52633$ is prime. In fact, it isn't:

$$52633 = 7 \times 73 \times 103$$