Exercises - Fast Exponentiation and Fermat's Little Theorem

  1. Find a number $a$ where $0 \le a \lt 73$ and $a \equiv 9^{794}\pmod{73}$  

    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. Solve $x^{86} \equiv 6 \pmod{29}$  

    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. The statement $7^{1734250} \equiv 1660565\pmod{1734251}$ is true. Can you conclude 1734251 is a composite number?  

    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. Verify using fast exponentiation that the congruence $$129^{64026} \equiv 15179\pmod{64027}$$ is true. 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.)

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