2
$\begingroup$

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 $81$s 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.

$\endgroup$
4
  • 1
    $\begingroup$ It's a basic rule that, if $a\equiv a'$ and $b\equiv b'$, then $a+b\equiv a'+b'$ and $ab\equiv a'b'$. $\endgroup$
    – Bernard
    Commented Jan 14, 2018 at 23:07
  • 1
    $\begingroup$ Isn't this the multiplication rule: $81\equiv-1\pmod {41}$ and $81\equiv-1\pmod{41}$. Multiply both sides. $\endgroup$ Commented Jan 14, 2018 at 23:07
  • $\begingroup$ @JyrkiLahtonen - Ah yeah, I see it now! $a\equiv b \mod 41 \ \wedge \ c\equiv d \mod 41 \ \Rightarrow \ ac \equiv cd \mod 41$ where $a=c=81 \ \wedge \ b=d=(-1)$. $\endgroup$
    – Alec
    Commented Jan 14, 2018 at 23:11
  • 1
    $\begingroup$ Correct. ${}{}{}$ $\endgroup$ Commented Jan 14, 2018 at 23:22

1 Answer 1

1
$\begingroup$

@JyrkiLahtonen's comment led me to the right answer, and I'm just posting it here for the sake of having something to accept, since it went overnight without being posted.

From $$2^{20} \equiv 81 \cdot 81 \pmod{41}$$ we can use the rule stating that $$a\equiv b \pmod n \ \ \wedge \ \ c\equiv d \pmod n \ \ \Rightarrow \ \ ac \equiv bd \pmod n$$

In this case, we have $$81\equiv -1 \pmod{41} \ \ \wedge \ \ 81\equiv -1 \pmod{41} \ \ \Rightarrow \ \ 81\cdot81 \equiv (-1)(-1) \pmod{41}$$

with $a=c=81$ and $b=d=-1$ such that $$2^{20} \equiv 81\cdot 81 \equiv(-1)(-1) = 1 \pmod{41}$$ finishing the problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .