5.7: Modular Arithmetic

Modular arithmetic uses only a fixed number of possible results in all its computation. For instance, there are only 12 hours on the face of a clock. If the time now is 7 o’clock, 20 hours later will be 3 o’clock; and we do not say 27 o’clock! This example explains why modular arithmetic is referred to by some as clock arithmetic.

Example $\PageIndex{1}\label{eg:modarith-01}$

Assume the current time is 2:00 p.m. Write this as 14:00. Sixty five hours later, it would be 79:00. Since $$79 = 24\cdot3+7, \nonumber$$ it will be 7:00 or 7 a.m.

hands-on exercise $\PageIndex{1}\label{he:modarith-01}$

Designate Sunday, Monday, Tuesday, …, Saturday as Day 0, 1, 2, …, 6. If today is Monday, then it is Day 1. What day of the week will it be two years from now? Assume there are 365 days in a year.

In the clock example, we essentially regard 27 o’clock the same as 3 o’clock. They key is, we are only interested in the remainder when a value is divided by 12.

Definition: congruent modulo

Let $n\geq2$ be a fixed integer. We say the two integers $m_1$ and $m_2$ are congruent modulo, denoted $$m_1 \equiv m_2 \pmod{n} \nonumber$$ if and only if $n\mid (m_1-m_2)$. The integer $n$ is called the modulus of the congruence.

What does this notion of congruence have to do with remainders? The next result describes their connection.

Theorem $\PageIndex{1}\label{thm:samer}$

Let $n\geq2$ be a fixed integer. For any two integers $m_1$ and $m_2$, $$m_1\equiv m_2 \mbox{ (mod~$n$)} \quad\Leftrightarrow\quad m_1\bmod n = m_2\bmod n. \nonumber$$

Remark

Do not confuse the two notations. The notation “(mod $n$)” after $m_1\equiv m_2$ indicates a congruence relation, in which “mod $n$” are enclosed by a pair of parentheses, and the notation is placed at the end of the congruence. In contrast, the “mod” between $m_1$ and $n$, without parentheses, is a binary operation that yields the remainder when $m_1$ is divided by $n$.

Proof

($\Rightarrow$) Assume $m_1\equiv m_2$ (mod $n$). The definition of congruence implies that we have $n\mid(m_1-m_2)$. Hence, $$m_1-m_2 = nq \nonumber$$ for some integer $q$. Let $m_1=nq_1+r_1$ and $m_2=nq_2+r_2$ for some integers $q_1, q_2, r_1, r_2$, such that $0\leq r_1,r_2<n$. Then $$nq = m_1-m_2 = n(q_1-q_2)+r_1-r_2. \nonumber$$ Since $r_1-r_2=n(q-q_1+q_2)$, we conclude that $n\mid r_1-r_2$. However, $0\leq r_1,r_2<n$ implies that $|r_1-r_2|<n$. Therefore, we must have $r_1-r_2=0$, or $r_1=r_2$. It follows that $m_1\bmod n = m_2\bmod n$.

($\Leftarrow$) Assume $m_1\bmod n = m_2\bmod n$. According to the Division Algorithm, the remainder in an integer division is unique. Thus, $m_1=nq_1+r$ and $m_2=nq_2+r$ for some integers $q_1, q_2, r$ such that $0\leq r<n$. Then $$m_1-m_2 = (nq_1+r)-(nq_2+r) = n(q_1-q_2). \nonumber$$ Therefore, $n\mid(m_1-m_2)$.

Corollary $\PageIndex{2}\label{cor:mod0div}$

Let $n\geq2$ be a fixed integer. Then $$a\equiv0 \pmod{n} \quad\Leftrightarrow\quad n\mid a. \nonumber$$

Theorem 5.7.1 tells us $m_1\equiv m_2$ (mod $n$) if and only if $m_1$ and $m_2$ share the same remainder when they are divided by $n$. Given any integer $m$, $$m\bmod n \in\{0,1,2,\ldots,n-1\}. \nonumber$$ We call these values the residues modulo . In modular arithmetic, when we say “reduced modulo ,” we mean whatever result we obtain, we divide it by $n$, and report only the smallest possible nonnegative residue.

The next theorem is fundamental to modular arithmetic.

Theorem $\PageIndex{3}\label{thm:modthm}$

Let $n\geq2$ be a fixed integer. If $a\equiv b$ (mod $n$) and $c\equiv d$ (mod $n$), then $$\begin{array}{rcll} a+c &\equiv& b+d & \pmod{n}, \\ ac &\equiv& bd & \pmod{n}. \end{array} \nonumber$$

Proof

Assume $a\equiv b$ (mod $n$) and $c\equiv d$ (mod $n$). Then $n\mid (a-b)$ and $n\mid(c-d)$. We can write $$a-b = ns, \qquad\mbox{and}\qquad c-d = nt \nonumber$$ for some integers $s$ and $t$. Consequently, $$(a+c)-(b+d) = (a-b)+(c-d) = ns+nt = n(s+t), \nonumber$$ where $s+t$ is an integer. This proves that $a+c\equiv b+d$ (mod $n$). We also have $$ac-bd = (b+ns)(d+nt)-bd = bnt+nsd+n^2st = n(bt+sd+nst), \nonumber$$ where $bt+sd+nst$ is an integer. Thus, $n\mid (ac-bd)$, which means $ac\equiv bd$ (mod $n$).

Because of Theorem 5.7.3, we can add or multiply an integer to both sides of a congruence without altering the congruences.

Example $\PageIndex{2}\label{eg:modarith-02}$

We can use subtraction to reduce 2370 modulo 11. Any multiple of 11 is congruent to 0 modulo 11. So we have, for example, $$2370\equiv 2370 \pmod{11}, \qquad\mbox{and}\qquad 0\equiv-2200 \pmod{11}. \nonumber$$ Applying Theorem 5.7.3, we obtain $$2370 \equiv 2370-2200 = 170 \pmod{11}. \nonumber$$ What this means is: we can keep subtracting appropriate multiples of $n$ from $m$ until the answer is between 0 and $n-1$, inclusive. It does not matter which multiple of 11 you use. The point is, pick one that you can think of quickly, and keep repeating the process. Continuing in this fashion, we find $$170 \equiv 170-110 = 60 \pmod{11}. \nonumber$$ Since $60-55=5$, we determine that $2370\equiv5$ (mod 11).

hands-on exercise $\PageIndex{2}\label{he:modarith-02}$

Reduce 12457 to the smallest nonnegative residue modulo 17.

Example $\PageIndex{3}\label{eg:modarith-03}$

In a similar manner, if $m$ is negative, we can keep adding multiples of $n$ to it until the answer is positive. For example, $$-278 \equiv -278+300 = 52 \pmod{11}. \nonumber$$ it is obvious that $52\equiv52-44=8$ (mod 11). Thus, $-278\equiv8$ (mod 11).

hands-on exercise $\PageIndex{3}\label{he:modarith-03}$

Evaluate $-3275\bmod11$. This is the same as reducing $-3275$ to the smallest nonnegative residue modulo 11.

In a complicated computation, reduce the result from each intermediate step before you carry on with the next step. This will simplify the computation tremendously. To further speed up the computation, we can use negative values in the intermediate step. Nonetheless, the final answer must be between 0 and $n-1$.

Example $\PageIndex{4}\label{eg:modarith-04}$

Reduce $37^2\cdot41-53\cdot2$ modulo 7.

Solution

Take note that $$\begin{array}{lclcr} 37 &\equiv& 37-35 &=& 2 \pmod{7}, \\ 41 &\equiv& 41-42 &=& -1 \pmod{7}, \\ 53 &\equiv& 53-49 &=& 4 \pmod{7}. \end{array} \nonumber$$ Therefore, $$37^2\cdot41-53\cdot2 \equiv 2^2\cdot(-1)-4\cdot2 = -12 \pmod{7}. \nonumber$$ We determine that $37^2\cdot41-53\cdot2 \equiv 2$ (mod 7).

hands-on exercise $\PageIndex{4}\label{he:modarith-04}$

Evaluate $56^3\cdot22\cdot17-35\cdot481$ (mod 9).

Tedious computation may become rather simple under modular arithmetic.

Example $\PageIndex{5}\label{eg:modarith-05}$

Show that if an integer $n$ is not divisible by 3, then $n^2-1$ is always divisible by 3. Equivalently, show that if an integer $n$ is not divisible by 3, then $n^2-1\equiv0$ (mod 3).

Solution 1

Let $n$ be an integer not divisible by 3, then either $n\equiv1$ (mod 3), or $n\equiv2$ (mod 3).

Case 1. If $n\equiv1$ (mod 3), then $$n^2-1 \equiv 1^2-1 = 0 \pmod{3}. \nonumber$$

Case 2. If $n\equiv2$ (mod 3), then $$n^2-1 \equiv 2^2-1 = 3 \equiv 0 \pmod{3}. \nonumber$$

In both cases, we have found that $n^2-1$ is divisible by 3.

Solution 2

Let $n$ be an integer not divisible by 3, then either $n\equiv1$ (mod 3), or $n\equiv2$ (mod 3). This is equivalent to saying $n\equiv\pm1$ (mod 3). Then $$n^2-1 \equiv (\pm1)^2-1 = 1-1 = 0 \pmod{3}, \nonumber$$ which means $n^2-1$ is divisible by 3.

hands-on exercise $\PageIndex{5}\label{he:modarith-05}$

Use modular arithmetic to show that $5\mid(n^5-n)$ for any integer $n$.

hands-on exercise $\PageIndex{6}$

Use modular arithmetic to show that $n(n+1)(2n+1)$ is divisible by 6 for any integer $n$.

Raising an integer to a large power poses a serious problem. We cannot just raise an integer to a large power, because the result could be so large that the calculator or computer has to convert it into a decimal value and start using scientific notation to handle it. Consequently, the answer will not be accurate.

A better solution is to reduce the intermediate results modulo $n$ after each multiplication. This will produce an accurate result, but it will take a long time to finish if the power is huge. Fortunately, there is a much faster way to perform exponentiation that uses a lesser number of multiplications.

Example $\PageIndex{6}\label{eg:modarith-06}$

Evaluate $5^{29}$ (mod 11).

Solution

First, write the exponent 29 as a sum of powers of 2. We can do it by inspection. Start with the highest power of 2 that is less than or equal to 29, and then work with whatever is left in the sum: $$29 = 16+13 = 16+8+5 = 16+8+4+1. \nonumber$$ We are essentially expressing 29 in base 2. We can now write

$$5^{29} = 5^{16+8+4+1} = 5^{16}\cdot5^8\cdot5^4\cdot5. \nonumber$$

These powers of 5 can be obtained by means of repeated squaring:

$$\begin{aligned} 5^1 &=& 5, \\ 5^2 &=& 5^2, \\ 5^4 &=& (5^2)^2, \\ 5^8 &=& (5^4)^2, \\ 5^{16} &=& (5^8)^2, \\ \vdots\hfil && \hfil\vdots \end{aligned}\label{eg:repsq}$$

The iteration is simple: each new power is obtained by squaring the previous power. Since we are doing modular arithmetic, we want to reduce each intermediate result modulo 11: $$\begin{array}{lclcrcrr@{\quad\pmod{11}}} 5 &= & 5 & & & & & \text{(mod 11)} \\ 5^2 &= & 25 &\equiv& 3 & & & \text{(mod 11)} \\ 5^4 &\equiv& 3^2 &= & 9 &=& -2 & \text{(mod 11)} \\ 5^8 &\equiv& 9^2 &\equiv&(-2)^2 &=& 4 & \text{(mod 11)} \\ 5^{16} &\equiv& 4^2 &= & 16&\equiv& 5 & \text{(mod 11)} \end{array} \nonumber$$ It follows that $$5^{29} = 5^{16}\cdot5^8\cdot5^4\cdot5 \equiv 5\cdot4\cdot(-2)\cdot5 \pmod{11}. \nonumber$$ After simplification, we find $5^{29}\equiv9$ (mod 11).

hands-on exercise $\PageIndex{7}\label{he:modarith-06}$

Use repeated squaring to find $7^{45}$ (mod 11).

hands-on exercise $\PageIndex{8}\label{he:modarith-07}$

Use repeated squaring to evaluate $9^{58}$ (mod 23).

In modular arithmetic, we are basically working with the remainders only. The set of integers $\{0,1,2,\ldots,n-1\}$ is called the set of integers modulo , and is denoted by $\mathbb{Z}_n$ (pronounced as Z mod $n$). In addition, we define two new arithmetic operations on $\mathbb{Z}_n$. They are called “addition” and “multiplication” because they work like the usual addition and multiplication, except that we have to apply the mod operation to the results. To distinguish them from the usual addition and multiplication, we denote them by $\oplus$ and $\odot$, and are called “circled plus” and “circled dot,” respectively. Formally,

$$a\oplus b = (a+b) \bmod n, \qquad\mbox{and}\qquad a\odot b = (a\cdot b)\bmod n. \nonumber$$

The addition and multiplication tables for $\mathbb{Z}_6$ are listed below.

$$\begin{array}{|c||*{6}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{6}{c|}}\hline\odot & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ \hline 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ \hline 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ \hline 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber$$

Compare them to the tables for $\mathbb{Z}_7$.

$$\begin{array}{|c||*{7}{c|}}\hline\oplus & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 6 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 6 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 6 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 6 & 0 & 1 & 2 & 3 & 4 \\ \hline 6 & 6 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \end{array} \qquad\qquad \begin{array}{|c||*{7}{c|}} \hline\odot & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\ \hline 3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\ \hline 4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\ \hline 5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\ \hline 6 & 0 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \nonumber$$

In both addition tables, all possible values appear in every row and every column. The same is true in the nonzero rows and nonzero columns in the multiplication table for $\mathbb{Z}_7$. However, some of the rows in the multiplication table for $\mathbb{Z}_6$ do not contain all the integers in $\mathbb{Z}_6$. This suggests that the algebraic properties of $\mathbb{Z}_n$ depend on the value of $n$.

In fact, whenever $n$ is prime, the addition and multiplication tables of $\mathbb{Z}_n$ behave like the ones in $\mathbb{Z}_7$. It can be shown that when $n$ is prime, $\mathbb{Z}_n$ has the following properties.

1. Both $\oplus$ and $\odot$ are commutative, meaning $$a\oplus b = b\oplus a \qquad\mbox{and}\qquad a\odot b = b\odot a \nonumber$$ for all $a,b\in\mathbb{Z}_n$.
2. Both $\oplus$ and $\odot$ are associative, meaning that $$(a\oplus b)\oplus c = a\oplus(b\oplus c) \qquad\mbox{and}\qquad (a\odot b)\odot c = a\odot(b\odot c) \nonumber$$ for all $a,b,c\in\mathbb{Z}_n$.
3. The operations $\oplus$ and $\odot$ satisfy the distributive laws $$a\odot(b\oplus c) = (a\odot b) \oplus (a\odot c) \qquad\mbox{and}\qquad (b\oplus c)\odot a = (b\odot a) \oplus (c\odot a) \nonumber$$ for all $a,b,c\in\mathbb{Z}_n$.
4. The integer 0 is the additive identity, meaning that $a\oplus 0 = 0\oplus a = a$ for all $a\in\mathbb{Z}_n$.
5. For every $a\in\mathbb{Z}_n$, there exists a unique integer $a'\in\mathbb{Z}_n$ such that $a\oplus a'=0$. This integer $a'$ is called the additive inverse or negative of $a$, and is denoted by $-a$.
6. The integer 1 is the multiplicative identity, meaning that $a\odot 1 = 1\odot a = a$ for all $a\in\mathbb{Z}_n$.
7. For every integer $a\in\mathbb{Z}_n^*$ (hence, $a\neq0$), there exists a unique nonzero integer $a'\in\mathbb{Z}_n$ such that $a\odot a'=1$. This integer $a'$ is called the multiplicative inverse or reciprocal of $a$, and is denoted by $a^{-1}$.

Example $\PageIndex{7}\label{eg:modarith-07}$

From the tables above, only 1 and 5 have multiplicative inverses in $\mathbb{Z}_6$. In fact, $$1\cdot1 = 1 \qquad\mbox{and}\qquad 5\cdot5 = 1 \qquad\mbox{in $\mathbb{Z}_6$} \nonumber$$ imply that $1^{-1}=1$, and $5^{-1}=5$ in $\mathbb{Z}_6$. On the other hand, every nonzero integer in $\mathbb{Z}_7$ has a multiplicative inverse: $$1^{-1}=1, \quad 2^{-2}=4, \quad 3^{-1}=5, \quad 4^{-1}=2, \quad 5^{-1}=3, \quad\mbox{and}\quad 6^{-1}=6. \nonumber$$ Be sure to verify these inverses.

In general, given any set of numbers, we can define arithmetic operations in any way we like, provided that they obey certain rules. This produces an algebraic structure. For example, we call a set of elements $S$ with two binary operations denoted $\oplus$ and $\odot$ a field, and write $\langle S,\oplus,\odot\rangle$ or $(S,\oplus,\odot)$, if it satisfies all seven properties listed above. Both $\langle\mathbb{R},+,\cdot\,\rangle$ and $\langle\mathbb{Q},+,\cdot\,\rangle$ are fields, but $\langle\mathbb{Z},+,\cdot\,\rangle$ is not, because multiplicative inverse of $a$ does not exist if $a\neq\pm1$.

Theorem $\PageIndex{4}$

The algebraic structure $\langle\mathbb{Z}_n,\oplus,\odot\rangle$ is a field if and only if $n$ is prime.

Proof

Verification of most of the properties is rather straightforward, with the exception of the existence of the multiplicative inverse, which we shall prove here. Since $n$ is a prime, any $a\in\mathbb{Z}^*$ must be relatively prime to $n$. Hence, $$as+nt = 1 \nonumber$$ for some integers $s$ and $t$. Modulo $n$, we find $nt=0$, hence, $as+nt=1$ becomes $$as = 1. \nonumber$$ Therefore $a^{-1} \equiv s$ (mod $n$).

The theorem tells us that if $n$ is prime, then $\mathbb{Z}_n$ is a field, hence, every nonzero integer has a multiplicative inverse.

Example $\PageIndex{8}\label{eg:modarith-08}$

Determine $7^{-1}$ (mod 29).

Solution

We want to find a number $a'$ such that $7a'\equiv1$ (mod 29). Note that $\gcd(7,29)=1$. Using extended Euclidean algorithm, we find $$7(-4)+29\cdot1 = 1. \nonumber$$ Since $29\cdot1\equiv0$ (mod 29), after reducing modulo 29, we find $$7(-4) \equiv 1 \pmod{29}. \nonumber$$ This implies that $7^{-1}\equiv-4\equiv 25$ (mod 29).

When $n$ is composite, $\mathbb{Z}_n$ is not a field. Then not every nonzero integer in it has a multiplicative inverse. Of course, some special nonzero integers may still have multiplicative inverses.

hands-on exercise $\PageIndex{9}\label{he:modarith-08}$

Determine $8^{-1}$ (mod 45).

Example $\PageIndex{9}\label{eg:modarith-09}$

Solve the equation $7x-3=5$ over $\mathbb{Z}_{29}$.

Solution

From $7x-3=5$, we find $7x=8$. Recall that what this equation really means is $$7x \equiv 8 \pmod{29}. \nonumber$$ The answer is not $x=\frac{8}{7}$, because $\mathbb{Z}_{29}$ only contains integers as its elements. This is what we should do: multiply $7^{-1}$ to both sides of the congruence: $$7^{-1}\cdot 7x \equiv 7^{-1}\cdot8 \pmod{29}. \nonumber$$ Since $7^{-1}\cdot7\equiv1$ (mod 29), we now have $$x\equiv 7^{-1}\cdot8 \pmod{29}. \nonumber$$ In a way, we use multiplicative inverse to simulate division. In this case, $7^{-1}\equiv7$ (mod 29). Hence, $x\equiv7\cdot8\equiv26$ (mod 29).

hands-on exercise $\PageIndex{10}\label{he:modarith-09}$

Solve the equation $8x+23=12$ over $\mathbb{Z}_{45}$.

Example $\PageIndex{10}\label{eg:modarith-10}$

Explain why $3^{-1}$ does not exist in $\mathbb{Z}_{24}$.

Solution

Suppose $3^{-1}$ exists in $\mathbb{Z}_{24}$, say, $3^{-1}\equiv z$ (mod 24). This means $3z\equiv1$ (mod 24). Hence, $$3z = 24q+1 \nonumber$$ for some integer $q$. This in turn implies that $$1 = 3z-24q = 3(z-8q), \nonumber$$ which is clearly impossible because $z-8q$ is an integer. This contradiction shows that $3^{-1}$ does not exist in $\mathbb{Z}_{24}$.

Both $\mathbb{R}$ and $\mathbb{Q}$ are infinite fields, while $\mathbb{Z}_n$ is a finite field when $n$ is prime. The next result is a truly amazing one, because it proclaims that the number of elements in any finite field (one with finitely many elements) must be the power of a certain prime. Unfortunately, we are unable to prove it here, because it is beyond the scope of this course.

Theorem $\PageIndex{5}$

There exists a finite field of $n$ elements if and only if $n$ is the power of a prime.

• Modular arithmetic modulo $n$ uses the mod operation to reduce the answers of all computation to within 0 through $n-1$.
• Instead of waiting until we obtain the final answer before we reduce it modulo $n$, it is easier to reduce every immediate result modulo $n$ before moving on to the next step in the computation.
• We can use negative integers in the intermediate steps.
• The set of integers $\{0,1,2,\ldots,n-1\}$, together with modular arithmetic modulo $n$, is denoted as $\mathbb{Z}_n$.
• For $a\cdot a'\equiv1$ (mod $n$), we say that $a'$ is the multiplicative inverse of $a$, and denote it $a^{-1}$.
• For some $a\in\mathbb{Z}_n$, the multiplicative inverse $a^{-1}$ may not exist. If it exists, we can use it to simulate division.

Exercise $\PageIndex{1}\label{ex:modarith-01}$

Construct the addition and multiplication tables for $\mathbb{Z}_8$. Which nonzero elements have multiplicative inverses (reciprocals)? What are their multiplicative inverses?

Exercise $\PageIndex{2}\label{ex:modarith-02}$

Repeat the last problem with $\mathbb{Z}_9$.

Exercise $\PageIndex{3}\label{ex:modarith-03}$

Find the sum and product of 1053 and 1761 in $\mathbb{Z}_{17}$.

Exercise $\PageIndex{4}\label{ex:modarith-04}$

Some of the results we derived earlier can be easily proven via modular arithmetic. For example, show that if an integer $n$ is not divisible by 3, then $n\equiv\pm1$ (mod 3). What can you say about $n^2$ (mod 3)? Therefore what form must $n^2$ take?

Exercise $\PageIndex{5}\label{ex:modarith-05}$

Show that no integer of the form $m^2+1$ is a multiple of 7.

Hint

What are the possible values of $m$ (mod 7)? Compare this to the last problem.

Exercise $\PageIndex{6}\label{ex:modarith-06}$

What are the possible values of $m$ (mod 13) such that $m^2+1$ is a multiple of 13?

Hint

Compute $m^2+1$ (mod 13) for each value of $m$.

Exercise $\PageIndex{7}\label{ex:modarith-07}$

Find the value of $4^{45}$ in $\mathbb{Z}_{11}$

1. using the fact that $45=3\cdot3\cdot5$
2. using repeated squaring

Exercise $\PageIndex{8}\label{ex:modarith-08}$

Use repeated squaring to evaluate $5^{23}$ (mod 11).

Exercise $\PageIndex{9}\label{ex:modarith-09}$

Solve these equations

1. $2x+ 5=10$ over $\mathbb{Z}_{13}$
2. $37x+28=25$ over $\mathbb{Z}_{57}$
3. $12-24x=15$ over $\mathbb{Z}_{35}$

Exercise $\PageIndex{10}\label{ex:modarith-10}$

Let $p$ and $q$ be odd primes.

1. Show that $p$ takes the form of either $6k+1$ or $6k+5$.

Hint

First, explain why being odd restricts $p$ to the form of $6k+1$, $6k+3$, and $6k+5$. Next, argue why $p\neq 6k+3$.

2. What could $p$ be congruent to, modulo 24?
3. Show that if $p\geq q\geq5$, then $24\mid (p^2-q^2)$.

Hint

What are the possible values of $p^2$ and $q^2$ modulo 24?

Exercise $\PageIndex{11}\label{ex:modarith-11}$

Use modular arithmetic to prove that, if $n$ is an integer not divisible by 5, then $n^4-1$ is divisible by 5.

Exercise $\PageIndex{12}\label{ex:modarith-12}$

Use modular arithmetic to prove that $8\mid(5^{2n}+7)$ for any integer $n\geq0$.

Exercise $\PageIndex{13}\label{ex:modarith-13}$

Use modular arithmetic to prove that $3\mid(2^{2n}-1)$ for any integer $n\geq0$.

Exercise $\PageIndex{14}\label{ex:modarith-14}$

Use modular arithmetic to prove that $5\mid(3^{3n+1}+2^{n+1})$ for any integer $n\geq0$.