Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

4 Answers 4

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

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.