Section 1.3 Modular Arithmetic

a % b gives us the image of a modulo b

In [1]:
7 * 18 % 11
Out[1]:
5

Alternately, we can work in the ring of integers modulo 11.

In [2]:
M11 = Integers(11)
In [3]:
M11.addition_table()
Out[3]:
+  a b c d e f g h i j k
 +----------------------
a| a b c d e f g h i j k
b| b c d e f g h i j k a
c| c d e f g h i j k a b
d| d e f g h i j k a b c
e| e f g h i j k a b c d
f| f g h i j k a b c d e
g| g h i j k a b c d e f
h| h i j k a b c d e f g
i| i j k a b c d e f g h
j| j k a b c d e f g h i
k| k a b c d e f g h i j
In [4]:
M11(7); M11(18); M11( 7 * 18)
Out[4]:
5

To find the multiplicative inverse, we can use either of our notations:

 

In [5]:
M11( 3 + 67 * 453)
Out[5]:
5
In [6]:
M11(7^(-1)); M11(1/7)
Out[6]:
8

We can also do modular arithmetic modulo a non-prime: 10

 

In [7]:
M10=Integers(10)
In [8]:
M10( 4 * 7)
Out[8]:
8

Not all integers have inverses mod 10, but some do.

In [9]:
M10.is_integral_domain()
Out[9]:
False
In [10]:
M10.list_of_elements_of_multiplicative_group()
Out[10]:
[1, 3, 7, 9]

We can find the inverse of these, but now we see the distinction Sage makes between the two notations.

In [13]:
M10(1/7)
Out[13]:
3
In [14]:
M10(7^{-1})

------------------------------------------------------------
TypeError                  Traceback (most recent call last)
<ipython-input-14-3b6e2e037836> in <module>()
----> 1 M10(Integer(7)**{-Integer(1)})

sage/rings/integer.pyx in sage.rings.integer.Integer.__pow__ (build/cythonized/sage/rings/integer.c:13882)()

TypeError: 'sage.rings.integer.Integer' object is not iterable

The reason it doesn't like the exponential notation is because this notation depends on its field descriptor.

In [15]:
M10.is_field(); M11.is_field()
Out[15]:
True

To see what other things the computer will tell you about M11, type 'M11.'  without the quotes, and then press the 'Tab' button.

You can use all of those functions.  Usually you have to put a '()' after them.  Sometimes they need an argument inside the '( )'. 

The computer views the elements as elements in a ring, with the following addition, and multiplication.

In [16]:
M11.addition_table(); M11.multiplication_table()
Out[16]:
*  a b c d e f g h i j k
 +----------------------
a| a a a a a a a a a a a
b| a b c d e f g h i j k
c| a c e g i k b d f h j
d| a d g j b e h k c f i
e| a e i b f j c g k d h
f| a f k e j d i c h b g
g| a g b h c i d j e k f
h| a h d k g c j f b i e
i| a i f c k h e b j g d
j| a j h f d b k i g e c
k| a k j i h g f e d c b

Here is the euler_phi function.

In [17]:
M11.unit_group_order(); M10.unit_group_order()
Out[17]:
4

Alternately, you can just compute the function on integers.

In [18]:
euler_phi(11); euler_phi(10)
Out[18]:
4

Observe that powering is pretty fast modulo 11. Compare it to the 'stupid' algorithm.

In [19]:
def slowpower11(BASE,EXP):
    m = 1;
    for i in range(EXP):
        m = M11(7 * m);
    return m

You can use the timeit command to see how long a command takes.

In [20]:
M11(7^41561)
Out[20]:
7
In [21]:
timeit('M11(7^41561)', number=25)

25 loops, best of 3: 142 µs per loop
In [22]:
slowpower11(7,41561)
Out[22]:
7
In [23]:
timeit('slowpower11(7,41561)', number=25)

25 loops, best of 3: 18.1 ms per loop