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.

  • 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
    @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
    @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$.