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.
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.
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$.
Hint: Have you tried just listing $2^1, 2^2, 2^3, \ldots \pmod 9$ for a while? You might get some ideas.
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$.