Skip to main content

Section 4.1 Introduction to Congruence

Let's start by a little calculation. What is the remainder of \(25\) when divided by \(6\text{?}\)

In general, the command x % m computes “\(x\) modulo \(m\)”, which is to say the remainder of \(x\) when you divide by \(m\text{.}\)

An alternate way to do this is with the command mod(x,m).

In a moment this will be more desirable, but for now it is less so, because it creates a different kind of Sage object.

Because of the division algorithm, we know that there is a unique such remainder. If we call it \(r\) (so that r = x % m), then \(0\leq r <m\text{,}\) which is very important. However, lots and lots of different numbers can have the same remainder:

(See Sage note 4.6.2 for this type of list construction.)

In mathematics, what we often do in such a situation where structure is shared is connect things with a relation.

A relation is a very general notion, and basically it exists once you define it; however, we will not pursue this further. Our relation will be called congruence, and it is massively important. It is also relatively new! We essentially use the same definitions and notation that the great 19th-century German mathematician C.F. Gauss (see Historical remark 14.1.3) came up with just two centuries ago.

Definition 4.1.1. Congruence.

We say that a number \(a\) is congruent to \(b\) another number, or

\begin{equation*} a \equiv b \text{ (mod }n)\text{,} \end{equation*}

precisely if \(n\mid (a-b)\text{.}\) We call \(n\) the modulus. The noun form of the relationship is called congruence.

Often we can prove a small helping statement, usually called a lemma.

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 \(25\equiv 1\equiv -5\) (mod \(6\)) is the same as saying \(25=4\cdot 6 +1\) and \(1=0\cdot 6 + 1\) and \(-5=-1\cdot 6+1\text{.}\)

It's fun to use congruence as a conceptual assistant. Here are an example of our previous thinking recast using congruence.

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

\begin{equation*} x^2\equiv 0\text{ or }1\text{ (mod }4) \end{equation*}

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?