Modular Arithmetic Substitution Problem in Multiplication

44 Views Asked by At

99 ≡ 387,420,489 ≡ 5 (mod 22)

However I have tried to reach this result using the following steps and I got it wrong:

99 ≡ 93 x 93 x 93 ≡ 729 x 729 x 729 ≡ 3 x 3 x 3 ≡ 18 (mod 22)

I can use this substitution in sum operations, but is it correct to say that I cannot do the same for multiplications?

2

There are 2 best solutions below

0
On BEST ANSWER

$3^3 = 27 \equiv 5 \,(\text{mod}\,\,22)$

1
On

Here's another way to go about it: $$\varphi(22)=10;1\equiv 9^{10}=9\cdot9^9 \pmod {22}\\5\cdot 9=45=22\cdot2+1\equiv 1 \pmod {22}$$ This uses Euler's totient theorem. most substitutions are still valid in modular arithmetic. as it's an extension of normal arithmetic.