Modular Arithmetic
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 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.
Congruences
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
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
Modular Inverse
Last updated
Was this helpful?