Why does (1/3) mod 3016 = 2011?

So I am taking a class where we are working on a cryptography section. Basically, the course says that: $$\frac 1 3 \mod(3016) = 2011$$ or when run through Python - modified with SciPi: $$\frac 1 3 \,\%\, 3016 = 2011$$

I don't understand how or why this happens. Does anyone know why the modulo division would produce this result?

Solution 1:

What you're calling $\dfrac 13$ is just the multiplicative inverse of $3$ mod $3016$. You can easily verify that $2011$ is the multiplicative inverse of $3$. $$3\cdot 2011 = 6033 = (2\cdot 3016)+1$$

Solution 2:

One can in fact use fractions in modular arithmetic, as long as one only uses fractions with denominator coprime to the modulus. For these fractions the usual grade school arithmetic of fractions holds true. For example, let's consider your problem.

$\quad {\rm mod}\ 3n\!+\!1\!:\,\ 3n\!+\!1\equiv 0\ $ so $\ 1 \equiv 3(-n)\ $ therefore $\ \dfrac{1}3 \equiv -n \equiv 2n\!+\!1.\ $

$\quad$ In your case $\ 3n\!+\!1 = 3016\,$ so $\,n=\dfrac{3015}3 = 1005,\,$ so $\,\dfrac{1}3\equiv 2n\!+\!1 = 2011$

The notation $\,1/3\,$ means $\,3^{-1},\,$ i.e. a root of $\,3x\equiv 1\pmod{3n\!+\!1}.\,$ The inverse exists and is unique because $\,\gcd(3,3n\!+\!1)=\gcd(3,1)=1,\,$ so by Bezout's identity for the gcd we have

$\quad \text{for some } j,k\!:\ \ 3j+(3n\!+\!1)k = 1\ \Rightarrow\ {\rm mod}\ 3n\!+\!1\!:\ 3j\equiv 1\ \ {\rm so}\ \ j\equiv 3^{-1}\! \equiv 1/3$

and inverses are always unique. Hence the notation $\,1/3\, :=\, 3^{-1}\,$ is well-defined.

Remark $\ $ Generally we can use the extended Euclidean algorithm to compute modular inverses. The above is essentially an optimization for the case when it terminates in a single step, i.e. inverting $\,a\,$ modulo $\,m = an+1,\,$ i.e. when $\,a\mid m-1.$