Section 1.3 Modular Arithmetic
a % b gives us the image of a modulo b
7 * 18 % 11
Alternately, we can work in the ring of integers modulo 11.
M11 = Integers(11)
M11.addition_table()
M11(7); M11(18); M11( 7 * 18)
To find the multiplicative inverse, we can use either of our notations:
M11( 3 + 67 * 453)
M11(7^(-1)); M11(1/7)
We can also do modular arithmetic modulo a non-prime: 10
M10=Integers(10)
M10( 4 * 7)
Not all integers have inverses mod 10, but some do.
M10.is_integral_domain()
M10.list_of_elements_of_multiplicative_group()
We can find the inverse of these, but now we see the distinction Sage makes between the two notations.
M10(1/7)
M10(7^{-1})
The reason it doesn't like the exponential notation is because this notation depends on its field descriptor.
M10.is_field(); M11.is_field()
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.
M11.addition_table(); M11.multiplication_table()
Here is the euler_phi function.
M11.unit_group_order(); M10.unit_group_order()
Alternately, you can just compute the function on integers.
euler_phi(11); euler_phi(10)
Observe that powering is pretty fast modulo 11. Compare it to the 'stupid' algorithm.
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.
M11(7^41561)
timeit('M11(7^41561)', number=25)
slowpower11(7,41561)
timeit('slowpower11(7,41561)', number=25)