0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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<m$. 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<x<m$ 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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.