Category Archives: Discrete Mathematics

Congruences 2

Theorem 1 (Fermat’s Little Theorem). Let $p$ be a prime. Then for any integer $a$, $$a^p\equiv a\mod p$$ and for any integer $a$ not divisible by $p$,
$$a^{p-1}\equiv 1\mod
p.$$

Proof. We prove the second statement first. Suppose that $p\not| a$. If
$i\equiv j\mod p$ then clearly $ai\equiv aj\mod p$. Conversely, if
$ai\equiv aj\mod p$ then $$p|ai-aj=a(i-j).$$ Since $(a,p)=1$, $p|i-j$, i.e., $i\equiv j\mod p$. So, $0a,1a,2a,\cdots,(p-1)a$ are a complete set of residues $\mod p$, that is, they are rearrangement of $0,1,2,\cdots,p-1$ when considered $\mod p$. Hence, $$(p-1)!a^{p-1}\equiv(p-1)!\mod p,$$
i.e., $p|(p-1)!(a^{p-1}-1)$. Since $p\not|(p-1)!$ then $p|a^{p-1}-1$, i.e., $$a^{p-1}\equiv 1\mod p.$$ If $a$ is divisible by $p$, then clearly
$$a^p\equiv a\mod p$$ since either side is congruent to $0\mod p$.

Corollary 2. If $p\not| a$ and if $n\equiv m\mod p-1$ then $$a^n\equiv a^m\mod p.$$

Proof. Say $n>m$. Since $n\equiv m\mod p-1$, $$n=m+(p-1)c$$ for some $c\in\mathbb{Z}$. By Fermat’s Little Theorem (Theorem 1),
$$a^{p-1}\equiv 1\mod p$$ and so
$$a^{c(p-1)}\equiv 1\mod p\Longrightarrow a^n=a^{m+(p-1)c}\equiv a^m\mod p.$$

Example. Find the last base-$7$ digit in $2^{1000000}$.

Solution: Let $p=7$. Since $1000000$ leaves a remainder of $4$ when divided by $p-1=6$, $$1000000\equiv 4\mod 6=7-1$$ and $7\not|2$. By Corollary 2, $$2^{1000000}\equiv 2^4=16\equiv 2\mod 7.$$
Thus, $2$ is the answer.

Lemma 3. If $a\equiv b\mod m$, $a\equiv b\mod n$, and
$(m,n)=1$, then $a\equiv b\mod mn$.

Proof. Since $a\equiv b\mod m$, $b-a=md$ for some $d\in\mathbb{Z}$.
\begin{align*} a\equiv b\mod n&\Longrightarrow n|md\\ &\Longrightarrow n|d\ \mbox{since}\ (m,n)=1\\ &\Longrightarrow d=ns\ \mbox{for some}\ s\in\mathbb{Z}\\ &\Longrightarrow b-a=mns\\ &\Longrightarrow a\equiv b\mod mn. \end{align*}

Definition (Euler phi function).
For any positive integer $n$, $\phi(n)$ is defined to be the number
of integers $a$, $1\leq a\leq n$, such that $(a,n)=1$. The function
$\phi$ is called the Euler phi function.

Example. $\phi(1)=1$ by definition.

To calculate $\phi(6)$, we write all positive integers that are
less than or equal to $6$ and then cross out the ones that are not
relatively prime to $6$. Counting the remaining numbers will give
$\phi(6)$: $$1,\not 2,\not 3,\not 4,5,\not 6.$$ Hence, $\phi(6)=2$.

Since $7$ is a prime number, any positive integer that are less than
$7$ are relatively prime to $7$, so $\phi(7)=6$. In general, if $p$
is a prime number then \begin{equation}\label{eq:phiprime} \phi(p)=p-1.\end{equation}

In order to calculate $\phi(12)$, we write $$1,\not 2,\not 3,\not 4,5,\not 6,7,\not 8,\not 9,\not 10,11,\not 12$$ Thus, $\phi(12)=4$.

As one can easily imagine, if a number $n$ gets bigger, computing
$\phi(n)$ will become really a hardship.

The following theorem provides a short cut to computing $\phi(n)$.

Theorem 4. If $k$ and $a$ are positive integers such that all primes dividing
$k$ also divide $a$, then \begin{equation}\label{eq:phi}\phi(ka)=k\phi(a).\end{equation}

Proof. We first write all positive integers that are less than or equal to $ka$: $$\begin{array}{cccc}
1 & 2 & \cdots & a\\a+1 & a+2 & \cdots & 2a\\& & \vdots &\\(k-1)a+1 & (k-1)a+2 & \cdots & ka\end{array}$$ and then cross out the entries that are not relatively prime to $ka$. It is easy to see that this amounts to crossing out everything not relatively prime to $a$. Clearly, any prime that divides $a$ divides $ka$. Conversely, if a prime divides $ka$, then it divides $k$ or $a$. If the prime divides $k$ then by the assumption, it divides $a$ as well. By Theorem 5 here, the pattern of crossing out is the same in each row. Since there are $\phi(a)$ entries left in the first row, there must be $k\phi(a)$ entries left in all. So, $$\phi(ka)=k\phi(a).$$

It would be also interesting to study the relationship between $\phi(pa)$ and $\phi(a)$ when $p\not|a$. First note that if $(a,n)>1$ then clearly $(pa,n)>1$ but the converse need not be true. If a prime number $q>1$ divides $pa$ then $q|p$ or $q|a$. If $q|p$ then $q=p$. That is, if $(pa,n)>1$ then $p|n$ or $(a,n)>1$. After crossing out all $n$ such that $(a,n)>1$, $p\phi(a)$ integers left and yet more to be eliminated, namely, the multiples of $p$, $1p,2p,\cdots,ap$. Of these, those $kp$ such that $(k,a)>1$ have
already been eliminated, and there are just $\phi(a)$ more to cross out. Thus, \begin{align*} \phi(pa)&=p\phi(a)-\phi(a)\\ &=(p-1)\phi(a). \end{align*} Hence, we proved the following theorem.

Theorem 5. Let $a$ be a positive integer and $p$ a prime such that $p\not|a$. Then \begin{equation}\label{eq:phi2}\phi(pa)=(p-1)\phi(a).\end{equation}

Example. \begin{align*} \phi(10^6)&=\phi(10^5\cdot 10)\\ &=10^5\phi(10)\ \mbox{by \eqref{eq:phi}}\\ &=10^5\phi(2\cdot 5)\\ &=10^5(2-1)\phi(5)\ \mbox{by \eqref{eq:phi2}}\\ &=10^5\cdot 4 \ \mbox{by \eqref{eq:phiprime}}\\&=400,000.\\\phi(60)&=\phi(2^2\cdot 3\cdot 5)\\ &=2\phi(2\cdot 3\cdot 5) \ \mbox{by \eqref{eq:phi}}\\ &=2\cdot(2-1)\phi(3\cdot 5) \ \mbox{by \eqref{eq:phi2}}\\ &=2(3-1)\phi(5)\ \mbox{by \eqref{eq:phi2}}\\ &=16 \ \mbox{by \eqref{eq:phiprime}}.\\ \phi(62)&=\phi(2\cdot 31)\\ &=(2-1)\phi(31)\ \mbox{by \eqref{eq:phi2}}\\ &=30\ \mbox{by \eqref{eq:phiprime}}. \end{align*}

Theorem 6. Let $p$ be a prime and $\alpha$ a positive integer. Then
\begin{equation}\label{eq:phiprime2}\phi(p^\alpha)=p^\alpha\left(1-\frac{1}{p}\right).\end{equation}

Proof. It follows immediately from \eqref{eq:phi} and \eqref{eq:phiprime}.\begin{align*}\phi(p^\alpha)&=p\phi(p^{\alpha-1})\\ &=p^2\phi(p^{\alpha-2})\\ &=\cdots\\ &=p^{\alpha-1}\phi(p)\\ &=p^{\alpha-1}(p-1)\\ &=p^{\alpha}\left(1-\frac{1}{p}\right). \end{align*}

Theorem 7 (Chinese Remainder Theorem) Suppose that we want to solve a system of congruences to different moduli: \begin{equation}\begin{aligned}x&\equiv a_1\mod m_1,\\x&\equiv a_2\mod m_2,\\&\cdots\ \ \ \ \ \cdots\\x&\equiv a_r\mod m_r.\end{aligned}\label{eq:congsys}\end{equation}
Suppose that each pair of moduli is relatively prime: $(m_i,m_j)=1$ for $i\ne j$. Then there exists a simultaneous solution $x$ to all of the congruences, and any two solutions are congruent to one another modulo $M=m_1m_2\cdots m_r$.

Proof. First we prove uniqueness modulo $M$. Suppose that $x’$ and $x^{\prime\prime}$
are two solutions to the system of congruences \eqref{eq:congsys}. Let $x=x’-x^{\prime\prime}$. Then for all $i=1,\cdots,r$,\begin{align*}x’&\equiv a_i\mod m_i,\\ x^{\prime\prime}&\equiv a_i\mod m_i.\end{align*}This implies that \begin{align*} x=x’-x^{\prime\prime}\equiv 0\mod m_i&\Longrightarrow x\equiv 0\mod M\ \mbox{by Lemma 3}\\&\Longrightarrow x’\equiv x^{\prime\prime}\mod M. \end{align*} We now show how to construct a solution $x$. For each $i=1,\cdots,r$, define $M_i:=M/m_i$. Then $(m_i,M_i)=1$, so by Bézout’s Lemma there exist $y,z\in\mathbb{Z}$ such that $$M_iy+m_iz=1.$$ This implies that $$M_iy\equiv 1\mod m_i.$$ Write $y:=N_i$, i.e., $$M_iN_i\equiv 1\mod m_i.$$ Set $$x:=\sum_{i=1}^ra_iM_iN_i.$$ Since $m_i|M_j$ whenever $i\ne j$, $$x\equiv a_iM_iN_i\equiv a_i\mod m_i.$$

Corollary 8. The Euler phi function is multiplicative, i.e., $$\phi(mn)=\phi(m)\phi(n)$$ whenever $(m,n)=1$.

Proof. We must count the number of integers between $0$ and $mn-1$ which have no common factor with $mn$. For each $0\leq j\leq mn-1$, let $j_1$ be its least nonnegative residue$\mod m$ (i.e., $0\leq j_1<m$ and $j\equiv j_1\mod m$) and $j_2$ be its least nonnegative residue$\mod n$ (i.e., $0\leq j_2<n$ and $j\equiv j_2\mod n$). It follows from the Chinese Remainder Theorem (Theorem 7) that for each pair $j_1,j_2$ there is one and only one $j$ between $0$ and $mn-1$ for which $$j\equiv j_1\mod m,\ j\equiv j_2\mod n.$$ Notice that $j$ has no common factor with $mn$ if and only if it has no common factor with $m$ (which is equivalent to $j_1$ having no common factor with $m$) and $j$ has no common factor with $n$ (which is equivalent to $j_2$ having no common factor with $n$). Thus, the $j$’s which we must count are in $1:1$ correspondence with the pairs $j_1,j_2$ for which $$0\leq j_1<m,\ (j_1,m)=1;\ 0\leq j_2<n,(j_2,n)=1.$$ The number of possible $j_1$’s is $\phi(m)$ and the number of possible $j_2$’s is $\phi(n)$. So, the number of pairs is $\phi(m)\phi(n)$.

Corollary 9. For any positive integer $n$,\begin{equation}\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right).\end{equation}

Proof. Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $n$. Then by Corollary 8, \begin{align*}\phi(n)&=\phi(p_1^{\alpha_1})\phi(p_2^{\alpha_2})\cdots\phi(p_r^{\alpha_r})\\ &=p_1^{\alpha_1}\left(1-\frac{1}{p_1}\right)p_2^{\alpha_2}\left(1-\frac{1}{p_2}\right)\cdots p_r^{\alpha_r}\left(1-\frac{1}{p_r}\right)\ \mbox{by \eqref{eq:phiprime2}}\\&=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_r}\right)\\&=n\prod_{p|n}\left(1-\frac{1}{p}\right).\end{align*}

Example. \begin{align*}\phi(60)&=\phi(2^2\cdot 3\cdot 5)\\&=60\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\\&=16.\\\phi(62)&=\phi(2\cdot 31)\\ &=62\left(1-\frac{1}{2}\right)\left(1-\frac{1}{31}\right)\\&=30.\\\phi(360)&=\phi(2^3\cdot 3^2\cdot 5)\\&=360\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\\&=96.\end{align*}

The following theorem is a generalization of Fermat’s Little Theorem
(Theorem 1) due to Euler.

Theorem 10 (Euler-Fermat Theorem). If $(a,m)=1$ then \begin{equation}\label{eq:euler} a^{\phi(m)}\equiv 1\mod m.\end{equation}

Proof. First consider the case when $m$ is a prime power, say $m=p^\alpha$.
We use induction on $\alpha$. The case $\alpha=1$ is precisely Fermat’s Little Theorem. Suppose that $\alpha\geq 2$ and the formula
\eqref{eq:euler} holds for the $(\alpha-1)$-st power of $p$. Then \begin{align*} \phi(p^{\alpha-1})&=p^{\alpha-1}\left(1-\frac{1}{p}\right)\\&=p^{\alpha-1}-p^{\alpha-2}\end{align*} and \begin{align*}a^{\phi(p^{\alpha-1})}&=a^{p^{\alpha-1}-p^{\alpha-2}}\\&\equiv 1\mod p^{\alpha-1}.\end{align*} That is,
$$a^{p^{\alpha-1}-p^{\alpha-2}}=1+p^{\alpha-1}b\ \mbox{for some}\ b\in\mathbb{Z}.$$ Thus, \begin{align*}a^{\phi(p^\alpha)}&=(a^{p^{\alpha-1}-p^{\alpha-2}})^p\\&=(1+p^{\alpha-1}b)^p.\end{align*} Note that the binomial coefficients of $(1+x)^p$ are each divisible by $p$ except in the $1$ and $x^p$ in the ends. This means the binomial coefficients of $(1+p^{\alpha-1}b)^p$ are each divisible by $p^\alpha$ except in the $1$ and $p^{p(\alpha-1)}b^p$ in the ends. Now, $$p^{p(\alpha-1)}b^p=p^\alpha p^{p(\alpha-1)-\alpha}b^p.$$ Since $p$ is a prime, $p\geq 2$. So, \begin{align*}p(\alpha-1)-\alpha&\geq 2(\alpha-1)-\alpha\\&=\alpha-2\geq 0\ \mbox{by assumption}.\end{align*}This means $p^{p(\alpha-1)}b^p$ is also divisible by $p^\alpha$. Hence, $$a^{\phi(p^\alpha)}\equiv 1\mod p^\alpha.$$ Let $m=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $m$. Then by the multiplicity of $\phi$ (Corollary 8), \begin{align*}\phi(m)&=\phi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r})\\&=\phi(p_1^{\alpha_1})\cdots \phi(p_r^{\alpha_r}).\end{align*} For each $i=1,\cdots,r$, $$a^{\phi(p_i^{\alpha_i})}\equiv 1\mod p_i^{\alpha_i}.$$
Let $M_i:=\phi(m)/\phi(p_i^{\alpha_i})$ for $i=1,\cdots,r$. Then \begin{align*} a^{\phi(m)}&=a^{\phi(p_1^{\alpha_1})\cdots \phi(p_r^{\alpha_r})}\\&=(a^{\phi(p_i^{\alpha_i})})^{M_i}\\&\equiv 1\mod p_i^{\alpha_i}.\end{align*}
Since $(p_i^{\alpha_i},p_j^{\alpha_j})=1$ if $i\ne j$, $$a^{\phi(m)}\equiv 1\mod m=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$$ by Lemma 3.

Remark. Suppose that $a$ is any positive integer such that $(a,105)=1$.
\begin{align*}\phi(105)&=\phi(3\cdot 5\cdot 7)\\&=105\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)\left(1-\frac{1}{7}\right)\\&=48.\end{align*}So, by Euler’s Theorem (Theorem 10) $$a^{48}\equiv 1\mod 105.$$ As we have seen in the proof of Theorem 10, there is a smaller power of $a$ which gives $1\mod m=105=3\cdot 5\cdot 7$. \begin{align*}a^{\phi(3)}=a^2\equiv 1\mod 3,\\ a^{\phi(5)}=a^4\equiv 1\mod 5,\\ a^{\phi(7)}=a^6\equiv 1\mod 7.\end{align*}
The least common multiple of $\phi(3)=2,\phi(5)=4,\phi(7)=6$ is 12 and so
\begin{align*}a^{12}&\equiv 1\mod 3,\\ a^{12}&\equiv 1\mod 5,\\ a^{12}&\equiv 1 \mod 7.\end{align*} By Lemma 3, $$a^{12}\equiv 1\mod3\cdot 5\cdot 7=105.$$

Example. Compute $2^{1000000}\mod 77$.

Solution: $77=7\cdot 11$ and $\phi(7)=6,\ \phi(11)=10$. The least common multiple of $6$ and $10$ is $30$. So, $$2^{30}\equiv 1\mod 77.$$ Since $1000000=30\cdot 33333+10$, $$2^{1000000}\equiv 2^{10}\mod 77\equiv 23\mod 77.$$

There is an alternative way to calculate $2^{1000000}\mod 77$. First compute $2^{1000000}\mod 7$. $$2^{\phi(7)}=2^6\equiv 1\mod 7.$$ Since $1000000=6\cdot 166666+4$, $$2^{1000000}\equiv 2^4\equiv 2\mod 7.$$ On the other hand,
$$2^{10}\equiv 1\mod 11.$$ So, $$2^{1000000}\equiv 1\mod 11.$$ We now find $0\leq x\leq 76$ which satisfies \begin{align*}x&\equiv 2\mod 7\\ x&\equiv 1\mod 11\end{align*} by the Chinese Remainder Theorem (Theorem 7). Let $M=7\cdot 11=77$, $M_1=11$, and $M_2=7$. Since $(7,11)=1$, there exist $y,z\in\mathbb{Z}$ such that $7y+11z=1$. By Euclidean algorithm, one can find solution $y=-3$, $z=2$. Thus, \begin{align*}a_1&=2,\ m_1=7,\ M_1=11,\ N_1=2,\\ a_2&=1,\ m_2=11,\ M_2=7,\ N_2=-3.\end{align*} Hence, \begin{align}x&=\sum_{i=1}^2a_iM_iN_i\ &=23\mod 77.\end{align}

Theorem. \begin{equation}\sum_{d|n}\phi(d)=n.\end{equation}

Proof. Let $$f(n):=\sum_{d|n}\phi(d).$$ First we show that $f(n)$ is multiplicative. Suppose that $(m,n)=1$ and $d|mn$. Then $d$ can be written in the form $d=d_1d_2$ such that $d_1|m$ and $d_2|n$. Since $(d_1,d_2)=1$, by Corollary 8, $$\phi(d)=\phi(d_1d_2)=\phi(d_1)\phi(d_2).$$
Now, \begin{align*}f(mn)&=\sum_{d|mn}\phi(d)\\&=\sum_{d_1|m}\sum_{d_2|n}\phi(d_1)\phi(d_2)\\&=\sum_{d_1|m}\phi(d_1)\left(\sum_{d_2|n}\phi(d_2)\right)\\&=\sum_{d_1|m}\phi(d_1)f(n)\\&=f(n)\sum_{d_1|m}\phi(d_1)\\&=f(m)f(n).\end{align*} Let $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ be the prime factorization of $n$. Then
$$f(n)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})\cdots f(p_r^{\alpha_r})$$ and for each $i=1,\cdots, r$, \begin{align*}f(p_i^{\alpha_i})&=\sum_{d|p_i^{\alpha_i}}\phi(d)\\&=\sum_{j=0}^{\alpha_i}\phi(p_i^j)\\&=\sum_{j=1}^{\alpha_i}p_i^j\left(1-\frac{1}{p_i}\right)+1\\&=\sum_{j=1}^{\alpha_i}(p_i^j-p_i^{j-1})+1\\&=p_i^{\alpha_i}.\end{align*} Therefore, $$f(n)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}=n.$$

Congruences 1

Definition. Let $m>0$. We say that $a$ is congruent to $b$ modulo $m$ and write $a\equiv b\mod m$ if $m|b-a$.

Example. Since $6|7-1$, $1\equiv 7\mod 6$. Since $6|13-1$, $1\equiv 13\mod 6$. Since $6\not|7-2$, $7\not\equiv 2\mod 6$.

Theorem 1. Let $a,a’,b,b’,c,d$, and $m$ be integers with $d>0$ and $m>0$. Then

  1. $a\equiv a\mod m$.
  2. If $a\equiv b\mod m$ then $b\equiv a\mod m$.
  3. If $a\equiv b\mod m$ and $b\equiv c\mod m$ then $a\equiv c\mod m$.
  4. If $a\equiv b\mod m$ and $a’\equiv b’\mod m$ then $a+a’\equiv b+b’\mod m$.
  5. If $a\equiv b\mod m$ and $a’\equiv b’\mod m$ then $aa’\equiv bb’\mod m$.
  6. If $a\equiv b\mod m$ and $d|m$ then $a\equiv b\mod d$.

Proof.

  1. Since $m|0=a-a$, $a\equiv a\mod m$.
  2. Let $a\equiv b\mod m$. Then $m|b-a$ and so $b-a=mk$ for some $k\in\mathbb{Z}$. Since $a-b=m(-k)$ and $-k\in\mathbb{Z}$, then $m|a-b$, i.e., $b\equiv a\mod m$.
  3. Suppose that $a\equiv b\mod m$ and $b\equiv c\mod m$. Then $m|b-a$ and $m|c-b$, so $$m|(b-a)+(c-b)=c-a.$$ Hence, $a\equiv c\mod m$.
  4. Suppose that $a\equiv b\mod m$ and $a’\equiv b’\mod m$. Then $m|b-a$ and $m|b’-a’$, so $$m|(b-a)+(b’-a’)=(b+b’)-(a+a’),$$ that is, $a+a’\equiv b+b’\mod m$.
  5. Suppose that $a\equiv b\mod m$ and $a’\equiv b’\mod m$. Then $m|b-a$ and $m|b’-a’$. Now, $$bb’-aa’=(b-a)a’+(b’-a’)b.$$ Since $m|b-a$ and $m|b’-a’$, $m|bb’-aa’$, i.e., $aa’\equiv bb’\mod m$.
  6. If $a\equiv b\mod m$ then $m|b-a$. If $d|m$ then $d|b-a$ and so $a\equiv b\mod d$.

Remark 1. Properties 1-3 tell us that $\equiv\mod m$ is an equivalence relation on $\mathbb{Z}$. Properties 1-5 tell us that $\equiv\mod m$ is a congruence relation, an equivalence relation that preserves operations, on $\mathbb{Z}$. One could easily guess that $\equiv\mod m$ is where the name congruence relation is originated from. For more details about congruence relation, see the reference [1] below.

Definition. If $m>0$ and $r$ is the remainder when the division algorithm is used to divide $b$ by $m$, then $r$ is called the least residue of $b$ modulo $m$.

Example.

  1. The least residue of $12\mod 7$ is $5$.
  2. The least residue of $20\mod 4$ is $0$.
  3. The least residue of $-12\mod 7$ is $2$.
  4. The least residue of $-3\mod 7$ is $4$.

Theorem 2. Let $m>0$. Then

  1. If $r$ and $b$ are integers such that $r\equiv b\mod m$ and $0\leq r<m$, then $r$ is the least residue $\mod m$.
  2. Two integers are congruent $\mod m$ if and only if they have the same least residue $\mod m$.

Proof.

  1. Suppose that $r\equiv b\mod m$. Then $m|b-r$ and so $b=mq+r$ for some $q\in\mathbb{Z}$. If $0\leq r<m$ then by the uniqueness of the quotient and the remainder, $r$ must be the least residue $\mod m$.
  2. Suppose that $b$ and $b’$ have the same remainder when divided by $m$, say $$b=mq+r\ {\rm and}\ b’=mq’+r$$ for some $q,q’\in\mathbb{Z}$. Then $b-b’=m(q-q’)$ and so $b\equiv b’\mod m$. Conversely, suppose that $b=b’\mod m$ and $b=mq+r$ with $0\leq r<m$. Then $b’=b\mod m$ and $b\equiv r\mod m$, thus $b’\equiv r\mod m$. Therefore by part 1, $r$ is the least residue of $b’\mod m$.

Example. Find the least residue of $33\cdot 26^2\mod 31$.

Solution: $33\equiv 2\mod 31$ and $26\equiv -5\mod 31$. So, \begin{align*} 33\cdot 26^2&\equiv 2\cdot (-5)^2\mod 31\\ &\equiv 50\mod 31\\ &\equiv 19\mod 31.\end{align*} Since $0\leq 19<31$, the least residue is $19$.

Theorem 3 (The Cancellation Theorem). If $a,b>0$, $x$ and $x’$ are integers such that $(a,b)=1$, then $ax\equiv ax’\mod b$ implies $x\equiv x’\mod b$.

The following example shows that the Cancellation Theorem does not necessarily hold unless the condition $(a,b)=1$ is satisfied.

Example. $(2,4)=2\ne 1$. $2\cdot 1\equiv 2\cdot 3\mod 4$ but $1\not\equiv 3\mod4$.

The Cancellation Theorem is a special case of the following more general theorem.

Theorem 4. If $a,b>0$, $x$ and $x’$ are integers such that $(a,b)=d$, then
$ax\equiv ax’\mod b$ if and only if $x\equiv x’\mod b/d$.

Proof. \begin{align*} ax\equiv ax’\mod b&\Longrightarrow b|a(x-x’)\\ &\Longrightarrow a(x-x’)=bk\ \mbox{for some}\ k\in\mathbb{Z}\\ &\Longrightarrow \frac{a}{d}(x-x’)=\frac{b}{d}k\\ &\Longrightarrow \frac{b}{d}|\frac{a}{d}(x-x’)\\ &\Longrightarrow \frac{b}{d}|x-x’\ \mbox{since}\ \left(\frac{a}{d},\frac{b}{d}\right)=1\\ &\Longrightarrow x\equiv x’\mod\frac{b}{d}. \end{align*} Conversely, if $x\equiv x’\mod\frac{b}{d}$, then
\begin{align*} x’-x=\frac{b}{d}k\ \mbox{for some}\ k&\Longrightarrow ax’-ax=b\left(\frac{a}{d}\right)k\\ &\Longrightarrow ax\equiv ax’\mod b. \end{align*}

Theorem 5. If $a>0, b$, and $b’$ are integers such that
$b\equiv b’\mod a$, then $(a,b)=(a,b’)$.

Proof. \begin{align*} b\equiv b’\mod a&\Longrightarrow b’-b=aq\ \mbox{for some}\ q\in\mathbb{Z}\\ &\Longrightarrow b’=b+aq\\ &\Longrightarrow (a,b)=(a,b’) \end{align*} by Lemma 3 here.

As mentioned in Remark 1, $\equiv\mod m$ is an equivalence relation on $\mathbb{Z}$. For fixed $m$, each equivalence class with respect to $\equiv\mod m$ has one and only one representative between $0$ and $m-1$. Denote by $\mathbb{Z}/m\mathbb{Z}$ or $\mathbb{Z}_m$ the set of all equivalence classes, called the residue classes. Then
$$\mathbb{Z}/m\mathbb{Z}=\{[0],[1],\cdots,[m-1]\}.$$
Often $\mathbb{Z}/m\mathbb{Z}$ is written simply as
$$\mathbb{Z}/m\mathbb{Z}=\{0,1,\cdots,m-1\},$$
i.e, those residue classes are represented by their representatives (typically those least residues $\mod m$) unless there is a confusion.

Define the binary operations $+$ and $\cdot$ on $\mathbb{Z}/m\mathbb{Z}$: For any $[a],[b]\in\mathbb{Z}/m\mathbb{Z}$,
$$[a]+[b]:=[a+b],\ [a]\cdot[b]:=[a\cdot b].$$
Then $+$ and $\cdot$ are well-defined due to properties (4) and (5), respectively in Theorem 1.

Theorem 6. $(\mathbb{Z}/m\mathbb{Z},+,\cdot)$ is a commutative ring with unity.

Consider $\mathbb{Z}/9\mathbb{Z}$. Its multiplication table is given by
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\\hline 2 & 0 & 2 & 4 & 6 & 8 & 1 & 3 & 5 & 7\\\hline 3 & 0 & 3 & 6 & 0 & 3 & 6 & 0 & 3 & 6\\\hline 4 & 0 & 4 & 8 & 3 & 7 & 2 & 6 & 1 & 5\\\hline 5 & 0 & 5 & 1 & 6 & 2 & 7 & 3 & 8 & 4\\\hline
6 & 0 & 6 & 3 & 0 & 6 & 3 & 0 & 6 & 3\\\hline 7 & 0 & 7 & 5 & 3 & 1 & 8 & 6 & 4 & 2\\\hline 8 & 0 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\\hline\end{array}$$
As one can see clearly, not every nonzero element of $\mathbb{Z}/9\mathbb{Z}$ has a multiplicative inverse. So, $\mathbb{Z}/9\mathbb{Z}$ cannot be a field. However, there are elements of $\mathbb{Z}/9\mathbb{Z}$ that have multiplicative inverses. They are $1,2,4,5,7,8$. As representatives of residue classes, they are all relatively prime to $9$. In fact, the following theorem holds in general.

Theorem 7. The elements of $\mathbb{Z}/m\mathbb{Z}$ which have multiplicative inverses are those which are relatively prime to $m$, i.e., the numbers $a$ for which there exists $b$ with $ab\equiv 1\mod m$ are precisely those $a$ for which $(a,m)=1$.

Proof. Let $d=(a,m)$ and suppose that there exists $b\in\mathbb{Z}$ such that $ab\equiv 1\mod m$. Then by property 6 in Theorem 1 $ab\equiv 1\mod d$. Since $d|a$, $d$ must divide $1$, i.e., $d=1$. Conversely, if $(a,m)=1$ then by Bézout’s Lemma (Theorem 5 here), there exist $x,y\in\mathbb{Z}$ such that $ax+my=1$. Choose $b=x$. Then $ab\equiv 1\mod m$.

Definition. If $(a,m)=1$ then by negative power $a^{-n}\mod m$ we mean the $n$-th powers of the inverse residue class, i.e., it is represented by the $n$-th power of any integer $b$ for which $ab\equiv 1\mod m$.

Example. Find $160^{-1}\mod 841$, i.e., the inverse of $160\mod 841$.

Solution: First check if $(160,841)=1$ by the Euclidean algorithm.
\begin{align*} 841&=160\cdot 5+41,\\ 160&=41\cdot 3+37,\\ 41&=37\cdot 1+4,\\ 37&=4\cdot 9+1. \end{align*} So, $(160,841)=1$. Now by working backward, let us find $b$ such that $160\cdot b\equiv 1\mod 841$. \begin{align*} 1&=37-4\cdot 9\\ &=37-(41-37)9\\ &=10\cdot 37-9\cdot 41\\ &=10(160-3\cdot 41)-9\cdot 41\\ &=10\cdot 160-39\cdot 41\\ &=10\cdot 160-39(841-5\cdot 160)\\ &=205\cdot 160-39\cdot 841.\end{align*} Hence, $b=205=160^{-1}$.

Corollary 8. If $p$ is a prime number then every nonzero residue class has a multiplicative inverse, i.e, $\mathbb{Z}/p\mathbb{Z}$ is a field. We often denote this finite field of $p$ elements by $\mathbb{F}_p$.

Corollary 9. Suppose $0\leq a,b<m$. If $(a,m)=1$ then there exists $x_0\in\mathbb{Z}$ such that $ax_0\equiv b\mod m$ and all solutions of $ax\equiv b\mod m$ are of the form $x=x_0+mn$ for $n$ an integer. If $(a,m)=d$ then there exists $x\in\mathbb{Z}$ such that $ax\equiv b\mod m$ if and only if $d|b$ and in that case our congruence is equivalent to the congruence $a’x\equiv b’\mod m’$, where $a’=a/d,b’=b/d,m’=m/d$.

Proof. If $(a,m)=1$ then there exists $a^{-1}\in\mathbb{Z}$ such that $a\cdot a^{-1}\equiv 1\mod m$, so $a\cdot (a^{-1}b)\equiv b\mod m$. Choose $x_0=a^{-1}b$. Since $(a,m)=1$, by Theorem 7 here, all solutions of equation $ax\equiv b\mod m$ or equivalently $ax+mq=b$ for some $q\in\mathbb{Z}$ are given in the form $$x=x_0+mn$$ for some $n\in\mathbb{Z}$. Let $(a,m)=d$. If there exists $x\in\mathbb{Z}$ such that $ax\equiv b\mod m$, then clearly $d|b$. Conversely, suppose that $d|b$. Since $(a/d,m/d)=1$, there exists $x\in\mathbb{Z}$ such that $\frac{a}{d}x\equiv\frac{b}{d}\mod\frac{m}{d}$ and this is clearly equivalent to $ax\equiv b\mod m$.

References:

  1. Stanley Burris and H. P. Sankappanavar, A Course in Universal Algebra, Springer-Verlag, 1981

Linear Combination

Theorem 1. Given integers $a$, $b$, and $c$ with $a$ and $b$ not both $0$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=c$ if and only if $(a,b)|c$.

Proof. Left as an exercise.

Corollary 2. Let $a$ and $b$ be integers. Then there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$ if and only if $(a,b)=1$ i.e. $a$ and $b$ are relatively prime.

Corollary 3. Let $a,a’,b\in\mathbb{Z}$. If $(a,b)=1$ and $(a’,b)=1$, then $(aa’,b)=1$.

Proof. Since $(a,b)=1$ and $(a’,b)=1$, there exist $x,y,x’,y’\in\mathbb{Z}$ such that $ax+by=1$ and $a’x’+by’=1$. Now, \begin{align*}1&=(ax+by)(a’x’+by’)\\&=aa’xx’+b(axy’+a’x’y+byy’)\end{align*} Hence, $(aa’,b)=1$.

Theorem 4. If $a,b$ and $c$ are integers such that $(a,b)=1$ and $a|bc$, then $a|c$.

Proof. Since $(a,b)=1$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$. So, we obtain $acx+bcy=c$. Since $a|ac$ and $a|bc$, $a|c$.

Remark. $a|bc$ does not necessarily imply that $a|b$ or $a|c$. For example, $6|36=4\cdot 9$ but $6\not|4$ and $6\not|9$. However, the following theorem holds.

Theorem 5. If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

Proof. Let $p$ be a prime number and $p|ab$. Suppose that $p\not|a$ and $p\not|b$. Since $p$ is prime and $p\not|a$, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$ but this is a contradiction to the assumption that $p\not|b$. Therefore, $p|a$ or $p|b$.

Theorem 6. If $a$ and $b$ are integers and $(a,b)=d$, then $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.

Proof. Since $(a,b)=d$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=d$. Dividing the equation by $d$, we obtain

$\frac{a}{d}x+\frac{b}{d}y=1$. By theorem 1, this implies that $\left(\frac{a}{d},\frac{b}{d}\right)=1$.

Example 1. Consider the equation $9x+24y=15$. Since $(9,24)=3$ and $3|15$, from theorem 1, we know that a solution exist. First, we can find a solution to $9x+24y=3$ using the Euclidean algorithm as seen before. \begin{align*}24&=9\cdot 2+6\\9&=6\cdot 1+3\\6&=3\cdot 2+0\end{align*} Thus, \begin{align*}3&=9-6\cdot 1\\&=9-(24-9\cdot 2)\cdot 1\\&=9\cdot 3+24\cdot(-1)\end{align*} Hence, $x’=3$ and $y’=-1$ is a solution to $9x+24y=3$ and thereby $x=5x’=15$ and $y=5y’=-5$ is a solution to $9x+24y=15$. Finding a solution is not a big deal. But there are other solutions. For instance, $x=-1$ and $y=1$ is also a solution to $9x+24y=15$. How do we find other solutions? We now turn our attention to this question.

Suppose that $(x_0,y_0)$ is a solution to \begin{equation}\label{eq:lineqn}ax+by=c\end{equation} Then \begin{equation}\label{eq:lineqn2}ax_0+by_0=c\end{equation} Subtracting \eqref{eq:lineqn2} from \eqref{eq:lineqn}, we obtain \begin{equation}\label{eq:lineqn3}a(x-x_0)=b(y_0-y)\end{equation} Let $d=(a,b)$. Dividing \eqref{eq:lineqn3} by $d$, we obtain \begin{equation}\label{eq:lineqn4}\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y)\end{equation} This means that $\frac{a}{d}|\frac{b}{d}(y_0-y)$. Since $\left(\frac{a}{d},\frac{b}{d}\right)=1$, by theorem 2, $\frac{a}{d}|y_0-y$ and so, $y_0-y=\frac{a}{d}t$ for some $t\in\mathbb{Z}$. From \eqref{eq:lineqn4} we also obtain $x-x_0=\frac{b}{d}t$. Therefore, $x$ and $y$ are written as \begin{equation}\label{eq:lineqnsol}x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t\end{equation} where $t\in\mathbb{Z}$. Conversely, any $(x,y)$ in the form \eqref{eq:lineqnsol} satisfies the equation \eqref{eq:lineqn}. $$a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)=ax_0+by_0=c$$

Theorem 7. Suppose that $a\ne 0$, $b\ne 0$, and $c$ are integers. Let $(x_0,y_0)$ be a particular solution to $ax+by=c$. Then all solutions to $ax+by=c$ are given by $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$ where $t\in\mathbb{Z}$ and $(a,b)=d$.

Example. In example 1, we found $(x_0,y_0)=(15,-5)$. So by theorem 6, all solutions to $9x+24y=15$ are given by $$x=15+7t,\ y=-5-3t$$ where $t\in\mathbb{Z}$.

Example. Find all positive integers $x,y$ such that $4x+6y=100$.

Solution. $(4,6)=2$ and $2|100$, so a solution exists.

$6=4\cdot 1+2$ i.e. $2=4\cdot (-1)+6\cdot 1$. $x_0=-50$ and $y_0=50$ is a particular solution to $4x+6y=100$. By theorem 3, all solutions are given by $$x=-50+3t,\ y=50-2t$$ where $t\in\mathbb{Z}$. Since $x$ and $y$ are required to be positive, we find that $17\leq t\leq 24$. The following table shows all those solutions. $$\begin{array}{|c||c|c|c|c|c|c|c|c|}\hline t & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\\hline x & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\\hline y & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2\\\hline\end{array}$$

Example. A man paid \$ 11.37 for some 39-cent pens and 69-cent pens. How many of each did he buy?

Solution. The problem is equivalent to solving the equation \begin{equation}\label{eq:pen}39x+69y=1137\end{equation} where $x$ and $y$ are nonnegative integers. $(39,69)=3$ and $3|1137$, so the equation has a solution. Solving the equation \eqref{eq:pen} is equivalent to solving \begin{equation}\label{eq:pen2}13x+23y=379\end{equation} where $x$ and $y$ are nonnegative integers. Since $(13,23)=1$, by the Euclidean algorithm, one can find a solution $x’=-7$ and $y’=4$ to $13x+23y=1$. $x_0=379x’=-2653$ and $y_0=379\cdot y’=1516$ is then a solution to \eqref{eq:pen2}. By theorem 3, all integer solutions to \eqref{eq:pen2} are given by $$x=-2653+23t,\ y=1516-13t,\ t\in\mathbb{Z}$$ From the conditions $x\geq 0, y\geq 0$, we obtain the inequality $115\frac{8}{23}\leq t\leq 116\frac{8}{23}$. There is only one integer $t=116$ that satisfies the inequality. $x=-2653+23\cdot 116=15$ and $y=1516-13\cdot 116=8$. So, the man bought 15 39-cent pens and 8 69-cent pens.

The Division Algorithm

Theorem 1. Suppose that $a,b\in\mathbb{Z}$ with $0<a<b$. Then there exists uniquely $q,r\in\mathbb{Z}$, $0\leq r<a$, such that
$$b=aq+r$$

Theorem 2. If $a$ and $b$ are positive integers, then
$$(a,b)[a,b]=ab$$

Suppose that $0<a<b$. Then by the division algorithm, there exist uniquely $q,r\in\mathbb{Z}$ such that $b=aq+r$ where $0\leq r<a$. If $d=(a,b)$ then $d|r$. This means $d\leq(a,r)$ since $d$ is a common divisor of $a$ and $r$. Since $(a,r)|a$ and $(a,r)|b$, $(a,r)$ is a common divisor of $a$ and $b$. This implies $(a,r)\leq(a,b)=d$. Thus, $d=(a,r)=(a,b)$. Therefore, we have the following lemma.

Lemma 3. For any integers $a>0$, $b$, $c$ and $k$, if $a=bk+c$ then $(a,b)=(b,c)$.

Example. Let $a=123$ and $b=504$. Then
$$504=123\cdot 4+12$$
By Lemma, we have
$$(123,504)=(12,123)$$
$$123=12\cdot 10+3$$
By Lemma again, we have
$$(12,123)=(3,12)=3$$
Hence, we obtain $(123,504)=3$.

Theorem 4. (The Euclidean Algorithm) Let $a$ and $b$ be integers, $0<a<b$. Apply the division algorithm repeatedly as follows. \begin{align*}b&=aq_1+r_1,\ 0<r_1<a\\a&=r_1q_2+r_2,\ 0<r_2<r_1\\r_1&=r_2q_3+r_3,\ 0<r_3<r_2\\&\vdots\\r_{n-2}&=r_{n-1}q_n+r_n,\ 0<r_n<r_{n-1}\\r_{n-1}&=r_nq_{n+1}\end{align*}Let $r_n$ be the last nonzero remainder. Then $(a,b)=r_n$

Example. Compute $(158,188)$ using the Euclidean algorithm.
\begin{align*}188&=158\cdot 1+30\\158&=30\cdot 5+8\\30&=8\cdot 3+6\\8&=6\cdot 1+2\\6&=2\cdot 3+0 \end{align*} Hence, $(158,188)=2$.

It is possible to use the Euclidean algorithm to write $(a,b)$ in the form $ax+by$. In the above example, \begin{align*}2&=8-6\cdot 1\\&=8-(30-8\cdot 3)\cdot 1\\&=-30+8\cdot 4\\&=-30+(158-30\cdot 5)\cdot 4\\&=158\cdot 4-30\cdot 21\\&=158\cdot 4-(188-158\cdot 1)\cdot 21\\&=158\cdot 25+188\cdot(-21) \end{align*}
In general, the following property holds.

Theorem 5. (Bézout’s Lemma) If $a$ and $b$ are integers such that $(a,b)$ is defined, then there exist $x,y\in\mathbb{Z}$ such that
\begin{equation}
\label{eq:bezout}
(a,b)=ax+by
\end{equation}

\eqref{eq:bezout} is called the Bézout’s identity.

Corollary 6. If $d$ is any common divisor of $a$ and $b$, not both of which are $0$, then $d|(a,b)$.

Definition. We say $k$ is a linear combination of $a$ and $b$ if there exist $x,y\in\mathbb{Z}$ such that $k=ax+by$.

Theorem 7. Given integers $a\ne 0$ and $b\ne 0$, and $m$, if $a|m$ and $b|m$ then $[a,b]|m$.

Proof. Assume that $\frac{m}{[a,b]}$ is not an integer. Then there exist $q,r\in\mathbb{Z}$ such that $m=[a,b]q+r$, $0<r<[a,b]$. The remainder $r$ is then written as $r=m-q[a,b]$. By assumption, $a|m$, and also $a|[a,b]$. So, $a|r$. By the same argument, we also obtain $b|r$. This means that $r$ is a common multiple of $a$ and $b$. But it is a contradiction to the fact that $0<r<[a,b]$. Hence, $r=0$.

Remark. This theorem and the preceding corollary are dual to each other.

Divisibility

Definition. We say $a$ divides $b$ and write $a|b$ if there exists $d\in\mathbb{Z}$ such that $b=ad$. We say that $a$ is a divisor of $b$ and that $b$ is a multiple of $a$. If $a|b$ is false, we write $a\not|b$.

Definition. We say $d$ is the greatest common divisor (gcd in short) of $a$ and $b$ if $d$ is the largest of all integers dividing both $a$ and $b$. We write $d=(a,b)$.

Example. Let $a=4$ and $b=6$. The divisors of $4$ are $1$, $-1$, $2$, $-2$, $4$, $-4$. The divisors of $6$ are $1$, $-1$, $2$, $-2$, $3$, $-3$, $6$, $-6$. So the common divisors of $4$ and $6$ are $1$, $-1$, $2$, $-2$ and $2=(4,6)$.

Definition. We say $m$ is the least common multiple (lcm in short) of $a$ and $b$ if $m$ is the smallest of all the positive integers that are multiples of both $a$ and $b$. We write $m=[a,b]$.

Example. Let $a=4$ and $b=6$. The positive multiples of $4$ are $4$, $8$, $12$, $16$, $20$, $24$, $28$, $\cdots$ and the positive multiples of $6$ are $6$, $12$, $18$, $24$, $30$, $\cdots$. Common positive multiples of $4$ and $6$ are $12$, $24$, $\cdots$ and $[4,6]=12$.

Theorem. Given integers $a$, $b$, and $c$,

  1. if $a|b$ then $a|bc$.
  2. if $a|b$ and $b|c$ then $a|c$.
  3. if $a|b$ and $a|c$ then $a|bx+cy$ for any $x,y\in\mathbb{Z}$.

Proof.

  1. If $a|b$ then there exists $d\in\mathbb{Z}$ such that $b=ad$. Now $bc=(ad)c=a(dc)$ and $dc\in\mathbb{Z}$ and hence $a|bc$.
  2. Let $a|b$ and $b|c$. Then there exist $d_1,d_2\in\mathbb{Z}$ such that $b=ad_1$ and $c=bd_2$. Now we have
    $$c=bd_2=(ad_1)d_2=a(d_1d_2)$$
    and $d_1d_2\in\mathbb{Z}$. Hence, $a|c$.
  3. Let $a|b$ and $a|c$. Then there exist $d_1,d_2\in\mathbb{Z}$ such that $b=ad_1$ and $c=ad_2$. For any $x,y\in\mathbb{Z}$ \begin{align*} bx+cy&=(ad_1)x+(ad_2)y\\&=a(d_1x+d_2y) \end{align*}
    and $d_1x+d_2y\in\mathbb{Z}$. Hence, $a|bx+cy$.