Please Login to access more options.

Problem 17(Computing Powers Modn Conjecture)

We need to be able to compute $a^k\pmod n$.

  1. Compute $2^k\pmod 5$ for $k=1,2,3,4,5,6,7$. What pattern do you see. What is $2^k\pmod 5 $ for $k=257$ and for $k=49827512$.
  2. Compute $5^k\pmod {11}$ for $k=1,2,3,4,5,6,7,8,9,10,11,12$. Can you discover a pattern. What if $k=3047$ or $k=478209183234$?
  3. Make a conjecture about $a^k\pmod n$. Come up with a different example to back your conjecture.

Solution

1. The following table displays values of $2^k\mod{5}$ given a few values of $k$. $$\begin{array}{c|c} k&2^k\mod{5}\\ \hline 0&1\\ 1&2\\ 2&4\\ 3&3\\ 4&1\\ 5&2\\ 6&4\\ 7&3\\ 8&1 \end{array}$$

Note there is a cyclic pattern. We can use this pattern to determine the value of $2^k\mod{5}$ for large values of $k$. We will first show that given $k=4q+r$ for some $q>0$ and $0\leq r<4$, we have $2^k\mod{5}=2^{4q+r}\mod{5}\in\{1,2,3,4\}$. Without loss of generality, let $r=1$. We know for $k=4(0)+1$ we have $2^k\mod{5}=2$. Now suppose for some $q>0$ we have $2^{4q+1}\mod{5}=2$. We compute $$\begin{align} 2^{4(q+1)+1}\mod{5}&=2^{4q+4+1}\mod{5}\\ &=2^{4q+1}2^4\mod{5}\\ &=(2^{4q+1}\mod{5})(2^4\mod{5})\mod{5}\\ &=(2)(16\mod{5})\mod{5}\\ &=(2)(1)\mod{5}\\ &=2\mod{5}\\ &=2 \end{align}$$ Thus, by mathematical induction we know $2^k\mod{5}=2$ for all $k=4q+1$ given $q>0$. Thus by definition of modular arithmetic we know $2^k\mod{5}=2$ for $k$ such that $k\mod{4}=1$. A similar process can be shown for $r=0,2,$ and $3$. The table below summarizes the information, as well as explores two cases of large values of $k$.

$$\begin{array}{c|c|c} k&k\mod{4}&2^k\mod{5}\\ \hline 4q+0&0&1\\ 4q+1&1&2\\ 4q+2&2&4\\ 4q+3&3&3\\ \hline 257&3&3\\ 49827512&0&1 \end{array}$$

2. In a similar manner as above, the following table displays values of $5^k\mod{11}$ for a few values of $k$. $$\begin{array}{c|c} k&5^k\mod{11}\\ \hline 1&5\\ 2&3\\ 3&4\\ 4&9\\ 5&1\\ 6&5\\ 7&3\\ 8&4\\ 9&9\\ 10&1\\ 11&5\\ 12&3\\ \end{array}$$

Note the cyclic pattern with 5 elements. We can use this pattern to determine values of $5^k\mod{11}$ for large values of $k$. We will first show that given $k=5q+r$ for some $q>0$ and $0\leq r<5$, we have $5^k\mod{11}=5^{5q+r}\mod{11}\in\{1,3,4,5,9\}$. Without loss of generality, let $r=3$. We know for $k=4(0)+3$ we have $5^k\mod{11}=4$. Now suppose for some $q>0$ we have $5^{5q+3}\mod{11}=4$. We compute $$\begin{align} 5^{5(q+1)+1}\mod{11}&=5^{5q+5+1}\mod{11}\\ &=5^{5q+1}5^5\mod{11}\\ &=(5^{5q+1}\mod{11})(5^5\mod{11})\mod{11}\\ &=(4)(3125\mod{11})\mod{11}\\ &=(4)(1)\mod{11}\\ &=4\mod{11}\\ &=4 \end{align}$$ Thus, by mathematical induction we know $5^k\mod{11}=4$ for all $k=5q+3$ given $q>0$. Thus by definition of modular arithmetic we know $5^k\mod{11}=4$ for $k$ such that $k\mod{5}=3$. A similar process can be shown for $r=0,1,2,$ and $4$. The table below summarizes the information, as well as explores two cases of large values of $k$.

$$\begin{array}{c|c|c} k&k\mod{4}&2^k\mod{5}\\ \hline 5q+0&0&1\\ 5q+1&1&5\\ 5q+2&2&3\\ 5q+3&3&4\\ 5q+4&4&9\\ \hline 3047&2&3\\ 478209783234&4&9 \end{array}$$

3. The last two parts displayed cyclic patterns for $a^k\mod{n}$, so one conjecture that can be made is that $a^k\mod{n}$ for any $n$ and $a<n$ will eventually form a cyclic pattern.

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.