# Problem in finding the inverse element in modular arithmetic

I'm new to modular arithmetic but it still is something that I think is pure mathematics that I don't get.

I have this problem 3 * d ≡ 1 mod 13. So I need to find the d which is the inverse of 3. I did find a solution that I understand:

3 * d ≡ 1 mod 13

Which can be written

3^(13-2) % 13 = 9 or pow(3, 13-2, 13) = 9


So that I understand, and this is the accepted answer. But my thought was a bit different:

My thought to calculate d was to divide both sides by 3 which gives us d = (1/3) * 1 mod 13

And that in python can be written pow(3, -1, 13) or pow(3, -1) % 13 which also gives 9 as a result.

But at first, I thought that it was wrong. How this calculation can give us 9? I mean 3^-1 = 1/3. And 1/3 mod 13 = 1/3.

In which part of my thinking am I wrong?

Notation: for integer $$m>0$$, we write $$u\equiv v\pmod m$$ when $$u-v$$ is a multiple of $$m$$. We write $$u=v\bmod m$$ when additionally $$0\le u. In the former, $$\pmod m$$ qualifies the congruence sign(s) $$\equiv$$ on its left. In the later, $$\bmod$$ is an operator.

The modular modular inverse $$x$$ of integer $$a$$ modulo integer $$m>1$$ is defined when $$\gcd(a,m)=1$$. It then is the uniquely defined integer $$x$$ such that $$0 and $$a\,x\bmod m=1$$. It's noted $$x=a^{-1}\bmod n$$. It holds $$3^{-1}\bmod13=9$$ because $$\gcd(3,13)=1$$, and $$0<9<13$$, and $$3\times9=27$$, and $$27-1$$ is a multiple of $$13$$.

A general method to determine if $$a^{-1}\bmod n$$ is defined, and compute it, is to find $$x$$, $$y$$, $$g$$ for the Bézout identity $$a\,x+m\,y=g$$. The inverse $$a^{-1}\bmod n$$ is defined when the Greatest Common Divisor $$g=1$$, and then it holds $$a\,x\equiv1\pmod m$$, and therefore $$a^{-1}\bmod n\,=\,x\bmod n$$.

One method to compute $$x$$, $$y$$, $$g$$ for the Bézout identity $$a\,x+m\,y=g$$ is the extended Euclidean algorithm. When computing the modular inverse, we do not need $$y$$, which allows to maintain two less variables. This slight variant deals only with non-negative quantities.

In modern Python, when operator pow has three integer parameters, and the second (the exponent) is a negative integer, and the third is greater than one, it's used a method equivalent to the above to determine if the multiplicative inverse exists; in the affirmative it's computed and raised to the absolute value of the exponent modulo the modulus. That's why pow(3, -1, 13) yields 9. That's the generic method to compute the multiplicative inverse in modern Python.

When $$m$$ is prime, $$\gcd(x,m)=1$$ is the same as $$x\bmod m\ne0$$. And when that holds, Fermat Little Theorem tells that $$x^{m-1}\bmod m=1$$. It follows that then, the modular modular inverse $$y$$ of $$x$$ is $$x^{m-2}\bmod m$$. This is why pow(3, 13-2, 13) also yields the multiplicative inverse of $$3$$ modulo $$13$$.

Note: pow(3, -1) % 13 asks Python to compute $$\frac13$$, that is $$0.3333\ldots$$, then reduce it modulo $$13$$, which leaves it unchanged.

Note: Python defines pow(u,e,1) to be 0, and handles negative modulus so that pow(u,e,m) is -pow(u,e,-m).