1.4: 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 congruent/residue 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\). 6 pm.

Properties

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

Theorem 1 :

Two integers \(a \) and \(b\) are said to be congruent modulo \( n\), \(a \equiv b \pmod  n\), if all of the following are true:

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

b) both \(a\) and \(b \) have 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.\)

Reflexive Property

Theorem 2:

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

Proof: 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 Property

Theorem 3:

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

Proof: 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.

Antisymmetric Property

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

Counter Example: \(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.

Transitive Property

Theorem 4 :

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

Proof: 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.

Theorem 5:

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

\pmodulo classes

Let . The relation \( \equiv \) on by \( a \equiv b \) if and only if , is an equivalence relation. The Classes of have the following equivalence classes:

.

 

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 a modulo world.

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

Theorem 5 :

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 6:

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 7:

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 8:

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.

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]

Multiplication

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

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]

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 there is a consistent pattern emerging and we know that \(1453\) is odd, then \(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{12}\):

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

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{13}\):

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 \( . \) 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{14}\)

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, for every positive integer , is divisible by .

Multiplicative inverse modulo m

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

Example \(\PageIndex{10}\)

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{11}\)

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

If \(m\) is prime, then by Fermat's little theorem, \(a^{m}\cong a\pmod \, m),\)  for all integers \(a\).

Hence \(a^{(m-1)}\cong 1\pmod \, m),\) for all integers \(a\) that are relatively prime to \(m.\) Thus,  if \(gcd(a,m)=1\) and \(m\) is prime then \(a^{-1}\cong a^{(m-2)} \pmod  m),\)

 

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 some parity if they are both even or both odd otherwise a and b are said to have different parity.

Example \(\PageIndex{15}\):

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

Answer

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

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

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