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

Section4.6Toward Congruences

Question4.6.1

What are the possible last digits of a perfect cube? (This was touched on at the end of Section 4.1.)

We can think of this more systematically now. For instance, if the last digit of \(x> 0\) is 3, then \(x=10m+3\) for some integer \(m\). That is, \([x]=[3]\) (mod \(10\)). So the cube would look like \begin{equation*}x^3=(10m+3)^3 = 1000m^3+900m^2+270m+27=10(\text{ stuff }+2)+7\end{equation*} This would presumably have last digit \(7\).

We can ask Sage to answer this for all possible last digits very quickly:

Sage note4.6.2List comprehensions

This programming structure is known as a list comprehension. Think of it as set builder notation \begin{equation*}\{i^3\text{ (mod }10)\mid 0\leq i\lt 10\}\end{equation*} That's the set of all cubes modulo i, for i between 0 and 9. Sage replaces 0..9 with the integers from 0 to 9.

If you check, what this is doing is getting the (least nonnegative) residue modulo 10 of the cube of every possible last digit. Notice that we also get every possible last digit.

It's possible to think of this more generally. Since we just said the last digit is all we cared about, we could think of this as answering a related kind of question. For all last digits \(d\), is there an \(x\) such that the following works? \begin{equation*}x^3\equiv d\text{ (mod }10)\end{equation*}

Definition4.6.3

Any (integer) equation with congruence in place of equality is called a congruence.

As a result, the previous calculation says that there is a solution to the congruence \(x^3\equiv d\text{ (mod }10)\) for all possible \(d\). Another way to say this is that every number (equivalence class) modulo \(10\) has a cube root. For instance, the cube root of \([7]\) is \([3]\).

This is definitely not true in \(\mathbb{Z}\); the usual cube root of 7 (where \(7\neq [7]\)) is not even rational! This exemplifies the following fact.

However, it is worth thinking about the following, though I will leave “things” vague.

Now let's try the same question again, but with a different modulus.

This seems to imply that every equivalence class modulo \(4\) “has a cube root” except \([2]\).

This is suggestive. Maybe the right generalization is to ask this.

Question4.6.6

Given a modulus \(n\), when is there a solution to \begin{equation*}x^3\equiv d\text{ (mod }n)\end{equation*} Or, for what moduli does \(d\) have a cube root modulo \(n\)?

Once we've opened things up to one such congruence, the sky's the limit.

Question4.6.7

Over the integers, there are only two solutions to \(x^2=x\), the familiar \(x=0\) and \(x=1\). This leads to another natural question we can ask in modular arithmetic.

Namely, what are solutions to the congruence \begin{equation*}x^2\equiv x\text{ (mod }n)\end{equation*} for different moduli \(n\)?

Sage can help us explore this sort of question.

Often, it seems we get the same answers as over the integers. But not always! Can you try to conjecture for which \(n\) we do get the same answer? (See Exercise 4.7.14.)

We begin to see that there are two aspects of solving congruences, which will come up again and again for us.

  • Solving a given congruence

  • Figuring out for which moduli a congruence has solutions (or how many or …)

Much of the course will return to these ideas, such as sooner in Chapters 5 and 7 and later in Chapter 17.