Skip to main content

Section 4.6 Toward Congruences

Recall a question touched on in Example 4.1.4.

Question 4.6.1.

What are the possible last digits of a perfect cube?

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\text{.}\) 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\text{.}\)

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

Sage note 4.6.2. List 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 \(10\text{,}\) generated by i from 0 to 9. (Sage replaces [0..9] with the list of 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\text{,}\) is there an \(x\) such that the following works?

\begin{equation*} x^3\equiv d\text{ (mod }10) \end{equation*}
Definition 4.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\text{.}\) 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]\text{.}\)

This is definitely not true in \(\mathbb{Z}\text{;}\) the usual cube root of 7 (where \(7\neq [7]\)) is not even rational! This exemplifies the following fact, which one could consider a driving force in number theory research.

However, a sort of converse is also worth thinking about, where I will leave “things” vague for now.

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]\text{.}\)

This is suggestive, so maybe we can refine our generalized question.

Question 4.6.6.

Given a modulus \(n\) and an integer \(d\text{,}\) identify whether there are solutions to

\begin{equation*} x^3\equiv d\text{ (mod }n)\text{.} \end{equation*}

Or, for what moduli does \(d\) have a cube root modulo \(n\text{?}\)

Once we've opened things up to one such congruence, the sky's the limit. For instance, let's take a slightly more complex quadratic. Over the integers, there are only two solutions to \(x^2=x\text{,}\) the familiar \(x=0\) and \(x=1\text{.}\) This leads to another natural question we can ask in modular arithmetic.

Question 4.6.7.

What are solutions to the congruence

\begin{equation*} x^2\equiv x\text{ (mod }n) \end{equation*}

for different moduli \(n\text{?}\)

Sage can help us explore this sort of question, such as in the following applet.

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

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; sooner, in Chapters 5 and 7, and later in Chapter 17.