1
$\begingroup$

Again the problem is: Calculate the value of: $$\left(2^{156221} - 1\right) \bmod 9$$

I have no idea how to find a solution to this and need help urgently!! Thank you in advance.

  • 1
    The powers of $2$, modulo $9$, cycle nicely, with period $6$.2012-11-05
  • 0
    Why is this urgent?2012-11-05
  • 0
    I have an exam shortly on problems similar to this and I have gotten all of the material down except how to do problems like this.2012-11-05

4 Answers 4

3

HINT: $2^3=8\equiv-1\pmod9$. $156221=3\cdot52073+2$.

Added: Since $7\equiv1\pmod 3$, $7^{18621}-1\equiv1^{18621}-1\equiv0\pmod3$.

  • 0
    Can you expain this further? I'm really struggling with this.2012-11-05
  • 0
    @Anthony: $2^{156221}=2^{3\cdot52073+2}=(2^3)^{52073}\cdot2^2\equiv(-1)^{52073}\dot4\pmod9$; now what’s $(-1)^{52073}\bmod 9$?2012-11-05
  • 0
    Well (-1)^52073 is -1, so -1(mod9) is 10?2012-11-05
  • 0
    @Anthony: No, $-1\bmod 9=8$; $10\bmod 9=1$, not $-1$. So now you want $8\cdot 4\bmod 9$, which is ... ?2012-11-05
  • 0
    Would it be 41?2012-11-05
  • 0
    @Anthony: How can that be? When you reduce modulo $9$, you get a number in the set $\{0,1,2,3,4,5,6,7,8\}$. $8\cdot4=32$, and $32\bmod9=?$2012-11-05
  • 0
    So then my answer would be 5? I'm really struggling here.2012-11-05
  • 0
    @Anthony: There you go! Yes: $32\equiv5\pmod9$, because $32-5=27$ is divisible by $9$, so $32\bmod9=5$. And if you trace back through the calculations, you’ll see that this is the answer to the original question.2012-11-05
  • 0
    Can you explain where that 4 came from2012-11-05
  • 0
    I'm still not seeing where the answer is actually coming from could we try another example? (7^18621)-1 (mod3)2012-11-05
  • 0
    @Anthony: $2^2$. Look back to my first comment: $156221=3\cdot52073+2$, so we had $(2^3)^{52073}\cdot2^2$.2012-11-05
  • 0
    OK I see where the 4 comes from now2012-11-05
  • 0
    Would the answer the second example I posted, (7^18621)-2(mod3), sorry about my typo earlier, be 7^(3*6207)-2(mod3) which leads to an answer of 2?2012-11-05
  • 0
    @Anthony: Yes: you get $1-2=-1\equiv2\pmod3$.2012-11-05
0

Hint: Have you tried just listing $2^1, 2^2, 2^3, \ldots \pmod 9$ for a while? You might get some ideas.

  • 0
    I haven't could you elaborate more I have been staring at this problem for hours without being able to come up with a solution.2012-11-05
  • 0
    @Anthony: just calculate what I suggested, maybe in a spreadsheet. With a calculator, going up to $2^{20}$ should take a couple minutes, with a spreadsheet even less. What do you get?2012-11-05
  • 0
    I see that 2^6, 2^12 both work for 1(mod9) but my calculator is simple and won't give me values above that I am also unsure of how to do it in a spreadsheet in a timely fashion.2012-11-05
  • 0
    Would (2^5) be the answer?2012-11-05
  • 0
    If $2^6\equiv 1$, what can you say about $2^{6k+r}\bmod 9$?2012-11-05
  • 0
    I'm not sure I follow. Would 2^6k+r be equal to 2^6+156221?2012-11-05
  • 0
    @Anthony: Parentheses, please. 2^6k+r=(2^6)k+r but you mean 2^(6k+r). The point is that $2^{6k+r}=2^{6k}\cdot 2^r \equiv 2^r \pmod 9$2012-11-05
0

Hint $\rm\:mod\ 9\!:\ \color{#0A0}{2^6}\equiv \color{#C00}1\:\Rightarrow\: 2^{R+6Q}\equiv 2^R (\color{#0A0}{2^6})^Q\equiv 2^R \color{#C00}1^Q\equiv 2^R,\ $ so $\rm\ 2^N\equiv 2^{N\ mod\ 6}$

In the same way, one can always reduce exponents mod the order of the element being powered.

0

The problem has already been solved several times. Perhaps a marginally different point of view will be helpful. The hard part of the problem is to calculate $$2^{156221}\pmod{9}.$$

Let us calculate $2^n\pmod{9}$, starting at $n=0$.

We have $2^0\pmod{9}=1$, $2^1\pmod{9}=2$, $2^2\pmod{9}=4$, $2^3\pmod{9}=8$, and $2^{4}\pmod{9}=8$. This last one is because $2^4=16$, and $16\pmod{9}=7$.

Continue. Let us calculate $2^5\pmod{9}$. There are two ways to do this. We can calculate $2^5$, getting $32$, and then reduce modulo $9$, getting $5$. Or else we can just multiply the previous answer, which is $7$, by $2$, and reduce modulo $9$.

Now calculate $2^6\pmod{9}$. Again, we could calculate in two ways. Either find $2^6$, and reduce modulo $9$. Or else take the previous answer of $5$, multiply by $2$, and reduce modulo $9$. We get $1$.

Continue, or else imagine continuing. What is $2^7\pmod{9}$? Take the previous answer, which is $1$, multiply by $2$, and reduce modulo $9$. We get $2$. What is $2^8\pmod{9}$? Take the previous answer, multiply by $2$, and reduce modulo $9$. We get $4$. You should continue this process a few more times.

So the pattern of remainders that we get goes like this: $$1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,\dots.$$ Note that the remainder is $1$ when the exponent is any multiple of $6$.

Now divide $156221$ on your calculator. We get a quotient of $q=26036$ (not important) and a remainder of $5$. So $$156221=6q+5=156216+5.$$ Because $156216$ is a multiple of $6$, when we reach $n=156216$, our remainder is $1$, and we are starting the pattern of remainders all over again, and have to step forward until $216221$. That advances us forward by $5$ in our pattern, and there the remainder (by coincidence) is $5$.

More algebraically, $$2^{156221}=2^{6q+5}=(2^6)^q 2^5.$$ But $2^{6}$ gives remainder $1$ when you divide by $9$. Therefore so does $(2^6)^q$. So our remainder is the same as the remainder when $2^5$ is divided by $9$, and that is $5$.