When Is Reduction Modulo N Helpful?

Reducing in modulo $n$ is very helpful in some problems. Let's look at an example:

Example 1: Find the remainder when $(7)^{123874}(19)^{2947387}$ is divided by $6$.

This problem appears quite scary. If you typed it on your calculator, you would probably get an overflow, so don't try it. Instead, let's approach it using modulo $6$. If we take $7 \pmod{6}$, we get one. This means that every single $7$ is congruent to a $1$ in our expression! Similarly, $19\equiv 1\pmod{6}$, so every $19$ also becomes a $1$! This means our entire expression is congruent to $$1^{123874}\cdot 1^{2947387}\equiv \boxed{1}\pmod{6}.$$ Yay! We're done!

Unluckily, not all problems reduce this easily.

Example 2: Find the remainder when $(7)^{16}(3)^{33}$ is divided by $5$.

Although the numbers are not quite as large as the previous problem, this example requires a bit more thinking. One clever approach is to combine the $7$'s and $3$'s like this: $$(7)^{16}(3)^{33}=(7)^{16}(3)^{16}(3)^{17}=(21)^{16}(3)^{17}.$$ Now we can perform a similar trick as the previous problem. We know $21\equiv 1\pmod{5}$, hence $$(21)^{16}(3)^{17}\equiv (1)^{16}(3)^{17}\equiv 3^{17}\pmod{5}.$$ Uh oh, what do we do now? Let's try to find a way to reduce this. We can separate $3^{17}$ into $3\cdot 3^16=3\cdot 9^8$, and since $9\equiv 4\equiv -1\pmod{5}$, we can substitute and arrive at $$3\cdot (-1)^8\equiv 3\cdot 1\equiv \boxed{3}\pmod{5}.$$

Time for one last example!

Example 3: Prove that for any odd prime $p$, $26p^2+1$ is composite.

Although this problem is significantly harder than the previous two, it uses the simple idea of reduction (and a bit of clever thinking).

Let's first show that if $p=3$, then the expression is composite. Plugging $3$ in, we get $26\cdot 3^2 +1=235\equiv 0\pmod{5}$. Easy.

Now let's show that any prime $p>3$ is divisible by $3$. We know that $26p^2\equiv 2p^2\pmod{3}$ (there's our reduction), so our expression simply becomes $2p^2+1$. Now for some casework!

Case 1: $p\equiv 1\pmod{3}$. Then we get $2\cdot 1^2+1=3\equiv 0\pmod{3}$ and we are done here.

Case 2: $p\equiv 2\pmod{3}$. Therefore our expression becomes $2\cdot 2^2+1=9\equiv 0\pmod{3}$ and we are done here as well.

There is no third case because $p>3$, so therefore $26p^2+1$ is composite for all primes $p$.

Reducing using modulo $n$ is very helpful when you need to find a remainder, or simply anything related to remainders and divisibility that consist of large numbers.

The explanation by Mr.Kevin is quite lucid. I would like to show a result I obtained while solving a problem.

I would be grateful if anyone could tell me if this is actually a theorem.

Problem: Find the remainder when 19^92 is divided by 92.

My method: 19^2 mod 92=85

19^92= (19^2)^46= 85^46

It is congruent to 85^46. I don’t have the feature in my device.

85^2 mod 92=49

85^46= (85^2)^23 =49^23

(49^2)^10 x 49^3

49^2 mod 92= 9

49^3 mod 92= 73

(49^2)^10= 9^10= (9^3)^3 x 9

9^3 mod 92= 85

Now multiply 9 by 73 obtained above.

9 x 73=657

657 mod 92=13

(9^3)^3 mod 92=85^3

85^3 mod 92= 25

Now multiply 25 and 13

25*13=325

325 mod 92=49

49 is the correct answer.

Maybe this method also works for other problems. Please check and leave a comment.

Thank you.