Section 4.1 Introduction to Congruence
Let's start by a little calculation. What is the remainder ofxxxxxxxxxx
25 % 6
x % m
computes “mod(x,m)
.
xxxxxxxxxx
mod(25,6)
r = x % m
), then xxxxxxxxxx
[ x % 6 for x in [1, 7, 13, 19, 25, -5, -11, 6001, -17]]
Definition 4.1.1. Congruence.
We say that a number
precisely if
Lemma 4.1.2. Congruence-Remainder.
Saying
Proof.
We can sketch the proof. It is a good exercise (see Exercise 4.7.15) to fill in the details.
Write \(a=nq+r\) and \(b=nq'+r'\text{.}\) (Why is this possible, what are the various symbols?) Then there are two steps (why do they suffice?)
First, if \(r=r'\) then there is a \(k\) such that \(a-b=nk\text{,}\) which means \(a\equiv b\) (mod \(n\)). (Why?)
The other direction is showing if \(a-b=nk\) for some \(k\in\mathbb{Z}\text{,}\) then \(r=r'\text{.}\) This is a little harder; try thinking about getting the remainders on one side, and what \(r\neq r'\) would imply with respect to \(n\text{.}\)
Example 4.1.3.
In our case, saying
Example 4.1.4.
Recall the fact about remainders when dividing by four, Proposition 2.1.4. This is just saying that the only possibilities are
Could you try to use this idea to think of possible last (decimal) digits of a perfect square? Which modulus would be helpful? (See Exercise 4.7.11.)
What about cubes; what remainders are possible modulo 4? What last digits are possible?