Section5.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:

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. 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.

Definition5.1.1Congruence
We say that \(a\) is congruent to \(b\), or \[a \equiv b \text{ mod }(n)\] precisely if \(n\mid (a-b)\).

It's fun to use congruence as a conceptual assistant.

  • For instance, we can try to recast the fact about remainders when dividing by four as saying that \(x^2\equiv 0\text{ or }1\) mod (4), and nothing else is possible.
  • Could you try to use this idea to think of possible last digits of a square? What modulus would be helpful?
  • What about cubes - what remainders are possible modulo 4? What last digits are possible?