1.3: Integers modulo n

Definition: modulo

Let \(n\) \(\in\) \(\mathbb{Z_+}\).

\(a\) is congruent to \(b\) modulo \(n\) denoted as \( a \equiv b \pmod n \), if \(a\) and \(b\)  have the remainder when they are divided by \(n\), for  \(a, b \in \mathbb{Z}\).

Example \(\PageIndex{1}\):

Suppose \(n= 5, \) then the possible remainders are \( 0,1, 2, 3,\) and \(4,\) when we divide any integer by \(5\).

Is \(6 \, \equiv 11 \pmod 5\)? Yes, because \(6\) and \(11\) both belong to the same congruence class \(1\). That is to say when \(6\) and \(11\) are divided by \(5\) the remainder is \(1.\)

Is \(7 \equiv 15 \pmod  5\)? No, because \(7\) and \(15\) do not belong to the same congruent/residue class. Seven has a remainder of \(2,\) while \(15\) has a remainder of \( 0, \) therefore \(7 \) is not congruent to \( 15 \pmod 5\). That is \(7 \not \equiv 15 \pmod 5\).

Example \(\PageIndex{2}\): Clock arithmetic

Find \(18:00\), that is find \(18 \pmod {12}\).

Solution

\(18 \pmod {12} \equiv 6\).  Hence, it is 6 pm.

Properties

Equivalence of Definitions for Modular Congruence

Theorem \(\PageIndex{1}\)

Let \(n \in \mathbb{Z}^+\) and \(a, b \in \mathbb{Z}\). The following three statements are logically equivalent: 

(a) \(n \mid (a - b)\).

(b) \(a\) and \(b\) leave the same remainder when divided by \(n\).

(c) \(a - b = kn\) for some \(k \in \mathbb{Z}\).

NOTE: Possible remainders of \( n\) are \(0, ..., n-1.\)

Proof

Let \(n \in \mathbb{Z}^+\) and \(a, b \in \mathbb{Z}\). We establish equivalence by proving the sequence of implications \(\text{(a)} \implies \text{(c)} \implies \text{(b)} \implies \text{(a)}\).

Part 1: Proof that (a) \(\implies\) (c) 

Assume statement (a) holds, so \(n \mid (a - b)\). Since  \(n\) divides \((a - b)\), there exists an integer \(k \in \mathbb{Z}\) such that \( a - b = kn. \) Thus, statement (c) immediately follows.

Part 2: Proof that (c) \(\implies\) (b)

Assume statement (c) holds, so \(a - b = kn\) for some \(k \in \mathbb{Z}\). By the Division Algorithm, there exist unique integers \(q_1, q_2 \in \mathbb{Z}\) and \(r_1, r_2 \in \mathbb{Z}\) such that \( a = q_1 n + r_1 \quad \text{where } 0 \le r_1 < n,  b = q_2 n + r_2 \quad \text{where } 0 \le r_2 < n. \) Subtracting the second equation from the first gives: \( a - b = (q_1 - q_2)n + (r_1 - r_2). \) Substituting \(a - b = kn\) into this expression yields: \( kn = (q_1 - q_2)n + (r_1 - r_2) \implies r_1 - r_2 = (k - q_1 + q_2)n. \)

Since \(k, q_1, q_2 \in \mathbb{Z}\), the quantity \(m = k - q_1 + q_2\) is an integer, meaning \(r_1 - r_2\) is an integer multiple of \(n\). Next, consider the bounds on \(r_1\) and \(r_2\): \( 0 \le r_1 < n \quad \text{and} \quad -n < -r_2 \le 0. \) Adding these inequalities yields: \( -n < r_1 - r_2 < n. \) The only integer multiple of \(n\) in the open interval \((-n, n)\) is \(0\). Therefore: \( r_1 - r_2 = 0 \implies r_1 = r_2. \) Thus, \(a\) and \(b\) leave the exact same remainder when divided by \(n\), proving statement (b).

Part 3: Proof that (b) \(\implies\) (a)

Assume statement (b) holds. Let \(r\) be the common remainder when \(a\) and \(b\) are divided by \(n\). By the Division Algorithm, there exist quotient integers \(q_1, q_2 \in \mathbb{Z}\) such that \( a = q_1 n + r \quad \text{and} \quad b = q_2 n + r, \quad \text{where } 0 \le r < n. \) Subtracting \(b\) from \(a\): \( a - b = (q_1 n + r) - (q_2 n + r) = (q_1 - q_2)n. \) Since \(q_1 - q_2 \in \mathbb{Z}\), by the definition of divisibility, \(n \mid (a - b)\). Thus, statement (a) holds.

Since \(\text{(a)} \implies \text{(c)} \implies \text{(b)} \implies \text{(a)}\), all three statements are logically equivalent.

Modulo as an Equivalence Relation

 

Theorem \(\PageIndex{2}\)

The relation " \(\equiv\) " over \(\mathbb{Z}\) is an equivalence relation. 

Proof

We shall show that \(\equiv\) is reflexive, symmetric, and Transitive.

Reflexive: 

Let \(a \in \mathbb{Z} \). Then \(a-a=0(n\) , and \( 0 \in \mathbb{Z}\). Hence \(a \equiv a \pmod n\). Thus, congruence modulo n is Reflexive.

Symmetric: 

Let \(a, b \in \mathbb{Z} \) such that \(a \equiv b \pmod n.\) Then \(a-b=kn, \) for some \(k \in \mathbb{Z}\). Now \( b-a= (-k)n \) and \(-k \in \mathbb{Z}\). Hence \(b \equiv a \pmod n\). Thus, the relation is symmetric.

Transitive: 

Let \(a, b, c \in\) \(\mathbb{Z}\), such that \(a \equiv b \pmod n\) and \(b \equiv c \pmod n.\) Then \(a=b+kn, k \in\) \(\mathbb{Z}\) and \(b=c+hn, h \in\) \(\mathbb{Z}\). We shall show that \(a \equiv c \pmod n\). Consider \(a=b+kn=(c+hn)+kn=c+(hn+kn)=c+(h+k)n, h+k \in\) \(\mathbb{Z}\). Hence \(a \equiv c \pmod n\). Thus, congruence modulo \(n\) is transitive.

Since the relation " \(\equiv\) " over \(\mathbb{Z}\) is reflexive, symmetric, and transitive, it is an equivalence relation.

Antisymmetric Property

Is the relation " \(\equiv\) " over \(\mathbb{Z}\) antisymmetric?

Counterexample: \(n\) is fixed

choose: \(a= n+1, b= 2n+1\), then

\(a \equiv b \pmod n\) and \( b \equiv a \pmod n\)

but \( a \ne b.\)

Thus the relation " \(\equiv\) "on \(\mathbb{Z}\) is not antisymmetric.

Modulo(Residue) classes

Definition: 

Let \( n \in \mathbb{Z}_+\).The relation \( \equiv \) on \(\mathbb{Z} \), defined by \( a \equiv b \) if and only if \(n \mid a-b\), is an equivalence relation. The equivalence (residue) classes are:

\([0], [1], [2] \cdots, [n-1]\)`

Example of writing equivalence classes:

Example \(\PageIndex{3}\):

The equivalence classes for \( \pmod  3 \) are (need to show steps):

.

.

.

Below, we will explore arithmetic operations in modular arithmetic.

Theorem \(\PageIndex{3}\): Additive Property

Let \( n \in \mathbb{Z_+}\). Let \( a, b, c,d, \in \mathbb{Z}\) such that \(a \equiv b \pmod n \) and \(c \equiv d \pmod n. \) Then \((a+c) \equiv (b+d)\pmod n.\)

Proof:

Let \(a, b, c, d \in\mathbb{Z}\), such that \(a \equiv b \pmod n \) and \(c \equiv d \pmod n. \)

We shall show that \( (a+c) \equiv (b+d) \pmod n).\)

Since \(a \equiv b \pmod n \) and \(c \equiv d \pmod n, n \mid (a-b\) and \(n \mid (c-d\)

Thus \( a= b+nk, \) and \(c= d+nl,\) for \(k \) and \( l \in \mathbb{Z}\).

Consider\( (a+c) -( b+d)= a-b+c-d=n(k+l), k+l \in \mathbb{Z}\).

Hence \((a+c)\equiv (b+d) \pmod n.\Box\)

Theorem \(\PageIndex{4}\):Multiplication Property

Let \( n \in \mathbb{Z_+}\). Let \( a, b, c,d, \in \mathbb{Z}\) such that \(a \equiv b \pmod  n \) and \(c \equiv d \pmod n. \) Then \((ac) \equiv (bd) \pmod n.\)

Proof:

Let \(a, b, c, d \in \mathbb{Z}\), such that \(a \equiv b \pmod n) \) and \(c \equiv d \pmod  n. \)

We shall show that \( (ac) \equiv (bd) \pmod n.\)

Since \(a \equiv b \pmod n \) and \(c \equiv d \pmod n, n \mid (a-b\) and \(n \mid (c-d\)

Thus \( a= b+nk, \) and \(c= d+nl,\) for \(k\) and \( l \in \mathbb{Z}\).

Consider \( (ac) -( bd)= ( b+nk) ( d+nl)-bd= bnl+dnk+n^2lk=n (bl+dk+nlk), \) where \((bl+dk+nlk) \in \mathbb{Z}\).

Hence \((ac) \equiv (bd) \pmod n.\Box\)

Theorem \(\PageIndex{5}\): Exponent

Let \( n \in \mathbb{Z_+}\). Let \(a, b \in\) \(\mathbb{Z}\) such that \(a \equiv b \pmod  n \). Then \(a^2 \equiv b^2 \pmod  n.\)

Proof:

Let \(a, b \in\) \(\mathbb{Z}\), and n \(\in\) \(\mathbb{Z_+}\), such that \(a \equiv b \pmod  n.\)

We shall show that \(a^2 \equiv b^2 \pmod  n.\)

Since \( a \equiv b \pmod  n, n\mid (a-b).\)

Thus \( (a-b)= nx,\) where \(x \in\) \(\mathbb{Z}\).

Consider \((a^2 - b^2) = (a+b)(a-b)=(a+b)(nx), = n(ax+bx), ax+bx \in \mathbb{Z}\).

Hence \(n \mid a^2 - b^2,\) therefore \(a^2 \equiv b^2 \pmod  n.\) \(\Box\)

Theorem \(\PageIndex{6}\)

Let \( n \in \mathbb{Z_+}\). Let \(a, b \in\) \(\mathbb{Z}\) such that \(a \equiv b \pmod  n\). Then \(a^m \equiv b^m \pmod  n\), \(\forall \in\) \(\mathbb{Z}\).

Proof:

Exercise.

Theorem \(\PageIndex{7}\): Cancellation Property

Let \(n \in \mathbb{Z}^+\) and \(a, b, c \in \mathbb{Z}\). If \(ac \equiv bc \pmod{n}\) and \(\gcd(c, n) = 1\), then \(a \equiv b \pmod{n}.\)

Proof

By definition of modular congruence, \(ac \equiv bc \pmod{n}\) means \(n \mid (ac - bc) = c(a - b)\). Since \(\gcd(c, n) = 1\), applying Euclid's Lemma yields \(n \mid (a - b)\). Hence, \(a \equiv b \pmod{n}\).

Theorem \(\PageIndex{8}\):  Well-define Arithmetic

Let \(n(>1) \in \mathbb{Z}^+\)  and \(a, b \in \mathbb{Z}\). Then  The operations \([a]_n+[b]_n=[a+b]_n\) and \([a]_n[b]_n=[ab]_n\) do not depend on the chosen representatives.

Proof

Let \(n(>1) \in \mathbb{Z}^+\)  and \(a, b \in \mathbb{Z}\).

Assume \(a'\in [a]\) and \(b'\in [b].\) Then  \(a-a'=kn\) and \(b-b'=\ell n\) for some \(k,\ell \in \mathbb{Z}\).  Which implies \((a+b)-(a'+b')=(k+\ell)n\) and \(ab-a'b'=a(b-b')+b'(a-a')=n(a\ell+b'k)\). Hence the result. \(square\)

Definition: 

Let \(n\geq 2\). For \(a\in \mathbb{Z}\), define \([a]_n=\{a+kn:k\in \mathbb{Z}\}.\)
Then \(\mathbb{Z}_{n}=\{[0]_n,[1]_n,\ldots,[n-1]_n\}.\)

Addition is defined by \([a]_n+[b]_n=[a+b]_n,\) and

multiplication is defined by
\([a]_n[b]_n=[ab]_n, \) for \(a, b \in \mathbb{Z}\).

By using the above results, we can solve many problems. Some of them are discussed below: 

Example \(\PageIndex{4}\): \( \pmod 3\) Arithmetic

Let \(n = 3\).

Addition

+	[0]	[1]	[2]
[0]	[0]	[1]	[2]
[1]	[1]	[2]	[0]
[2]	[2]	[0]	[1]

Note:

We will call \([0]\) is the additive identity on \(\mathbb{Z}_{3}\). 

Additive inverses: \([1]\) is the additive inverse of \([2]\), and vice versa.

 

Multiplication

x	[0]	[1]	[2]
[0]	[0]	[0]	[0]
[1]	[0]	[1]	[2]
[2]	[0]	[2]	[1]

Note:

We will call \([1]\) is the multiplicative identity on \(\mathbb{Z}_{3}\). 

Multiplicative inverses: \([1]\) is the multiplicative inverse of \([1]\), and \([2]\) is the multiplicative inverse of \([2]\).

\([0]\) has no multiplicative inverse.

 

 

Example \(\PageIndex{5}\): \( \pmod 4\) Arithmetic

Let \(n=4\).

x	[0]	[1]	[2]	[3]
[0]	[0]	[0]	[0]	[0]
[1]	[0]	[1]	[2]	[3]
[2]	[0]	[2]	[0]	[2]
[3]	[0]	[3]	[2]	[1]

 

Note:

We will call \([1]\) is the multiplicative identity on \(\mathbb{Z}_{4}\). 

Multiplicative inverses: \([1] \) and \([3]\) have multiplicative inverses.

\([0], [2]\) has no multiplicative inverse.

Example \(\PageIndex{6}\):

Find the remainder when \((101)(103)(107)(109)\) is divided by \( 11.\)

Answer

\(101 \equiv 2 \pmod 11\)

\(103 \equiv 4 \pmod 11\)

\(107 \equiv 8 \pmod 11\)

\(109 \equiv 10 \pmod 11\) .

Therefore,

\((101)(103)(107)(109) \equiv (2)(4)(8)(10) \pmod 11 \equiv 2 \pmod 11\) .

Example \(\PageIndex{7}\):

Find the remainder when\( 7^{1453}\) is divided by \( 8.\)

Answer

\(7^0 \equiv 1 \pmod 8\)

\(7^1 \equiv 7 \pmod 8\)

\(7^2 \equiv 1 \pmod 8\)

\(7^3 \equiv 7 \pmod 8\) ,

As a consistent pattern emerges and we know that \(1453\) is odd, we have \(7^{1453} \equiv 7 \pmod 8\). Thus the remainder is \(7.\)

Example \(\PageIndex{8}\):

Find the remainder when \(7^{2020}\) is divided by \(18.\)

Answer

\(7^0 \equiv 1 \pmod {18}\)

\(7^1 \equiv 7 \pmod {18}\)

\(7^2 \equiv 13 \pmod {18}\)

\(7^3 \equiv 1 \pmod {18}\) ,

As there is a consistent pattern emerging and we know that \(2020=(673)3+1\), \(7^{2020}= 7^{(673)3+1}=\left( 7^3\right)^{673}7^1 \equiv 7 \pmod {18}).\) Thus the remainder is \(7.\)

Example \(\PageIndex{9}\):

Find the remainder when \( 26^{1453} \) is divided by \( 3.\)

Example \(\PageIndex{10}\):

Show that \( n^2+1 \) is not divisible by \(3\) for any integer \( n.\)

Answer

Proof: Let \(n \in \mathbb{Z} \). We shall show that \( (n^2+1) \) is not divisible by \(3 \) using the language of congruences.

We shall show that \( (n^2+1)\pmod 3) \not \equiv 0 \) by examining the possible cases.

Case 1: \(n \equiv 0 \pmod 3.\)

\(\implies n^2 \equiv 0^2 \pmod 3.\)

\(\implies (n^2+1) \equiv 1 \pmod 3.\)

Hence \(n^2+1\) is not divisible by \(3.\)

Case 2: \(n \equiv 1 \pmod 3.\)

\(n^2 \equiv 1^2 \pmod 3.\)

\((n^2+1) \equiv 1 \pmod 3.\)

Hence \(n^2+1\) is not divisible by \(3.\)

Case 3: \(n \equiv 2 \pmod 3.\)

\(n^2 \equiv 2^2 \pmod 3) \equiv 1 \pmod 3).\)

\((n^2+1) \equiv 2 \pmod 3).\)

Hence \(n^2+1\) is not divisible by \(3.\)

Since none of the possible cases is congruent to \(0 \pmod 3, n^2+1 \) is not divisible by \(3.\) \(\Box\)

Example \(\PageIndex{11}\):

Show that \(5 \mid a^5+4a\) for any integer \(a.\)

Answer

Notice that \(4 \equiv -1 \pmod 5). \) Therefore, \(5 \mid a^5+4a \) iff \(5 \mid a^5-a\) for all integer \(a\).

Let .

We shall show that .

Then and .

We will proceed by examining the 5 possible cases of \( a \). Specifically, .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Having examined all possible cases, .◻

 

Answer

Let where and .

Then .

Thus . Rearranging, we obtain .

Consider

.

Let .

Since , then .

Thus .

Clearly, . We shall examine the possible cases of .

Case b=0: If then . Thus .

Case b=1: If then and where q .

Thus .

Case b=2: If then and .

Thus .

Case b=3: If then and .

Thus .

Case b=4: If then and .

Thus .

Having examined all possible cases, .◻

Example \(\PageIndex{12}\)

For every positive integer , prove that is divisible by .

Answer

Proof:

Let be the statement .

says that .

says that . Since and , is true.

Assume is true for some .

We will show that is true.

Specifically, we will show that .

Consider that

.

Since , .

Let .

Thus .

Having shown the inductive step, we conclude that for every positive integer , is divisible by .

Multiplicative inverse modulo n

Theorem \(\PageIndex{9}\)

Let \(n \in \mathbb{Z}_+.\)  Let \(a \in \mathbb{Z}\) such that \(a\) and \(n\) are relatively prime. Then there exist integers \(x\) and \(y\) such that \(ax+ny=1.\) Then  \(ax \equiv 1 ( \pmod n ) \), also denoted by  \(ax \equiv 1 \pmod n . \) Note that \(1\) is the multiplicative identity on \(\pmod n \). In this case, \(x \pmod n) \) is the inverse of \(a \pmod n \) .

Example \(\PageIndex{13}\)

If possible, find multiplicative inverse of \( 2 \pmod {10.}\)

Solution

Since \(\gcd(2,10)=2 \ne 1\), \(2\) has no multiplicative inverse modulo \(10.\)

Example \(\PageIndex{14}\)

If possible, find multiplicative inverse of \( 16 \pmod {35}.\)

Solution

Using the Euclidean Algorithm, we will find \(gcd(16, 35) \).

\begin{eqnarray*}35&=(16)(2)+3\\16&=(3)(5)+1\\3 &=(1)(3)+0\end{eqnarray*}

Thus \(gcd(16,35)=1\). Hence multiplicative inverse of \( 16 \pmod {35}\) exists.

By using the Bezout's algorithm,

\begin{eqnarray*}1&=16+(3)(-5)\\&=16+(35+(16)(-2)) (-5)\\&=(35)(-5)+(16)(11)\end{eqnarray*}

Thus \(gcd(16,35)=1=(35)(-5)+(16)(11).\) Hence the multiplicative inverse of \( 16 \pmod {35}\) is \(11\).

Example \(\PageIndex{12}\)

Find the multiplicative inverse of \(7 \pmod{26}\), if possible.
Solution:

Using the Euclidean Algorithm:
\begin{align*}
26 &= (7)(3) + 5 \\
7 &= (5)(1) + 2 \\
5 &= (2)(2) + 1 \\
2 &= (1)(2) + 0
\end{align*}
Since \(\gcd(7, 26) = 1\), the inverse exists. Back-substituting:
\begin{align*}
1 &= 5 + (-2)(2) \\
&= 5 +(-1) (7 +(5)(-1))(2) = (5)(3) +(7)(-2) \\
&= (26 +( 7)(-3))(3) - (7)(2) = (26)(3) + 7(-11)
\end{align*}
This gives \(7(-11) \equiv 1 \pmod{26}\). Since the coefficient \(-11\) is negative, reduce it modulo \(26\):
\(\(-11 \equiv -11 + 26 \equiv 15 \pmod{26}\).

Check: \(7 \times 15 = 105 = (4 \times 26) + 1 \equiv 1 \pmod{26}\).  
Thus, the multiplicative inverse of \(7 \pmod{26}\) is \(15\).

Odd and Even integers:

An integer \( n\) is even iff \( n\equiv 0\pmod 2).\)

An integer \( n\) is odd iff \(n\equiv 1\pmod 2).\)

Two integers a and b are said to have the same parity if they are both even or both odd; otherwise, a and b are said to have different parity.

Example \(\PageIndex{15}\):

Show that the sum of an odd integer and an even integer is odd.

Answer

Proof: Let \(a\) be an odd integer and \(b\) be an even integer. We shall show that \( a+b\) is odd by using the language of congruences.

Since \(a\) is odd, \(a \equiv 1 \pmod 2.\)

Since \(b \) is even, \( b \equiv 0 \pmod 2.\)

Then \((a+b) \equiv (1+0)\pmod 2,\)

\((a+b) \equiv 1 \pmod 2.\)

Hence \(a+b\) is odd.\(\Box\)

Example \(\PageIndex{16}\):

Show that the product of an odd integer and an even integer is even.

Answer

Proof: Let \(a\) be an odd integer and let \(b\) be an even integer. We shall show that \(ab\) is even by using the language of congruences.

Since \(a\) is odd, \(a \equiv 1 \pmod 2.\)

Since \(b \) is even, \( b \equiv 0 \pmod 2.\)

Then \((ab) \equiv (1)(0)\pmod 2,\)

\((ab) \equiv 0 \pmod 2.\)

Hence \(ab\) is even.\(\Box\)

Convention:

Throughout this text, we identify \(\mathbb{Z}_n, n\geq 2,\) with \(\{0,1,\ldots, (n-1)\}\), using these representatives instead of the residue classes \(\{[0]_n,[1]_n,\ldots,[n-1]_n\}\).