How to find a remainder of $\frac{3^{208}}{2}$ without an calculator?

Question

$$\frac{3^{208}}{2^{109}}\text{?}$$ I wasn't able to get the exact question source but I believe there's been a typo. Should be something like$3^{208}$ mod 2 which has been clarified in many other questions. Deeply sorry for the confusion! Thank you all!!

Answer 1

I cannot see any simple way of doing this. For one, the modulus you have is absolutely huge : you cannot do elementary calculations with $2^{109}$.

Same exponentials may help you estimate the quotient : in no way does it help you find the remainder.

One simplification you probably may have considered, is that $(2+1)^{208} = \sum_{i=0}^{208} \binom {208}i 2^i$. Since after $i=109$, every term is a multiple of $2^{109}$, you can eliminate these. However, that still leaves the terms $i=0$ to $108$, which is quite a task!(You could argue, a harder task than the previous one).

$\color{red}{275886531195588709026997180223041}$

With a calculator, of course.

EDIT : If this is from a GRE test, then that is somewhat surprising. I request you to post this exact text for us, so that then I can appropriately edit this answer.

EDIT : If the question really was $3^{208} \mod 2$, then well, $3^{208}$ is odd, obviously, so there.