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

Question

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?

Answer 1

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.$

Answer 2

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$$

Answer 3

No one has mentioned that for any fixed N, {a | gcd(a,N)=1} forms a group. Closure under multiplication is easy to see with elementary manipulations. The inverses usually are explained using the Euclidean Algorithm. At the very least if you want to understand inverses in modular systems, this desire could sustain you while you read/hear an explanation of the Euclidean Algorithm.