# Modulo arithmetic: finding “c” when result of right-hand side expression is a float [duplicate]

In my series of questions on modular arithmetic, I stumbled upon cases where normal textbooks don't explain much.

Now my problem is to find $$c$$ when the expression to be solved (right-hand side) includes multiplication and resolves to floating point numbers:

$$c ≡ a^{5} ∗ b^{−3} \mod 43$$ given that $$0 \leq c < 43$$ and, $$a ≡ 27 \mod 43$$ and $$b ≡ 19 \mod 43$$. ($$a$$ and $$b$$ are integers).

By solving the right-hand side, by replacing the values for of a and b:

$$c ≡ 27^{5} ∗ 19^{−3} \mod 43 = 1423.768 mod 43$$

If I compute this on a calculator, gives: $$4.7680$$

$$c$$ must be an integer, should this be approximated to $$5$$? How should I approach such cases when right-hand side resolves to float numbers and thus the resulting value of the variable of interest?

All inputs are valuable. As mentioned, it's new to me and I am trying hard to understand it. Thank you.

• You can't do modular arithmetic this way, it will give you the wrong answers - the rounding involved in floating point is not well behaved at all from the perspective of modular arithmetic. It is a funny coincidence that $5$ appears to be the correct value here. – user208649 Sep 29 '20 at 20:11

In modular arithimetic $$k^{-n}$$ is NOT a rational fraction.

$$k^{-1}= m$$ is the multiplicative inverse of $$k$$; that is $$k^{-1}$$ is the INTEGER class $$m$$ so that $$mk \equiv 1 \pmod {..}$$. And $$k^{-n} = (k^{-1})^n$$ is the integer class so that $$k^{-n}k^n \equiv 1$$.

So if $$b \equiv 19\pmod {43}$$ then $$b^{-1}= m$$ is the $$m$$ so that $$19m \equiv 1\pmod {43}$$.

$$43 = 2*19 + 5$$ so $$5 = 43 -2*19$$

$$19 = 3*5 + 4$$ so $$4 = 19-3*5=19-3(43-2*19)=7*19 - 3*43$$

$$5 = 4 + 1$$ so $$1 = 5-4 = (43-2*19) - (7*19 - 3*43)= -9*19+4*43$$

So $$1 \equiv -9\cdot 19 \pmod {43}$$

So $$b^{-1}\equiv 19^{-1} \equiv -9 \equiv 34 \pmod{43}$$

We can verify: $$19\cdot 34 \equiv 1 \pmod {43}$$ as $$19*34=1 + 15*43$$.

And $$b^{-3}\equiv 19^{-3} \equiv 34^3 \pmod {43}$$.

So $$c \equiv a^5 b^{-3} \equiv 27^5\cdot 34^3 \pmod {43}$$.

Now here's a trick. I notice that $$34 \equiv -9 \pmod {43}$$ so

$$c \equiv 27^5 \cdot 34^3 \equiv$$

$$3^{15}\cdot (-9)^3 \equiv - 3^{15}9^3 \equiv$$

$$-3^{15}3^{6}\equiv -3^{21} \pmod 43$$.

Now $$3^4 \equiv 81 = 86 - 5\equiv -5\pmod{43}$$ so $$3^7\equiv 3^4\cdot 3^3\equiv -5*27\equiv -135\equiv -135 + 4*43 \equiv 37 \pmod {43}$$.

so $$-3^{21} \equiv -(3^7)^3 \equiv -37^3\equiv -(-6)^3\equiv 6^3\equiv 2^3*3^3\equiv 8*27 \equiv 216 \equiv 1+5*43\equiv 1 \pmod {43}$$.

So $$c =1$$.

$$\begin{array}{rr|rrl} & 43 & 1 & 0 \\ -2 & 19 & 0 & 1 & (43 - 38 = 5, \, 1-0=1, \, 0-2=-2)\\ \hline -4 & 5 & 1 & -2 & (19 - 20 = -1, \,0-4 = -4, \, 1+8 = 9) \\ & -1 & -4 & 9 \\ \hline \end{array}$$

So \begin{align} -1 = -4(43) + 9(19) & \implies 1 = 4(43) - 9(19) \\ & \implies 1 \equiv -9(19) \pmod{43} \\ & \implies 19^{-1} \equiv -9 \pmod{43} \\ \end{align}

Given $$a = 27$$ and $$b=19$$, then $$c \equiv a^5 \cdot b^{-3} \equiv 27^5 \cdot 19^{-3} \equiv 1\pmod{43}$$