Basic Ideas of Cryptography and Some Simple Cryptosystems

Cryptography is the study of methods of sending messages in disguised form. The message we want to send is called the plaintext and the disguised message is called the ciphertext. The process of converting a plaintext to a ciphertext is enciphering or encryption and the reverse process is deciphering or decryption. The plaintext and ciphertext are broken up into multiple message units (a single letter, a pair of letters, a triple of letters, …). An enciphering transformation is a function that takes any plaintext message unit and gives us a ciphertext message unit. Let $\mathcal{P}$ be the set of all possible plaintext massage units and $\mathcal{C}$ the set of all possible ciphertext message units. Then an enciphering transformation can be represented as a function $f: \mathcal{P}\longrightarrow\mathcal{C}$ (assumed to be a one-to-one correspondence) and the deciphering transformation is its inverse function $f^{-1}:\mathcal{C}\longrightarrow\mathcal{P}$. The functional composition
$$\mathcal{P}\stackrel{f}{\longrightarrow}\mathcal{C}\stackrel{f^{-1}}{\longrightarrow}\mathcal{P}$$
is a cryptosystem.

Making a Cryptosystem

First step is to label all possible plaintext message units and ciphertext message units by means of mathematical objects. For example, if our plaintext and ciphertext message units are single letters from A-Z and the blank, then we can label them as $0,1,2,\cdots,26$.

ABCDEFGHIJKLMN
012345678910111213
OPQRSTUVWXYZblank
14151617181920212223242526

If we use digraphs, length-2 strings of letters, as message units, then we can label the digraph whose two letters correspond to $x,y\in\{0,1,2,\cdots,26\}$ by the integer $27x+y\in\{0,1,2,\cdots,728\}$. So, we view the individual letters as digits to the base 27 and the digraph as a 2-digit integer to that base. For instance, the digraph NO corresponds to $27\cdot 13+14=365$.

Example. Suppose we use the 26-letter alphabet A-Z with numerical equivalents 0-25. Let $P\in\{0,1,2,\cdots,25\}$ denotes a plaintext message unit. Define $f:\{0,1,2,\cdots,25\}\longrightarrow\{0,1,2,\cdots,25\}$ by
$$f(P)=\left\{\begin{array}{ccc}
P+3 & \mbox{if} & P<23\\
P-23 & \mbox{if} & P\geq 23
\end{array}\right.$$
Simply, $f(P)\equiv P+3\mod 26$. Let us encipher YES. Each letter corresponds to plaintext units 24, 4, 18, respectively. The enciphering (add 3 mod 26) of each plaintext unit is 1, 7, 21, respectively and their corresponding alphabet letters are BHV. Let us now decipher ZKB. Each letter corresponds to ciphertext units 25, 10, 1, respectively. By subtracting 3 mod 26, each unit is deciphered to 22, 7, 24, respectively. The corresponding letters are WHY.

The cryptosystem shown in the above example is one of the oldest cryptosystems. It was invented and used by Julius Caesar. The cryptosystem can be written, in general, as
\begin{equation}
\label{eq:shiftransf}
C=f(P)\equiv P+b\mod N
\end{equation}
\eqref{eq:shiftransf} is called the shift transformation.

Breaking the Code

We need to know two types of information to break a code:

  1. The first type of information we need to know is the nature (structure) of the cryptosystem. For example, we know the cryptosystem uses a shift transformation on single letters of the 26-letter alphabet A-Z with numerical equivalents 0-25.
  2. The second type of information we need to know is a specific choice of parameters connected with the cryptosystem. In the shit transformation, it is $b$. The parameter $b$ is called a key, or more specifically the enciphering key.

Example. The intercepted message is FQOCUDEM and we would like to decipher this. Suppose we know that it was enciphered using a shift transformation on single letters of the 26-letter alphabet A-Z with numerical equivalents 0-25. So we need to figure out the parameter $b$. Suppose that we have already intercepted a long string of ciphertext. The most frequently occurring letter in English text is E and the second most frequently occurring letter is T according to the finding by Samuel Morse (1791-1872), the inventor of Morse code. He obtained the result by counting the number of letters in sets of printers’ type. E is also most frequently occurring letter in the words listed in the main entries of the Concise Oxford English Dictionary (9th Edition, 1995) with the percentage of words the letter E appears in 11.16% but the second most frequently occurring letter in English vocabulary is A (8.5%) and T (7%) is 5th most frequently occurring letter. See here for more information. It is reasonable to assume that the most frequently occurring letter in the ciphertext is the encryption of E. Suppose that the letter U appears the most frequently in the ciphertext. This indicates the shift $b$ take E=4 to U=20, i.e. $20\equiv 4+b\mod 26$, so $b=16$. To decipher the message we just need to subtract 16 mod 26 from the numerical equivalents of FQOCUDEM.
\begin{align*} \mbox{FQOCUDEM}&= 5\ 16\ 14\ 2\ 20\ 3\ 4\ 12\\ &\mapsto 15\ 0\ 24\ 12\ 4\ 13\ 14\ 22\\ &=\mbox{PAYMENOW} \end{align*}
The type of analysis we have done in this example by considering the most frequently occurring letter is called the frequency analysis.

The cryptosystem by a shift transformation is so simple that it can easily be broken. We can make an improvement by using a more general type of transformation on $\mathbb{Z}/N\mathbb{Z}$, called an affine map:
\begin{equation}
\label{eq:affine}
C\equiv aP+b\mod N
\end{equation}
where $a$ and $b$ are fixed integers which form the enciphering key.

Example. Let us encipher PAYMENOW using the affine transformation \eqref{eq:affine} with $a=7$, $b=12$.
\begin{align*} 15\ 0\ 24\ 12\ 4\ 13\ 14\ 22&\mapsto 13\ 12\ 24\ 18\ 14\ 25\ 6\ 10\\ &=\mbox{NMYSOZGK} \end{align*}

Deciphering a message that was enciphered by means of the affine map \eqref{eq:affine} can be achieved by
\begin{equation}
\label{eq:affine2}
\begin{aligned}
P&\equiv a^{-1}C-a^{-1}b\mod N\\
P&\equiv a’C+b’\mod N
\end{aligned}
\end{equation}
where $a^{-1}$ is the multiplicative inverse of $a$. This works only if $(a,N)=1$, otherwise we cannot solve \eqref{eq:affine} for $P$ in terms of $C$. Thus, $a$ is required to be in
$$(\mathbb{Z}/N\mathbb{Z})^*=\{[a]\in\mathbb{Z}/N\mathbb{Z}: (a,N)=1\}$$ so that the map $C$ can be a one-to-one correspondence. $((\mathbb{Z}/N\mathbb{Z})^*,\cdot)$ is a multiplicative abelian group.

Example. Suppose that we know the most frequently occurring letter of ciphertext is K and the second most frequently occurring one is D. It is reasonable to assume that these are E and T, the two most frequently occurring letters in the English language.
\begin{align*} 10a’+b’&\equiv 4\mod 26\\ 3a’+b’&\equiv 19\mod 26 \end{align*}
Subtracting the second equation from the first, we obtain $7a’\equiv 11\mod 26$ and so $a’\equiv 7^{-1}\cdot 11\mod 26\equiv 15\cdot 11\mod 26\equiv 9\mod 26$. $b’$ is obtained from the first equation by $b’\equiv 4-10a’\mod 26\equiv 18\mod 26$. Hence, messages can be deciphered by means of the formula $P\equiv 9C+18\mod 26$.
$$\varphi(26)=\varphi(2\cdot 13)=\left(1-\frac{1}{2}\right)\left(1-\frac{1}{13}\right)=12$$
so we know $(\mathbb{Z}/26\mathbb{Z})^*$ has 12 elements. $(\mathbb{Z}/26\mathbb{Z})^*$ is given by
$$(\mathbb{Z}/26\mathbb{Z})^*={1,3,5,7,9,11,15,17,19,21,23,25}$$

Digraph Transformations

Suppose that our plaintext and ciphertext message units are two-letter blocks (digraphs). If the entire plaintext has an odd number of letters, then in order to obtain a whole number of digraphs, we add on an extra letter at the end. For instance, we can add on the blank if our alphabet contains it. If we are using the 26-letter alphabet, we can add on another letter that may not cause a trouble. Each digraph is assigned to a numerical equivalent as a 2-digit base-$N$ integer $xN+y$, where $x$ is the numerical equivalent of the first letter in the digraph and $y$ is the numerical equivalent of the second letter in the digraph. This gives a one-to-one correspondence between the set of all digraphs in the $N$-letter alphabet and $\mathbb{Z}/N^2\mathbb{Z}=\{0,1,2,\cdots,N^2-1\}$. Define the encryption of $P$ to be $C\equiv a P+b\mod N^2$, where $(a,N^2)=1$ i.e. $a\in(\mathbb{Z}/N^2\mathbb{Z})^*$.

Example. Suppose that we are using 26-letter alphabet and the digraph enciphering transformation $C\equiv 159P+580\mod 676$. The digraph NO has numerical equivalent $13*26+14=352$. The ciphertext is $C\equiv 159\cdot 352+580\mod 676\equiv 440\mod 676$. $440=16\cdot 26+24$, so its equivalent digraph is QY. The digraph ON has numerical equivalent $14\cdot 26+13=377$ and its ciphertext is $C\equiv 159\cdot 377+580\mod 676\equiv 359\mod 676$. Since $359=13\cdot 26+21$, its digraph equivalent is NV.

To break a digraph encryption system $C\equiv aP+b\mod N^2$ we need to know the ciphertext corresponding to two different plaintext message units. The message units are digraphs, so for frequency analysis count which two-letter blocks occur the most often in a long string of ciphertext. If we use the 26-letter alphabet, TH and HE are known to be the first and the second most frequently occurring digraphs.

Example. You know that your adversary is using a cryptosystem with 27-letter alphabet A-Z, the blank. Each diagraph corresponds to an integer in $\mathbb{Z}/729\mathbb{Z}=\{0,1,2,\cdots, 728=27^2-1\}$. As previously seen, if two letters in the digraph have numerical equivalent of $x$ and $y$, then the digraph has the numerical equivalent $27x+y$. Suppose that a study of a large sample of ciphertext shows that the most frequently occurring digraphs are ZA, IA and IW in that order. Suppose that the most frequently occurring digraphs in the English language (for text written in 27-letter alphabet) are Eblank, Sblank, blankT in that order. We also know that the cryptosystem uses an affine transformation $\mod 729$. find the deciphering key and read the message NDXBHO. Also find the enciphering key.

Solution.
\begin{align*} C&\equiv aP+b\mod 729\\ P&\equiv a’C+b’\mod 729 \end{align*}
where $a’=a^{-1}\in\mathbb{Z}/27\mathbb{Z}$ and $b’=-a^{-1}b\in\mathbb{Z}/27\mathbb{Z}$.

The numerical equivalents of ZA, IA and IW, respectively, are
\begin{align*} 25\cdot 27+0&=675\\ 8\cdot 27+0&=216\\ 8\cdot 27+22&=238 \end{align*}
The numerical equivalents of Eblank, Sblank, blankT, respectively, are
\begin{align*} 4\cdot 27+26&=134\\ 18\cdot 27+26&=512\\ 26\cdot 27+19&=721 \end{align*}
Now, we have the equations
\begin{align*} 675a’+b’&\equiv 134\mod 729\\ 216a’+b’&\equiv 512\mod 729\\ 238a’+b’&\equiv 721\mod 729 \end{align*}
One may think only two of theses equations would be needed to determine $a’$ and $b’$ but that is not necessarily the case. Subtracting the second equation from the first, we obtain $459a’\equiv 351\mod 729$. This equation however does not have a unique solution because $(459,729)=27$. (There are 27 solutions modulo 729, $a’=104+27t$, $-3\leq t\leq 23$.) If we subtract the third equation from the first, we obtain $437a’\equiv 142\mod 729$. $(437,729)=1$, i.e. there exists $437^{-1}\in\mathbb{Z}/729\mathbb{Z}$. Hence, the equation has a unique solution $a’\equiv 437^{-1}\cdot 142\mod 729$.

Finding $437^{-1}\in\mathbb{Z}/729\mathbb{Z}$:
\begin{align*} 729&=437+292\\ 437&=292+145\\ 292&=2\cdot 145+2\\ 145&=72\cdot 2+1 \end{align*}
and
\begin{align*} 1&=145-72\cdot 2\\ &=145-72(292-2\cdot 145)\\ &=145\cdot 145-97\cdot 292\\ &=145(437-292)-97\cdot 292\\ &=145\cdot 437-217\cdot 292\\ &=145\cdot 437-217(729-437)\\ &\equiv 362\cdot 437\mod 729 \end{align*}
Therefore, $362\equiv 437^{-1}\mod 27$. $a’$ and $b’$ are then given by
\begin{align*} a’&\equiv 362\cdot 142\mod 729\equiv 374\mod 729\\ b’&\equiv 134-675\cdot 374\mod 729\equiv 647\mod 729 \end{align*}
The numerical equivalents of ND, XB, and HO are 354, 622, 203, respectively. The deciphering of these digraphs is given by
\begin{align*} a’\cdot 354+b’&=374\cdot 354+647\equiv 365\mod 729\\ a’\cdot 622+b’&=374\cdot 622+647\equiv 724\mod 729\\ a’\cdot 203+b’&=374\cdot 203+647\equiv 24\mod 729 \end{align*}
\begin{align*} 365&=27\cdot 13+14\mapsto\mbox{NO}\\ 724&=27\cdot 26+22\mapsto\mbox{blankW}\\ 24&=27\cdot 0+24\mapsto\mbox{AY} \end{align*}
The deciphered message is NO WAY. The enciphering keys $a$ and $b$ are given by
\begin{align*} a&\equiv(a’)^{-1}\mod 729\equiv 374^{-1}\mod 729\equiv 614\mod 729\\ b&\equiv -ab’\mod 729\equiv -614\cdot 647\mod 729\equiv 47\mod 729 \end{align*}

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.