computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc... by hand

Question

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for efficiently solving such problems by hand.

Answer 1

There are a lot of tricks. A useful one for your problems is Fermat's Theorem, which says that if $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$.

We look for example at $2^{170}$ modulo $19$. Note that $170=9\cdot 18+8$. Thus $$2^{170}=(2^{18})^9 2^8\equiv 1^9\cdot 2^8\equiv 2^8\pmod{19}.$$

The number $2^8$ is easy to handle. But even here there are tricks, which, for larger numbers, cut down enormously on computation time. You might want to look up the very useful binary method for modular (and other) exponentiation. Our number $2^8$ provides a too simple example. Note that $2^4=16\equiv -3\pmod{19}$. So $2^8\equiv (-3)^2\pmod{19}$.

Answer 2

For those specific examples, Fermat's Little Theorem is the way to go. It states that if $p$ is prime and $gcd(a,p) = 1$, then $$a^{p-1} \equiv 1 \bmod{p}$$.

For the more general case where the modulus is not prime, then you have Euler's theorem, which states that if $gcd(a, m) = 1$, then $$a^{\phi(m)} \equiv 1 \bmod{m}$$ where $\phi$ is Euler's totient function.

Answer 3

$$2^9\equiv-1(mod)19$$ $\implies$ $$2^{162}\equiv1(mod)19$$ $\implies$ $$2^{170}\equiv256(mod)19=9(mod)19$$ Also $$3^3\equiv 2^3(mod)19$$ So $$3^{63}\equiv2^{63}(mod)19=-1(mod)19$$ So $$2^{170}+3^{63}\equiv 8(mod)19$$