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.

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:

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?

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!

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

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