Authors: A~Z, perhaps someone else but not yet (or they've decided to remain hidden like a ninja)
Introduction
Thinking not over the integers as a whole but modulo some integer
n
instead 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.
Congruences
For the following chapter, we will assume
n
is a natural integer, and
a
and
b
are two integers. We say that
a
and
b
are congruent modulo
n
when
n∣(b−a)
, or equivalently when there is an integer
k
such that
a=b+kn
. We denote this by
a≡b[n]
or
a≡bmodn
. I will use the first notation throughout this chapter.
Remark: When
b=0
, we have
a≡r[b]
, where
r
is the remainder in the euclidean division of
a
by
This relation has a number of useful properties:
∀c∈Z,a≡b[n]⟹ac≡bc[n]
∀c∈Z,a≡b[n]⟹a+c≡b+c[n]
∀c∈Z,a≡b[n] and b≡c[n]⟹a≡c[n]
∀m∈N,a≡b[n]⟹am≡bm[n]
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 modulo
n
form a ring, which we note
Z/nZ
. 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 5
Zn(7)
# 2
Zn(8)== Zn(13)
# True
Powering modulo
n
is 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
# 4
power_mod(987654321,987654321,7)# Output result as simple integer
# 6
Zmod(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
n
. 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 integers
a
and
b
such that
a2=2+4b
Modular Inverse
Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integer
c
is the same as multiplying by its inverse; that is we want to find another integer
d
such that
cd≡1[n]
. Since
cd≡1[n]⟺∃k∈Z,cd=1+kn
, it is clear from Bézout's Identity that such an inverse exists if and only if
gcd(c,n)=1
. Therefore, the units modulo
n
are the integers coprime to
n
, lying in a set we call the unit group modulo
n
:
(Z/nZ)×
Zn = Zmod(10)
Zn(7).is_unit()
# True
Zn(8).is_unit()
# False
3==1/Zn(7)== Zn(7)^(-1)==pow(7,-1,10)# member of Z/10Z
# True
inverse_mod(7,10)# simple integer
# 3
Zn(3)/7
# 9
Zn(3)/8
# ZeroDivisionError: inverse of Mod(8, 10) does not exist
Zn.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 in
d
and
k
to the equation
cd−kn=1
from above).
xgcd(7,10)# find (gcd(a, b), u, v) in au + bv = gcd(a, b)