Computing elliptic curve finite field modular arithmetic

Question

Sorry for asking such a n00b question but what does the following compute to?

$s=(3(16)^2+9)\cdot(2\cdot 5)^{-1}\bmod{23} = 11$

In an online response here, I saw this computes to $11$ but whenever I do the computation I get $8.7$. Can someone show me how to get $11$?

Answer 1

As $\displaystyle2\cdot12-23=1,2\cdot12\equiv1\pmod{23}\iff 2^{-1}\equiv12$

As $\displaystyle5\cdot9-23\cdot2=-1\pmod{23}\iff5\cdot9\equiv-1\pmod{23}\iff5^{-1}\equiv-9\equiv14$

$\displaystyle\implies (2\cdot5)^{-1}\equiv2^{-1}\cdot5^{-1}\equiv12\cdot14\pmod{23}\equiv7$

Answer 2

Doing arithmetic modulo $\;23\;$ all through:

$$\begin{align*}16&=-7\implies 16^2=7^2=3\implies 3\cdot(16^2)=9\\{}\\ 2\cdot5&= 10\;\;,\;\;10\cdot 7=1\implies10^{-1}=7\end{align*}$$

Thus

$$s=\left(3\cdot(16)^2+9\right)\cdot(2\cdot5)^{-1}=(9+9)\cdot 7=(-5)\cdot 7=-12=11$$

Answer 3

It seems that you have performed the following computation

$$ {\rm mod}\ 23\!:\,\ (3(16)^2\!+9)\cdot (2\cdot 5)^{-1} = \dfrac{777}{10} = 77 + \dfrac{7}{10}\equiv 8 + \dfrac{7}{10} = 8.7$$

Finishing we have $\ \dfrac{7}{10}\equiv \dfrac{30}{10}\equiv 3,\ $ therefore $\ 8+ \dfrac{7}{10} \equiv 8+ 3 \equiv 11,\,$ which is correct.

However, unless one has mastered modular arithmetic, it is not advisable to use decimal notation to denote fractions when performing modular arithmetic. This might cause teachers to think that you have not correctly grasped the notion of modular inverses.

Generally, the use of fractions in modular arithmetic is valid only when the denominator is invertible, i.e. coprime to the modulus. Otherwise the quotient need not be unique, for example mod $\rm\:10,\:$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}\,$ cannot designate a unique solution of $\,4x\equiv 2.\,$ Indeed, the solution is $\rm\:x\equiv 1/2\equiv 3\pmod 5,\,$ which requires canceling $\,2\,$ from the modulus too, since $\rm\:10\:|\:4x-2\iff5\:|\:2x-1.\:$

The grade-school rules of fraction arithmetic apply universally (i.e. in all rings) where the denominators are invertible. This fundamental property will be clarified conceptually when one learns in university algebra about the universal properties of fractions rings and localizations.