## Exercises - Fast Exponentiation and Fermat's Little Theorem

1. Note that $73$ is prime and $9 \not\equiv 0\pmod{73}$. Thus, Fermat's Little Theorem applies and guarantees that $9^{72} \equiv 1\pmod{73}$.

Thus $\pmod{73}$ we have, $$\begin{array}{rcl} 9^{794} &=& (9^{72})^{11} \cdot 9^2 \\ &\equiv& 1^{11} \cdot 81 \\ &\equiv& 81 \\ &\equiv& 8 \end{array}$$

2. By Fermat's Little Theorem, we know since $29$ is prime, that if $x \not\equiv 0\pmod{29}$, then $x^{28} \equiv 1\pmod{29}$.

Clearly $x \equiv 0\pmod{29}$ is not a solution as $0^{86} \equiv 0\pmod{29}$

Consequently, we may rewrite the left side of the congruence given in the following way $$x^{86} = (x^{28})^3 \cdot x^2 \equiv 1^3 \cdot x^2 = x^2$$

Thus, we really just need to solve $x^2 \equiv 6\pmod{29}$.

Now we can check the rest by hand $\pmod{29}$:

 $1^2 \equiv 1$ $2^2 \equiv 4$ $3^2 \equiv 9$ $4^2 \equiv 16$ $5^2 \equiv 25$ $6^2 \equiv 7$ $7^2 \equiv 20$ $8^2 \equiv 6$ $9^2 \equiv 23$ $10^2 \equiv 13$ $11^2 \equiv 5$ $12^2 \equiv 28$ $13^2 \equiv 24$ $14^2 \equiv 22$ $15^2 \equiv 22$ $16^2 \equiv 24$ $17^2 \equiv 28$ $18^2 \equiv 5$ $19^2 \equiv 13$ $20^2 \equiv 23$ $21^2 \equiv 6$ $22^2 \equiv 20$ $23^2 \equiv 7$ $24^2 \equiv 25$ $25^2 \equiv 16$ $26^2 \equiv 9$ $27^2 \equiv 4$ $28^2 \equiv 1$

So from the table above, $x$ is a solution to $x^{86} \equiv 6 \pmod{29}$ if and only if either $$x \equiv 8\pmod{29} \quad \textrm{ or } \quad x \equiv 21\pmod{29}$$

3. Solve $x^{39} \equiv 3 \pmod{13}$

4. Yes!

If $1734251$ were prime, then noting that $7 \not\equiv 0\pmod{1734251}$, Fermat's Little Theorem would guarantee that $$7^{1734250} \equiv 1\pmod{1734251}$$ which is clearly not the case.

Thus, $1734251$ is not prime, and instead must be a composite number.

5. 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.)

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