Binary numbers mod 3 without a calculator? Binary number mod 3. Find:
$1101101001010111010110111011111001_2 \bmod 3$
You may not use a calculator.
I know how to convert a small binary number, but I do not know what approach to take with a larger one like this? Any thoughts on how you would proceed?
 A: Note that $\,2\equiv -1\pmod 3\,$, so it follows that $\,2^n\equiv (-1)^n\pmod 3\,$, and binary numbers are just sums of powers of 2. Can you take it from there?
A: $2^{even}\equiv (-1)^{even} \equiv 1 \pmod 3$
$2^{odd} \equiv (-1)^{odd} \equiv -1 \pmod 3$.
So 
$1101101001010111010110111011111001_2 \pmod 3$...
Marking the odd powers in red and the evens in blue
$\color{red}1\color{blue}10\color{blue}1\color{red}10\color{red}100\color{blue}10\color{blue}10\color{blue}1\color{red}1\color{blue}10\color{blue}10\color{blue}1\color{red}10\color{red}1\color{blue}1\color{red}10\color{red}1\color{blue}1\color{red}1\color{blue}1\color{red}100\color{blue}1_2 \pmod 3$
That's $12$ to and even power and $10$ to an odd power.
So $\color{red}1\color{blue}10\color{blue}1\color{red}10\color{red}100\color{blue}10\color{blue}10\color{blue}1\color{red}1\color{blue}10\color{blue}10\color{blue}1\color{red}10\color{red}1\color{blue}1\color{red}10\color{red}1\color{blue}1\color{red}1\color{blue}1\color{red}100\color{blue}1_2 \pmod 3$
$\equiv \color{blue}{12}-\color{red}{10} \equiv 2\pmod 3$
Note that if you have $11$ next to each other that's an even and an odd and they cast each other out.
