Thinking not over the integers as a whole but modulo some integerinstead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.
For the following chapter, we will assumeis a natural integer, andandare two integers. We say thatandare congruent modulowhen, or equivalently when there is an integersuch that. We denote this byor . I will use the first notation throughout this chapter.
Remark: When, we have, whereis the remainder in the euclidean division ofby
This relation has a number of useful properties:
The proofs are left as an exercise to the reader :p (Hint: go back to the definition)
Seeing as addition and multiplication are well defined, the integers moduloform a ring, which we note. In sage, you can construct such ring with either of the following
Zn = Zmod(5)Zn = Integers(5)Zn = IntegerModRing(5)# Ring of integers modulo 5Zn(7)# 2Zn(8) == Zn(13)# True
Powering modulois relatively fast, thanks to the double-and-square algorithm, so we needn't worry about it taking too much time when working with high powers
pow(2, 564654533, 7) # Output result as member of Z/7Z# 4power_mod(987654321, 987654321, 7) # Output result as simple integer# 6Zmod(7)(84564685)^(2^100) # ^ stands for powering in sage. To get XOR, use ^^.# 5
As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integer. This can be used to prove that a relation is never true by finding a suitable modulus, or to derive conditions on the potential solutions of the equation.
Example: by choosing an appropriate modulus, show that not even god is able to find integersandsuch that
Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integeris the same as multiplying by its inverse; that is we want to find another integersuch that. Since, it is clear from Bézout's Identity that such an inverse exists if and only if. Therefore, the units moduloare the integers coprime to, lying in a set we call the unit group modulo:
Zn = Zmod(10)Zn(7).is_unit()# TrueZn(8).is_unit()# False3 == 1/Zn(7) == Zn(7)^(-1) == pow(7,-1,10) # member of Z/10Z# Trueinverse_mod(7, 10) # simple integer# 3Zn(3)/7# 9Zn(3)/8# ZeroDivisionError: inverse of Mod(8, 10) does not existZn.unit_group()# Multiplicative Abelian group isomorphic to C4 (C4 being the cyclic group of order 4)
Finding the modular inverse of a number is an easy task, thanks to the extended euclidean algorithm (that outputs solutions inandto the equationfrom above).
xgcd(7, 10) # find (gcd(a, b), u, v) in au + bv = gcd(a, b)# (1, 3, -2) <-- (gcd(7, 10), d, -k)