Tuesday, January 29, 2019

elementary number theory - Reducing products in modular arithmetic

During an effort to show that 2^{20} \equiv 1 \mod{41}, I have done the following:


2^{20} = \left(2^5\right)^4 = 32^4


Since 32 \equiv -9 \mod{41}, we get 32^4 \equiv (-9)^4 = 81\cdot81 \mod 41


From here, I know that I can reduce the 81s, such that I get 2^{20} \equiv (-1)(-1) \mod 41, so I can solve the problem, but I can't connect this reduction to a particular rule of modular arithmetic.


Question


From 2^{20} \equiv 81 \cdot 81 \mod 41, which rule is it that states that the 81s can be reduced to their individual congruences, modulo 41? In other words, why may I reduce them to (-1)(-1)?



I'm familiar with some of the rules, like the basic addition/subtraction/multiplication/power ones, but if it's one of these, I don't quite see the connection.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...