# How do I find a value for $2^{156221} - 1\pmod 9$?

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.

-
The powers of $2$, modulo $9$, cycle nicely, with period $6$. – André Nicolas Nov 5 '12 at 21:10
Why is this urgent? – Did Nov 5 '12 at 21:19
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. – Anthony Nov 5 '12 at 21:21

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

-
Can you expain this further? I'm really struggling with this. – Anthony Nov 5 '12 at 21:26
@Anthony: $2^{156221}=2^{3\cdot52073+2}=(2^3)^{52073}\cdot2^2\equiv(-1)^{52073}\dot4\pmod9‌​$; now what’s $(-1)^{52073}\bmod 9$? – Brian M. Scott Nov 5 '12 at 21:34
Well (-1)^52073 is -1, so -1(mod9) is 10? – Anthony Nov 5 '12 at 21:41
@Anthony: No, $-1\bmod 9=8$; $10\bmod 9=1$, not $-1$. So now you want $8\cdot 4\bmod 9$, which is ... ? – Brian M. Scott Nov 5 '12 at 21:44
Would it be 41? – Anthony Nov 5 '12 at 21:57

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

-
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. – Anthony Nov 5 '12 at 21:10
@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? – Ross Millikan Nov 5 '12 at 21:13
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. – Anthony Nov 5 '12 at 21:15
Would (2^5) be the answer? – Anthony Nov 5 '12 at 21:16
If $2^6\equiv 1$, what can you say about $2^{6k+r}\bmod 9$? – Hagen von Eitzen Nov 5 '12 at 21:17

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.

-

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

-