# 3.2: Residue Systems and Euler’s φ-Function

$$\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}$$

residue of $$a$$ modulo $$m$$. As a result, we see that any integer is congruent to one of the integers $$0,1,2,...,m-1$$ modulo m.

A complete residue system modulo $$m$$ is a set of integers such that every integer is congruent modulo $$m$$ to exactly one integer of the set.

The easiest complete residue system modulo $$m$$ is the set of integers $$0,1,2,...,m-1$$. Every integer is congruent to one of these integers modulo $$m$$.

The set of integers $$\{0,1,2,3,4\}$$ form a complete residue system modulo $$5$$. Another complete residue system modulo $$5$$ could be $$6,7,8,9,10$$.

A reduced residue system modulo $$m$$ is a set of integers $$r_i$$ such that $$(r_i,m)=1$$ for all $$i$$ and $$r_i \neq r_j (mod \ m)$$ if $$i\neq j$$.

Notice that, a reduced residue system modulo $$m$$ can be obtained by deleting all the elements of the complete residue system set that are not relatively prime to $$m$$.

The set of integers $$\{1,5\}$$ is a reduced residue system modulo $$6$$.

The following lemma will help determine a complete residue system modulo any positive integer $$m$$.

LEmma

A set of $$m$$ incongruent integers modulo $$m$$ forms a complete residue system modulo $$m$$.

We will prove this lemma by contradiction. Suppose that the set of $$m$$ integers does not form a complete residue system modulo $$m$$. Then we can find at least one integer $$a$$ that is not congruent to any element in this set. Hence non of the elements of this set is actually congruent to the remainder when $$a$$ is divided by $$m$$. Thus dividing by $$m$$ yields to at most $$m-1$$ remainders. Therefore by the pigeonhole principle, at least two integers in the set that have the same remainder modulo $$m$$. This is a contradiction since the set of integers is formed of $$m$$ integers that are incongruent modulo $$m$$.

If $$a_1, a_2,...,a_m$$ is a complete residue system modulo $$m$$, and if $$k$$ is a positive integer with $$(k,m)=1$$, then $ka_1+b, ka_2+b,...,ka_m+b$ is another complete residue system modulo $$m$$ for any integer $$b$$.

Let us prove first that no two elements of the set $$\{ka_1+b, ka_2+b,...,ka_m+b\}$$ are congruent modulo $$m$$. Suppose there exists $$i$$ and $$j$$ such that $ka_i+b\equiv ka_j+b(mod\ m).$ Thus we get that $ka_i\equiv ka_j(mod \ m).$ Now since $$(k,m)=1$$, we get $a_i\equiv a_j(mod\ m)$ But for $$i\neq j$$, $$a_i$$ is inequivalent to $$a_j$$ modulo $$m$$. Thus $$i=j$$. Now notice that there are $$m$$ inequivalent integers modulo m and thus by Lemma 10, the set form a complete residue system modulo $$m$$.

## Euler’s $$\phi$$-Function

We now present a function that counts the number of positive integers less than a given integer that are relatively prime to that given integer. This function is called Euler $$\phi$$-function. We will discuss the properties of Euler $$\phi$$-function in details in chapter 5. It will be sufficient for our purposes in this chapter to the notation.

The Euler $$\phi$$-function of a positive integer n, denoted by $$\phi(n)$$ counts the number of positive integers less than $$n$$ that are relatively prime to n.

Since 1 and 3 are the only two integers that are relatively prime to 4 and less than 4, then $$\phi(4)=2$$. Also, 1,2,...,6 are the integers that are relatively prime to 7 that are less than 7, thus $$\phi(7)=6$$.

Now we can say that the number of elements in a reduced residue system modulo $$n$$ is $$\phi(n)$$.

If $$a_1,a_2,...,a_{\phi(n)}$$ is a reduced residue system modulo $$n$$ and $$(k,n)=1$$, then $$ka_1,ka_2,...,ka_{\phi(n)}$$ is a reduced residue system modulo $$n$$.

The proof proceeds exactly in the same way as that of Theorem 24.

Exercises

1. Give a reduced residue system modulo 12.
2. Give a complete residue system modulo 13 consisting only of odd integers.
3. Find $$\phi(8)$$ and $$\phi(101)$$.