Please Login to access more options.

Problem 26 (Powers With Modular Arithmetic)

  1. We know that $481\mod {483} =(-2)\mod {483}$. Use this fact to quickly compute $481^2\mod{483}$ without a calculator. [How can you use the $-2$ to simplify this?]
  2. Using the same idea, what is $481^{3}\mod{483}$ and $481^4\mod{483}$? You should be giving a positive integer less than 483 for all your answers.
  3. Explain why $12\cdot 16 \mod 17$ is the same as $(-5)(-1)\mod 17$.
  4. Now compute $14^k \pmod {17}$ without a calculator for as many values of $k$ as needed until you find a repeating pattern. See the hint below.

Let me give you a suggestion. Rather than trying to compute $14^4$, instead first compute $14^2$ by considering $(-3)^2$. To compute $(14)^3$, instead use the product $(14)^2(14)=(9)(-3)=(-8)(-3)$. Use your work from the previous power to figure out the next power. If you try to do this with brute force, it gets outrageously large really fast. If you swap from positive to negative values when the numbers get large (above 8), you should be able to do this without ever needing long division. You should find that no product ever gets above 24.

The following Sage code will compute powers with modular arithmetic. You are welcome to check your answers with this, but the whole point to the problem is to learn how to simplify the computations by hand. To compute $a^m\mod n$ you would write "power_mod($a$,$m$,$n$)." 

power_mod(481, 4, 483)

Solution

Recall from problem 25 that $((a \mod n)(b\mod n))\mod n = (ab)\mod n$. For part 1 we wish to find $481^2\mod 483$. We compute $$\begin{align} 481^2\mod 483 &= (481 \cdot 481) \mod 483\\ &=((481 \mod 483)\cdot (481\mod 483))\mod 483\\ &=((-2 \mod 483)\cdot (-2 \mod 483))\mod 483\\ &=(-2)^2 \mod 483\\ &= 4 \mod 483\\ &= 4. \end{align}$$

Next up is $481^3\mod 483$. We compute $$\begin{align} 481^3\mod 483 &= (-2)^3 \mod 483\\ &= -8 \mod 483\\ &= 475. \end{align}$$

Why does $12\cdot 16 \mod 17 = (-5)(-1)\mod 17$? Remember the result from problem 25. We compute $$\begin{align} 12\cdot 16 \mod 17 &= ((12\mod 17)(16\mod 17))\mod 17\\ &=((-5\mod 17)(-1\mod 17))\mod 17\\ &=(-5)(-1)\mod 17. \end{align}$$

Finally, we will use this result to find a pattern for $14^k \mod 17$. We compute $$\begin{align} 14^1\mod 17 &= (-3)^1 \mod 17\\ &= 14,\\ 14^2\mod 17 &= (-3)^2 \mod 17\\ &= 9 \mod 17\\ &= 9,\\ 14^3\mod 17 &= (14^2 \cdot 14)\mod 17\\ &= 9\cdot -3 \mod 17\\ &= -8\cdot -3 \mod 17\\ &= 24 \mod 17\\ &= 7,\\ 14^4 \mod 17 &= 14^3\cdot 14 \mod 17\\ &= 7\cdot -3 \mod 17\\ &= -21 \mod 17\\ &= -4 \mod 17\\ &= 13.\\ \end{align}$$

The process follows this pattern $14^k\mod 17= ((14^{k-1}\mod 17)\cdot -3)\mod17)$, which we follow until we arrive upon the list in the proceeding table. $$\begin{array}{|c|c|c|c|c|c|c|c|} k & 14^k\mod 17 & k & 14^k\mod 17 & k & 14^k\mod 17 & k & 14^k\mod 17\\ \hline 1 & 14 & 5 & 12 & 9 & 3 & 13 & 5\\ 2 & 9 & 6 & 15 & 10 & 8 & 14 & 2\\ 3 & 7 & 7 & 6 & 11 & 10 & 15 & 11\\ 4 & 13 & 8 & 16 & 12 & 4 & 16 & 1 \end{array}$$ The next result will restart the pattern all over again, and we will cycle through the same numbers. Thus the cycle passes through each number less than $17$. $\square$

Tags

Change these as needed.

  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.