Modular maths: How do I find the remainder?

Question

How do I find the remainder of $5^{22} \pmod{25}$?

And also how do I find the remainder of $3^{16} + 7 \pmod{5}$?

Answer 1

I these situations you can apply Fermat's little theorem. It states that if $p$ is a prime that is coprime to $a$, then $a^{p - 1} \equiv 1 \mod p$. For example, in your first case this means $5^{22} = 5^{16} 5^6 \equiv 5^{16} \pmod{7}$.

If you apply this rule multiple times, you can significantly reduce the complexity of this problem. If you apply euclidean division to the exponent and the modulus, you can simplify this to a single step. I hope you can take t from here.

Answer 2

Try to see which power of $5$ can give $1$ or $-1$ modulo $7$. This will reduce your computations quite significantly. For example, $5^2 \equiv 4 \pmod{7}$ so $5^3 \equiv 20 \equiv 6 \equiv -1 \pmod{7}$. Thus $$5^{22} \equiv 5^{21} \cdot 5 \equiv (5^{3})^7 \cdot 5 \equiv -5 \equiv 2 \pmod{7}$$

Answer 3

$$5^{22}=5\cdot 5^{21}=5\cdot (5^3)^7\equiv 5\cdot (-1)^7\equiv -5\equiv 2 (mod7).$$

Do the second in a similar way.

Answer 4

Well $5^3 = 125 \equiv -1 \pmod {7}$ because $7 \mid 125 - (-1)$

And since ${5}^{3} \equiv -1 \pmod {7}$ then ${(5^3)}^{7} \equiv (-1)^7 \pmod{7}$ and so $5^{21} \equiv -1 \pmod{7}$ and so $5^{22} \equiv -5 \pmod 7$. But since $-5 \equiv 2 \pmod 7$ then $5^{22} \equiv 2 \pmod 7$ as well