Section5.5Toward Congruences

Subsection5.5.1Why modular arithmetic matters

This has been fun and all. But why are we doing all this? There are two reasons.

The first is practical. Simply put, modular arithmetic makes it much easier to solve certain otherwise very difficult problems about integers, because we can check whether things are possible when we look at things just modulo \(n\). For instance, we can prove things like:

  • “The polynomial \(x^3-x+1\) has no integer roots”.
  • “The curve \(x^3=y^2-7\) has no lattice points”.

Most practical of all are the rules for using modular arithmetic.

  • First off, always first reduce modulo \(n\), then do our arithmetic (add, multiply, exponentiate). We have seen lots of examples of this.
  • Secondly, always use whichever residue of a number modulo \(n\) is convenient for our purposes.

    For example, to add \([22]+[21]\) modulo \(23\) it might be smarter to use the residues \(-1\in[22]\) and \(-2\in [21]\). The answer \([-3]\) is of course the same as \([22+21]=[43]=[20]\) modulo \(23\).

    Remark5.5.1

    Sage note:
    We can check if two numerical expressions are equal using ==.

There are a few things to be aware of when doing this, of course. One very important such caveat is that with exponentiation, you can only replace the base with something in the same congruence class. Just to make sure you get this, on your own compare \[2^3\text{ mod }(5), \; 7^3 \text{ mod }(5),\; \text{ and }2^8 \text{ mod }(5)\; .\] These are quite different.

Referring to our earlier wording, we can assume \([a]^n\) is well-defined, but there is no guarantee that \(a^{[n]}\) makes any sense.

The second reason for doing modular arithmetic is theoretical. We get a new number system! It's one which has new problems, new solutions, and new things to explore. And that's what we'll be doing from now on.

Subsection5.5.2Cubes and cube roots modulo \(n\)

Here is a question: “What are the possible last digits of a perfect cube?” This was touched on at the end of Section 5.1.

But we can think of this better 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 \[x^3=(10m+3)^3 = 1000m^3+900m^2+270m+27=10(\text{ stuff }+2)+7\] This would presumably have last digit \(7\).

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

Remark5.5.2

Sage note:
This structure is known as a "list comprehension". Think of it as set builder notation - the set of all cubes mode 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 the residue modulo 10 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 \[x^3\equiv d\text{ mod }(10)\] works?

Definition5.5.3
Such an “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!

Subsection5.5.3Moving to more moduli

Let's try the same question, but with a different modulus.

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

This is suggestive, so here's another question we can ask.

  • Over the integers, there are only two solutions to \(x^2=x\) - namely, \(x=0\) and \(x=1\).
  • What about solutions to the congruence \(x^2\equiv x\) mod (\(n\)) for different moduli \(n\)?
  • Often, it seems we get the same answers. But not always! Can you try to conjecture for which \(n\) we do get the same answer?

With this question, 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.