1.4: Integers modulo n

Last updated

Nov 25, 2024
Save as PDF
- 1.3: Primes
- 1.5 Linear Congruence

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$ $\newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$ $\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$ $\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$ $\newcommand{\AA}{\unicode[.8,0]{x212B}}$

$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vectorC}[1]{\textbf{#1}}$

$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$

$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$

$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\avec}{\mathbf a}$

$\newcommand{\bvec}{\mathbf b}$

$\newcommand{\cvec}{\mathbf c}$

$\newcommand{\dvec}{\mathbf d}$

$\newcommand{\dtil}{\widetilde{\mathbf d}}$

$\newcommand{\evec}{\mathbf e}$

$\newcommand{\fvec}{\mathbf f}$

$\newcommand{\nvec}{\mathbf n}$

$\newcommand{\pvec}{\mathbf p}$

$\newcommand{\qvec}{\mathbf q}$

$\newcommand{\svec}{\mathbf s}$

$\newcommand{\tvec}{\mathbf t}$

$\newcommand{\uvec}{\mathbf u}$

$\newcommand{\vvec}{\mathbf v}$

$\newcommand{\wvec}{\mathbf w}$

$\newcommand{\xvec}{\mathbf x}$

$\newcommand{\yvec}{\mathbf y}$

$\newcommand{\zvec}{\mathbf z}$

$\newcommand{\rvec}{\mathbf r}$

$\newcommand{\mvec}{\mathbf m}$

$\newcommand{\zerovec}{\mathbf 0}$

$\newcommand{\onevec}{\mathbf 1}$

$\newcommand{\real}{\mathbb R}$

$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$

$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$

$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$

$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$

$\newcommand{\bcal}{\cal B}$

$\newcommand{\ccal}{\cal C}$

$\newcommand{\scal}{\cal S}$

$\newcommand{\wcal}{\cal W}$

$\newcommand{\ecal}{\cal E}$

$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$

$\newcommand{\gray}[1]{\color{gray}{#1}}$

$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$

$\newcommand{\rank}{\operatorname{rank}}$

$\newcommand{\row}{\text{Row}}$

$\newcommand{\col}{\text{Col}}$

$\renewcommand{\row}{\text{Row}}$

$\newcommand{\nul}{\text{Nul}}$

$\newcommand{\var}{\text{Var}}$

$\newcommand{\corr}{\text{corr}}$

$\newcommand{\len}[1]{\left|#1\right|}$

$\newcommand{\bbar}{\overline{\bvec}}$

$\newcommand{\bhat}{\widehat{\bvec}}$

$\newcommand{\bperp}{\bvec^\perp}$

$\newcommand{\xhat}{\widehat{\xvec}}$

$\newcommand{\vhat}{\widehat{\vvec}}$

$\newcommand{\uhat}{\widehat{\uvec}}$

$\newcommand{\what}{\widehat{\wvec}}$

$\newcommand{\Sighat}{\widehat{\Sigma}}$

$\newcommand{\lt}{<}$

$\newcommand{\gt}{>}$

$\newcommand{\amp}{&}$

$\definecolor{fillinmathshade}{gray}{0.9}$

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$

Search

Text Color

Text Size

Margin Size

Font Type

Theorem 1 :

Reflexive Property

Theorem 2:

Symmetric Property

Theorem 3:

Antisymmetric Property

Theorem 4 :

Theorem 5:

Theorem 5 :

Theorem 6:

Theorem 7:

Theorem 8:

Example $\PageIndex{10}$

Example $\PageIndex{11}$

Solution

Example $\PageIndex{16}$ :

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]

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]

Properties

Theorem 1 :

Reflexive Property

Theorem 2:

Symmetric Property

Theorem 3:

Antisymmetric Property

Transitive Property

Theorem 4 :

Theorem 5:

\pmodulo classes

Theorem 5 :

Theorem 6:

Theorem 7:

Theorem 8:

Multiplicative inverse modulo m

Example \PageIndex{10}\PageIndex{10}

Example \PageIndex{11}\PageIndex{11}

Solution

Odd and Even integers:

Example \PageIndex{16}\PageIndex{16}:

Support Center

How can we help?

Example $\PageIndex{10}$

Example $\PageIndex{11}$

Example $\PageIndex{16}$ :

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]