How do I quickly find if a big number $\bmod n$ is odd or even? How do I quickly find if big number is even or odd?
For example I want to find if $17^{50}\mod 101$ even or odd ?
 A: For general numbers, you just divide by $2$. For the question you've asked, I'm assuming you're asking the the least positive residue of $17^{50} \bmod 101$ is odd or even. Since exponentiation is so fast in modular arithmetic, I would recommend simply computing $17^{50} \bmod 101$ through repeated squaring.
In this particular case, you can be a bit more clever if you know some elementary number theory. By Fermat's little Theorem, we know that $17^{100} \equiv 1 \pmod{101}$. As $101$ is prime, the only square roots of $1$ are $\pm 1$. So we have $17^{50} \equiv \pm 1 \pmod{101}$. Which one depends on whether or not $17$ is a quadratic residue mod $101$.
Using Legendre symbols, you can perform the sequence of operations
$$\newcommand{kron}[2]{\left( \frac{#1}{#2} \right)}
\kron{17}{101} = \kron{101}{17} = \kron{16}{17} = 1.$$
So $17$ is a square mod $101$ (so $17$ is not a primitive root), which means that $17^{50} \equiv 1 \pmod {101}$. So it's odd.
A: Convert $50$ to binary and read out its bits: $50 = 32+16+2$.
Compute successive squares of $17$ and keep a running product of those powers corresponding to the list of bits:  \begin{align}
    17^2 &\cong 289 \cong 87 \pmod{101}  &  17^2 &\cong 87 \pmod{101}  \\
    17^4 &\cong 87^2 \cong 95 \cong -6 \pmod{101}  \\
    17^8 &\cong (-6)^2 \cong 36 \pmod{101}  \\
    17^{16} &\cong 36^2 \cong 84 \pmod{101}  &  17^{16+2} &\cong 87 \cdot 84 \cong 36 \pmod{101}  \\
    17^{32} &\cong 84^2 \cong 87 \pmod{101}  &  17^{32+16+2} &\cong 36 \cdot 87 \cong 1 \pmod{101}  \text{,}
\end{align} and $1$ is odd.
The are other shortcuts, unfortunately, for odd modulus, they're not useful.  For instance, by Fermat's little theorem, we know, since $101$ is prime, $17^{100} \cong 1 \pmod{101}$, so $17^{50} \cong \pm 1 \pmod{101}$, but $1$ is odd and $-1 \cong 100$ is even, so this doesn't help much.
