Modulo arithmetic: remainders, equivalence and useful methods

What you will get from this section. You will learn what $a\equiv b\mod m$ means and the basic rules of modulo arithmetic. You will then see how these rules can be used to solve problems that might otherwise be difficult, including some that could occur in the TMUA. Although modulo arithmetic is not required knowledge for the TMUA, and any question for which it is useful can also be solved using ordinary arguments about remainders and divisibility, it can turn lengthy calculations and proofs into very short ones. It is therefore an extremely useful and interesting additional technique to learn.

TMUA Relevance Score: 6/10

Basic definition

Let $m$ be a positive integer. We write

$a\equiv b\mod m$

to mean that $a$ and $b$ have the same remainder upon division by $m$. We read this as “$a$ is equivalent to $b$ modulo $m$”.

For example, consider the numbers $24$, $10$, $3$ and $-4$. We have

• $24=3\times7+3$;
• $10=1\times7+3$;
• $3=0\times7+3$;
• $-4=(-1)\times7+3$.

They all leave remainder $3$ when divided by $7$, so

$24\equiv10\equiv3\equiv-4\mod7$.

It is also often useful to characterise equivalence modulo $m$ in the following way:

$a\equiv b\mod m$ if and only if $m$ divides $a-b$.

This is equivalent to the first definition and is sometimes the more useful characterisation.

Adding and subtracting multiples of $m$

We may add or subtract any multiple of $m$ from either side without changing the equivalence modulo $m$.

If $a\equiv b\mod m$, then $a+pm\equiv b+qm\mod m$ for any integers $p$ and $q$.

Why is this true? If $a$ and $b$ have the same remainder modulo $m$, then so do $a+pm$ and $b+qm$, since adding or subtracting a multiple of $m$ does not change the remainder upon division by $m$.

For example, $22\equiv1\mod7$. Adding $14$, which is a multiple of $7$, to $22=3\times7+1$ gives

$22+14=3\times7+1+2\times7=5\times7+1$,

so the remainder is still $1$.

As another example, $22\equiv50\mod7$ means that $22$ and $50$ have the same remainder modulo $7$. If we add $14$ to $22$ while subtracting $28$ from $50$, neither remainder changes, so the resulting numbers remain equivalent modulo $7$. We do not even need to know what the common remainder is—although, in this case, it is $1$.

The most important takeaway intuition

$a\equiv b\mod m$ means that we may regard $a$ and $b$ as the “same”, or as equal, modulo $m$.

Equivalent is the most appropriate way to understand the relationship between such $a$ and $b$. This is not equality in the ordinary sense, but they do have equal remainders upon division by $m$.

Another way to envisage this is to put all integers into groups according to their remainder upon division by $m$. Then $a$ and $b$ belong to the same group. This is what mathematicians call an equivalence relation, which satisfies three key properties:

• every integer is equivalent to itself;
• if $a\equiv b\mod m$, then $b\equiv a\mod m$;
• if $a\equiv b\mod m$ and $b\equiv c\mod m$, then $a\equiv c\mod m$.

This leads to the important basic operations that we can perform in modulo arithmetic. Although $a$ and $b$ are not equal in the ordinary sense, they are regarded as the same modulo $m$. Consequently, some of the operations we can perform on ordinary equations can also be performed on equivalences modulo $m$. This is the next intuition to build.

Basic properties

As mentioned above, we may treat $a\equiv b\mod m$ almost like an equation when adding, subtracting and multiplying. There is, however, an important difference when we try to reverse these operations.

Adding $k$ to both sides

For any integer $k$,

$a\equiv b\mod m\quad\Longleftrightarrow\quad a+k\equiv b+k\mod m$.

The forward implication follows by adding $k$ to both sides. The converse follows by adding $-k$ to both sides.

Multiplying both sides by $k$

For every integer $k$,

$a\equiv b\mod m\quad\Longrightarrow\quad ak\equiv bk\mod m$.

This is less obvious, but it is always true. If $m$ divides $a-b$, then it must also divide $k(a-b)=ak-bk$. Notice that the implication arrow only goes from left to right, unlike the equivalence for addition. The converse is not always true. For example, $2\equiv8\mod6$, but dividing both sides by $2$ would give $1\equiv4\mod6$, which is false.

Cancelling $k$ from both sides

The converse of multiplying both sides by $k$ would allow us to cancel a non-zero integer $k$ from both sides. As shown above, this is not valid in general. The exact condition is:

The implication $ak\equiv bk\mod m\Longrightarrow a\equiv b\mod m$ is valid for all integers $a$ and $b$ if and only if $\gcd(k,m)=1$.

First, we prove the if direction.

Suppose that $\gcd(k,m)=1$ and $ak\equiv bk\mod m$. Then $m$ divides $k(a-b)$. Since $k$ and $m$ have no prime factors in common, all the prime factors of $m$, with their required multiplicities, must divide $a-b$. Hence $m$ divides $a-b$, so $a\equiv b\mod m$.

We now prove the only if direction by contradiction.

Suppose, for contradiction, that cancellation is valid for all integers $a$ and $b$, but $d=\gcd(k,m)>1$. Take $a=0$ and $b=m/d$. Since $d$ divides $k$, the number $bk=(m/d)k=m(k/d)$ is divisible by $m$. Therefore, $ak\equiv bk\mod m$.

However, since $d>1$, we have $0<b<m$, so $b$ is not divisible by $m$. Hence $a\not\equiv b\mod m$. This contradicts our assumption that cancellation is valid for all integers $a$ and $b$. Therefore, cancellation can be valid for all integers $a$ and $b$ only if $\gcd(k,m)=1$.

Combining two equivalences

We can do more than add the same integer to, or multiply both sides of, a single equivalence modulo $m$. We can also add, subtract and multiply two equivalences.

If $a\equiv b\mod m$ and $c\equiv d\mod m$, then

$a+c\equiv b+d\mod m$,

$a-c\equiv b-d\mod m$,

$ac\equiv bd\mod m$.

Proof of the multiplication property

All the properties above can be proved directly from the basic definition. We will prove the least obvious one: if $a\equiv b\mod m$ and $c\equiv d\mod m$, then $ac\equiv bd\mod m$.

Since $a\equiv b\mod m$, the difference $a-b$ is divisible by $m$. Similarly, $c-d$ is divisible by $m$. Now

Both terms on the right are divisible by $m$, so their sum is divisible by $m$. Therefore, $m$ divides $ac-bd$, which proves that $ac\equiv bd\mod m$.

Raising both sides to a positive integer power

The multiplication property immediately gives a further useful rule. We may multiply $a\equiv b\mod m$ by itself repeatedly to obtain

If $a\equiv b\mod m$, then $a^n\equiv b^n\mod m$ for every positive integer $n$.

This is perhaps the biggest cheat rule. For example, knowing that $7\equiv-1\mod4$ immediately tells us that $7^k\equiv1\mod4$ for every positive even integer $k$. You will see many problems shamelessly exploit this shortcut. 😊

Useful methods through TMUA-style examples

Modulo arithmetic develops into a deep topic studied further in university mathematics. For our purposes, however, we need no more than the basic results outlined above. The contrasting examples that follow demonstrate different techniques for using these results to shorten solutions and make the underlying logic easier to follow.

Example 1: Replacing a number inside an algebraic expression

An integer $n$ leaves remainder $5$ when divided by $7$. What remainder does $n^4+3n^2+2n$ leave when divided by $7$?

We are given that $n\equiv5\mod7$. Since $5\equiv-2\mod7$, we may use the more convenient representative $-2$ instead. Applying the addition, multiplication and positive-power rules gives

$n^4+3n^2+2n\equiv(-2)^4+3(-2)^2+2(-2)=16+12-4=24\equiv3\mod7$.

The required remainder is $3$.

Without modulo arithmetic, we could write $n=7q+5$, substitute this into the expression and expand. Modulo arithmetic avoids introducing $q$ and discards all multiples of $7$ immediately.

Technique: Replace numbers with the smallest or most convenient equivalent representatives throughout the calculation.

Example 2: Powers and repeating cycles

What is the remainder when $3^{2026}+7^{2026}$ is divided by $10$?

The powers of $3$ modulo $10$ repeat as

$3,9,7,1,3,9,7,1,\ldots$

Indeed, $3^1\equiv3\mod10$, $3^2\equiv9\mod10$, $3^3\equiv27\equiv7\mod10$ and $3^4=3\cdot3^3\equiv3\cdot7=21\equiv1\mod10$. Multiplying by $3$ once more returns us to $3$, so the cycle repeats.

Similarly, you can verify that the powers of $7$ repeat as

$7,9,3,1,7,9,3,1,\ldots$

Both cycles have length $4$, and $2026=4\times506+2$. The exponent therefore occupies the second position in each cycle, so

$3^{2026}\equiv9\mod10$ and $7^{2026}\equiv9\mod10$.

Hence

$3^{2026}+7^{2026}\equiv9+9=18\equiv8\mod10$,

so the required remainder is $8$.

This particular example is not significantly simplified by modulo arithmetic, but it illustrates how modulo notation can make calculations and logical arguments more systematic and concise.

Technique: When powers repeat in a cycle, reduce the exponent modulo the length of the cycle to determine its position.

Example 3: Proving that an integer equation is impossible

Can integers $x$, $y$ and $z$ satisfy

$x^2+y^2=4z+3$?

Every integer is equivalent modulo $4$ to one of $0$, $1$, $2$ or $3$. Squaring these four representatives gives remainders $0$, $1$, $0$ and $1$, respectively. Therefore, every square is equivalent to either $0$ or $1$ modulo $4$.

It follows that $x^2+y^2$ can only be equivalent to $0$, $1$ or $2$ modulo $4$. However, $4z+3\equiv3\mod4$. The two sides can never be equivalent modulo $4$, so they cannot be equal. Therefore, the equation has no integer solutions.

A case-by-case argument based on whether $x$ and $y$ are even or odd would reach the same conclusion, but modulo arithmetic expresses all four cases together.

Technique: List the possible remainders of each side. If the two sets of possible remainders do not overlap, the equation has no integer solutions.

Example 4: Following a recurrence relation modulo $m$

The sequence $(u_n)$ is defined by $u_1=1$ and $u_{n+1}=2u_n+1$.

For which positive integers $n$ is $u_n$ divisible by $5$?

We need only follow the remainders modulo $5$:

The remainder $1$ has returned. Since each new remainder is determined entirely by the previous one, the same cycle must now repeat:

$1,3,2,0,1,3,2,0,\ldots$

The remainder is $0$ every fourth term. Therefore, $u_n$ is divisible by $5$ precisely when $n$ is divisible by $4$.

We could instead derive $u_n=2^n-1$ and study the remainders of the powers of $2$. Following the recurrence directly is quicker.

Technique: Apply the recurrence directly to the remainders. Once the same state returns, all subsequent remainders repeat.

Example 5: The units digit of a power tower

Find the units digit of

The units digit of an integer is determined by its remainder modulo $10$. The powers of $7$ modulo $10$ repeat in a cycle of length $4$:

We therefore need to determine the remainder when the exponent $7^{7^{7^{7^{7}}}}$ is divided by $4$.

Since $7\equiv3\mod4$ and the exponent $7^{7^{7^{7}}}$ is odd,

Here, I replaced $3$ with $-1$ because $3\equiv-1\mod4$. Nice, right? 😊

The exponent therefore occupies the third position in the cycle of powers of $7$ modulo $10$. Hence

so the units digit is $3$.

Technique: For a power tower, determine only the remainder needed at each level rather than attempting to calculate the enormous exponent.

Summary

The statement $a\equiv b\mod m$ means that $a$ and $b$ leave the same remainder when divided by $m$. Working modulo $m$, we can:

• Replace numbers with the smallest or most convenient equivalent representatives throughout a calculation.

• Add, subtract and multiply equivalences, and raise both sides to any positive integer power.

• Cancel a non-zero integer $k$ from both sides when $\gcd(k,m)=1$. This is the precise condition that guarantees cancellation in every case.