Prove that it is divisible by 3. Prove that the product of the last digit of the number $2^n$ and of the sum of all its digits but the last is divisible by 3.
I have no idea how to solve it. Please help. Question from Mathematical circles (Russian Experience).
 A: The last digit cycles through $2,4,8,6$ and correspond to when the remainder of $n$ divided by $4$ is $1,2,3,0$.
Therefore, for $n$ multiple of $4$, you are done, since $6$ is divisible by $3$.
The sum of the digits of a number leaves the same remainder after division by $3$ as the original number. This is because $$a_0+10a_1+...+10^ka_k=(a_1+...+a_k)+9(a_1+11a_2+...+11...1a_k)$$
The remainder of $2^n$ after division by $3$ is $(-1)^n$ since $2^n=(3-1)^n$.
Therefore the sum of the digits except the last leaves remainder equal to $(-1)^n$ minus the last digit. This is, $(-1)^n-2=3, (-1)^n-4=-3,(-1)^n-8=-9$ for $n$ leaving remainders $1,2,3$ after division by $4$, respectively.
Therefore, the sum of all the digits but the last is divisible by $3$ in all remaining cases.
A: I'm explaining solution from the book as I've read it. I assume that you didn't understand the solution
You've to find out pattern in remainders of two cycles.  

Here is the pattern of remainders of $2^n$ when divided by $3$.
$2,1,2,1,2,1,2,1...$
  And here is pattern of remainders when last digit of $2^n$ is divided by $3$.
$2,1,2,0,2,1,2,0...$ 

You can neglect the cases where the remainders are $0$ because they indeed will be divisible because remainder is $0$.
For the rest the difference of remainders is $0$ which means the number left after removal of last digit is divisible by $3$.
