Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.1Introduction to Congruence

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

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

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\), 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 Gauss came up with just two centuries ago.

Definition4.1.1Congruence

We say that \(a\) is congruent to \(b\), or \begin{equation*}a \equiv b \text{ (mod }n)\end{equation*} precisely if \(n\mid (a-b)\). We call \(n\) the modulus.

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

Proof
Example4.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\).

It's fun to use congruence as a conceptual assistant. Here are some examples of our previous thinking recast in this way.

  • 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?

  • What about cubes; what remainders are possible modulo 4? What last digits are possible?