| | |
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}$$
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}$$
Solve $x^{39} \equiv 3 \pmod{13}$
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.
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.)
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$$