19

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?

Zack
  • 293
  • 2
  • 7
  • What exactly do you mean run through python? That's not python code. – Random832 Apr 20 '15 at 05:25
  • The class I'm taking uses Sage Mathematics, which uses Python code. The code: x = (1 / 3) % 3016; print(x); prints out the value 2011, I thought I would just simplify that into one line. I mentioned it was 'ran through python' because I wasn't sure whether this was the actual 'math' answer, or if the Python programming language was just doing the math weird. – Zack Apr 20 '15 at 05:35
  • 3
    I don't know where you type that code into, but it's not the python interpreter (and therefore is not python code), since there's nothing in there to cause it to use the sage mathematics library rather than the standard int library. Python itself will give a result of either 0 or 0.33333333 depending on the version. – Random832 Apr 20 '15 at 05:44
  • Yes but my point is that python doesn't give 2011 as the result – Random832 Apr 20 '15 at 06:00
  • I looked it up and Sage says that it uses SciPi - http://www.scipy.org/, so I guess that is why it gives out 2011. – Zack Apr 20 '15 at 06:01
  • 9
    I can confirm that typing `(1/3)%3016` at the **sage** prompt returns 2011. But no way is this what plain Python gives you. Possibly sage modifies the definition of built-in operators, or performs some other magic, but in any case the question should state that 'sage' is used, not Python. For more information about where the computation actually takes place, try typing `(1/3)%3015` in sage instead. – Marc van Leeuwen Apr 20 '15 at 07:41
  • My answer at http://math.stackexchange.com/questions/1127483/how-to-make-sense-of-fractions/1127776#1127776 complements @Bye_World s answer here. – Ethan Bolker Apr 20 '15 at 14:25
  • @MarcvanLeeuwen I don't think sage so much modifies the python interpreter as I believe it preforms all kinds of preparsing for it. Including retyping and similar. – DRF Apr 20 '15 at 16:04

3 Answers3

44

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

25

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

Community
  • 1
Bill Dubuque
  • 265,059
  • 37
  • 279
  • 908
-4

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.

Model_Math
  • 21
  • 3
  • The OP is asking why the operation works and why his code gives him this answer. You could improve your answer by showing the Euclidean algorithm or at least linking to it and explaining in more detail how it relates to inverses. – Math Man Apr 22 '15 at 02:20
  • Ok, I prefer motivating concepts to working example details, so I'll stay away from the homework problems. Sorry to have drawn so much negative attention. – Model_Math Apr 22 '15 at 02:26