Use the fact that $\displaystyle (2/p)=1$ for $\displaystyle p\equiv\pm 1 \mod 8$ and $\displaystyle (2/p)=-1$ for $\displaystyle p\equiv\pm 3 \mod 8$.
Out of curiosity, how would you evaluate linear congruences like
$\displaystyle 2^{43112609} - 1 \equiv a \mbox{ (mod 8)} $if you have BIG numbers, without a calculator or computer?
Out of curiosity, how would you evaluate linear congruences like
$\displaystyle 2^{43112609} - 1 \equiv a \mbox{ (mod 8)} $if you have BIG numbers, without a calculator or computer?
Think about it : $\displaystyle 2^n \equiv 0 \mod 8$ for $\displaystyle n \geq 3$. So $\displaystyle 2^{43112609} - 1 \equiv -1 \mod 8$.