# Solution

$\require{AMSsymbols}$

Verify using fast exponentiation that the following congruence is true $$129^{64026} \equiv 15179\pmod{64027}$$ Can you conclude 64027 is a composite number?

First we verify the congruence given with fast exponentiation

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

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

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

$$\begin{array}{rcl} 64026 &=& 2 \cdot 32013 + 0\\ 32013 &=& 2 \cdot 16006 + 1\\ 16006 &=& 2 \cdot 8003 + 0\\ 8003 &=& 2 \cdot 4001 + 1\\ 4001 &=& 2 \cdot 2000 + 1\\ 2000 &=& 2 \cdot 1000 + 0\\ 1000 &=& 2 \cdot 500 + 0\\ 500 &=& 2 \cdot 250 + 0\\ 250 &=& 2 \cdot 125 + 0\\ 125 &=& 2 \cdot 62 + 1\\ 62 &=& 2 \cdot 31 + 0\\ 31 &=& 2 \cdot 15 + 1\\ 15 &=& 2 \cdot 7 + 1\\ 7 &=& 2 \cdot 3 + 1\\ 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

$$64026 = 1111101000011010_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

$$129^{64026} = 129^{32768} \cdot 129^{16384} \cdot 129^{8192} \cdot 129^{4096} \cdot 129^{2048} \cdot 129^{512} \cdot 129^{16} \cdot 129^8 \cdot 129^1$$

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

$$\begin{array}{rcccl} 129^{1} &\equiv& 129\\ 129^{2} &\equiv& 129^2 &\equiv& \fbox{16641}\\ 129^{4} &\equiv& 16641^2 &\equiv& 276922881 &\equiv& 6106\\ 129^{8} &\equiv& 6106^2 &\equiv& 37283236 &\equiv& \fbox{19522}\\ 129^{16} &\equiv& 19522^2 &\equiv& 381108484 &\equiv& \fbox{19780}\\ 129^{32} &\equiv& 19780^2 &\equiv& 391248400 &\equiv& 43430\\ 129^{64} &\equiv& 43430^2 &\equiv& 1886164900 &\equiv& 57534\\ 129^{128} &\equiv& 57534^2 &\equiv& 3310161156 &\equiv& 29283\\ 129^{256} &\equiv& 29283^2 &\equiv& 857494089 &\equiv& 44505\\ 129^{512} &\equiv& 44505^2 &\equiv& 1980695025 &\equiv& \fbox{19780}\\ 129^{1024} &\equiv& 19780^2 &\equiv& 391248400 &\equiv& 43430\\ 129^{2048} &\equiv& 43430^2 &\equiv& 1886164900 &\equiv& \fbox{57534}\\ 129^{4096} &\equiv& 57534^2 &\equiv& 3310161156 &\equiv& \fbox{29283}\\ 129^{8192} &\equiv& 29283^2 &\equiv& 857494089 &\equiv& \fbox{44505}\\ 129^{16384} &\equiv& 44505^2 &\equiv& 1980695025 &\equiv& \fbox{19780}\\ 129^{32768} &\equiv& 19780^2 &\equiv& 391248400 &\equiv& \fbox{43430}\\ \end{array}$$

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

$$\begin{array}{rcl} 129^{64026} &\equiv& 16641 \cdot 19522 \cdot 19780 \cdot 19780 \cdot 57534 \cdot 29283 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 56631 \cdot 19780 \cdot 19780 \cdot 57534 \cdot 29283 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 8815 \cdot 19780 \cdot 57534 \cdot 29283 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 15179 \cdot 57534 \cdot 29283 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 44333 \cdot 29283 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 55814 \cdot 44505 \cdot 19780 \cdot 43430\\ &\equiv& 10578 \cdot 19780 \cdot 43430\\ &\equiv& 56631 \cdot 43430\\ &\equiv& 15179 \end{array}$$

This verifies the calculation given in the question above.

Note, from this calculation, we can confirm that $64027$ must be composite, as otherwise Fermat's Little Theorem would require that $129^{64026} \equiv 1\pmod{64027}$

(In case you are curious, $64027 = 43 \times 1489$. That said, how to find these two factors is not revealed by the above calculations.)