# Primality Tests

We begin by discussing a method of computing $a^d\mod n$, called the repeated squaring method, which is efficient enough to require only a handheld calculator using the following example.

Example. Let us compute the least residue of $848^{187}\mod 1189$ by using only a handheld calculator. First we convert 187 to the base 2:
\begin{align*} 187&=(10111011)_2\\ &=1\cdot 2^7+0\cdot 2^6+1\cdot 2^5+1\cdot 2^4+1\cdot 2^3+0\cdot 2^2+1\cdot 2+1\\ &=128+32+16+8+2+1 \end{align*}
Let $a=848$ and $n=1189$.
$$\begin{array}{|c|c|} \hline k & a^k\mod n\\ \hline 1 & 848\\ \hline 2 & 848^2=719104\equiv 948\mod 1189\\ \hline 4 & 948^2=898704\equiv 1009\mod 1189\\ \hline 8 & 1009^2= 1018081\equiv 297\mod 1189\\ \hline 16 & 297^2=88209\equiv 223\mod 1189\\ \hline 32 & 223^2=49729\equiv 980\mod 1189\\ \hline 64 & 980^2=960400\equiv 877\mod 1189\\ \hline 128 & 877^2=769129\equiv 1035\mod 1189\\ \hline \end{array}$$
Hence,
\begin{align*} 848^{187}&=848^{128+32+16+8+2+1}\\ &=848^{128}\cdot 848^{32}\cdot 848^{16}\cdot 848^8\cdot 848^2\cdot 848\\ &\equiv 1035\cdot 980\cdot 223\cdot 297\cdot 948\cdot 848\mod 1189\mod 1189\\ &\equiv 190\mod 1189 \end{align*}

Here is our first primality test. Let us recall Fermat Little Theorem: If $n$ is a prime and $n\not|a$, then $a^{n-1}\equiv 1\mod n$. The contrapositive of the above statement can serve as a primality test: if $a^{n-1}\not\equiv 1\mod n$, then $n$ is not a prime or $n|a$.

Example. Let us show that $33$ is not a prime using the above primality test. (Of course it is not prime because $33=3\cdot 11$.) $33\not|2$ and
\begin{align*} 2^{33-1}&=2^{32}\\ &=(2^5)^62^2\\ &=(32)^62^2\\ &\equiv(-1)^62^2\mod 33\\ &\equiv 4\mod 33 \end{align*}
Thus, $33$ is not a prime.

Here is another primality test.

Theorem. If the integer $n>1$ has no prime divisor less than or equal to $\sqrt{n}$, then $n$ is prime.

Proof. Suppose that $n$ is a composite number. Then $n=d_1d_2$ for some $d_1>1$ and $d_2>1$. Suppose that all prime divisors are greater than $\sqrt{n}$. Then $d_1>\sqrt{n}$ and $d_2>\sqrt{n}$. But $n=d_1d_2>(\sqrt{n})^2=n$, which is impossible. This proves the theorem. If $d_1\leq\sqrt{n}$, then $d_1$ is either prime or else has a prime divisor less than or equal to $\sqrt{n}$.

Question: Is the statement “If $2^{n-1}\equiv 1\mod n$ then $n$ is a prime.” true? The ancient Chinese believed so, but there is a counterexample. $2^{340}\equiv 1\mod 341$. But, $341=11\cdot 31$ (this is left as an exercise), so it is not a prime.

Definition. We call $n$ a pseudoprime if $2^{n-1}\equiv 1\mod n$ but $n$ is composite. More generally, a composite number $n$ such that $a^{n-1}\equiv 1\mod n$ is called a pseudoprime to base $a$.

The smallest pseudoprime is $341$, and it was not discovered until 1819. Bases other than $2$ can be used to identify composite numbers. For example,
$$3^{340}\equiv 56\mod 341$$
Thus, $341$ is not a prime number. These pseudoprimes are rarer then primes. Ever rarer are pseudoprimes to multiples bases. It is known, for example, that there are only 1770 integers below $25\cdot 10^9$ that are simultaneously pseudoprimes to the bases $2$, $3$, $5$ and $7$. So, the primality of numbers less than $25\cdot 10^9$ can be determined by testing Fermat’s congruence $a^{n-1}\equiv 1\mod n$ with these four bases, then comparing any number passing all 4 tests with a list of the 1770 exceptions. If the number is not any of those 1770 exceptions, it must be a prime.

Next we discuss Mersenne numbers and Fermat numbers, and primality tests those numbers.

Definition. If $k$ is a positive integer, we call $M_k=2^k-1$ a Mersenne number.

$$\begin{array}{|c|c|c|} \hline k & M_k=2^k-1 & \mbox{prime?}\\ \hline 1 & 1 & \mbox{N}\\ \hline 2 & 3 & \mbox{Y}\\ \hline 3 & 7 & \mbox{Y}\\ \hline 4 & 15=3\cdot 5 & \mbox{N}\\ \hline 5 & 31 & \mbox{Y}\\ \hline 6 & 63=9\cdot 7 & \mbox{N}\\ \hline 7 & 127 & \mbox{Y}\\ \hline 8 & 255=3\cdot 5\cdot 7 & \mbox{N}\\ \hline 9 & 511=7\cdot 73 & \mbox{N}\\ \hline 10 & 1023=3\cdot 11\cdot 31 & \mbox{N}\\ \hline \end{array}$$
From this table, one may expect that $M_k$ is prime when $k$ is prime. However, $M_{11}=2047=23\cdot 89$ is not a prime.

Theorem.
If $d|k$, then $M_d|M_k$, so if $M_k$ is prime, then $k$ is prime.

Proof. Since $d|k$, $k=dd_1$ for some $d_1\in\mathbb{Z}$.
$$M_k=2^k-1=2^{dd_1}-1=(2^d-1)(2^{(d(d_1-1)}+2^{(d(d_1-2)}+\cdots+2^d+1)$$

$$\begin{array}{|c|c|c|} \hline k & 2^k+1 & \mbox{prime?}\\ \hline 1 & 3 & \mbox{Y}\\ \hline 2 & 5 & \mbox{Y}\\ \hline 3 & 9=3\cdot 3 & \mbox{N}\\ \hline 4 & 17 & \mbox{Y}\\ \hline 5 & 33=3\cdot 11 & \mbox{N}\\ \hline 6 & 65=5\cdot 13 & \mbox{N}\\ \hline 7 & 129=3\cdot 43 & \mbox{N}\\ \hline 8 & 257 & \mbox{Y}\\ \hline 9 & 513=3\cdot 3\cdot 3\cdot 19 & \mbox{N}\\ \hline 10 & 1025=5\cdot 5\cdot 41 & \mbox{N}\\ \hline \end{array}$$

Theorem. If $k$, $a$, and $b$ are positive integers such that $k=ab$, where $a$ is odd, then
$$2^b+1|2^k+1$$
In particular, if $2^k+1$ is prime, then $k$ is $0$ or a power of $2$.

Proof. Under the assumption, we want to show that
$$2^k+1\equiv 0\mod 2^b+1$$
or
$$2^k\equiv -1\mod 2^b+1$$
Since, $2^b\equiv -1\mod 2^b+1$,
$$2^k=2^{ab}=(2^b)^a\equiv (-1)^a\mod 2^b+1\equiv -1\mod 2^b+1$$
If $k>0$ is not a power of $2$, then we can take $a>1$ so that
$$1<2^b+1<2^k+1$$
This means that $2^k+1$ has a positive divisor other than 1 and itself.

Definition. $F_r=2^{2^r}+1$ is called a Fermat number.

Example. $F_0=3$, $F_1=5$, $F_2=17$, $F_3=257$, $F_4=65537$ are primes, so Fermat conjectured that Fermat numbers are prime. But $F_5=2^{32}+1$ is not a prime. It is divisible by $641$. $641$ can be written
\begin{align*} 641&=640+1=2^7\cdot 5+1\\ 641&=625+16=5^4+2^4 \end{align*}
Thus, we have $2^7\cdot 5\equiv -1\mod 641$ and $2^4\equiv -5^4\mod 641$.
Now,
\begin{align*} F_5&=2^{32}+1\\ &=(2^7)^4\cdot 2^4+1\\ &\equiv(2^7)^4(-5^4)+1\mod 641\\ &\equiv -(2^7\cdot 5)^4+1\mod 641\\ &\equiv 0\mod 641 \end{align*}
No other Fermat numbers that are prime have been found yet.

One may expect that for any composite number $n$, there exists a base $a$ for which Fermat’s theorem can be used to show that $n$ is composite. However, there are composite numbers called Carmichael numbers, which are pseudo primes to every base. That is, $n$ is composite, but $a^{n-1}\equiv 1\mod n$, whenever $(a,n)=1$. The smallest Carmichael number is $561=3\cdot 11\cdot 17$. It was proved in 1994 that there are infinitely many Carmichael numbers.

There is a primality test just for Mersenne numbers. It is called the Lucas-Lehmer test. Define a sequence $S_1,S_2,\cdots$ by
\begin{align*} S_1&=4,\\ S_n&=S_{n-1}-2\ \mbox{for}\ n>1. \end{align*}
For example, $S_2=4^2-2=14$, $S_3=14^2-2=194$. Then the Lucas-Lehmer test is

Theorem. If $p$ is an odd prime then $M_p=2^p-1$ is prime if and only if $S_{p-1}\equiv 0\mod M_p$.

For example, take $p=7$ and show that $M_p=2^7-1=127$ is a prime.
\begin{align*} S_3&=194\equiv 67\mod 127\\ S_4&\equiv 67^2-2\mod 127\equiv 42\mod 127\\ S_5&\equiv 42^2-2\mod 127\equiv 111\mod 127\\ S_6&\equiv 111^2-2\mod 127\equiv 0\mod 127. \end{align*}

There is also a primality test just for Fermat numbers. It is called Péppin’s test.

Theorem. If $n>0$, the Fermat number $F_n=2^{2^n}+1$ is prime if and only if $3^{\frac{F_n-1}{2}}\equiv -1\mod F_n$.

Example. Use Pépin’s test to show that $F_3=257$ is prime.

Solution. $3^{\frac{257-1}{2}}=3^{128}=3^{2^7}$.
\begin{align*} 3^2&=9\\ 3^4&=9^2=81\\ 3^8&=81^2\equiv 136\mod 257\\ 3^{16}&\equiv 136^2\mod 257\equiv 249\mod 257\\ 3^{32}&\equiv 249^2\mod 257\equiv 64\mod 257\\ 3^{64}&\equiv 64^2\mod 257\equiv 241\mod 257\\ 3^{128}&\equiv 241^2\mod 257\equiv 256\mod 257\equiv -1\mod 257 \end{align*}

# RSA Protocol, A Public Key Cryptosystem

As we discussed here, the enciphering and deciphering transformations involve secret keys called encryption and decryption keys. These keys are shared only by the transmitter and the receiver, so they are called private keys. An Achilles heel of cryptographic communication systems that use private keys is that secret communications can take place only after a key is transmitted in secret over a totally secure communication channel. This is referred to as the CATCH 22 of cryptography. First there are two most famous people when it comes to cryptography and communications, way even more famous than the great mathematician Claude E. Shannon formerly at Bell Lab, who is dubbed the father of modern communication theory. They are Alice and Bob. Literally any books and papers on cryptography, communications, or even quantum computing would mention their names.

CATCH 22: Before the transmitter and the receiver Alice and Bob can communicate in secret, they must first communicate in secret.

There is more to this CATCH 22.

CATCH 22a: Even if Alice and Bob succeed in tansmitting their key over a secure communication channel, there is no mechanism that guarantees with full certainty that no one is able to eavesdrop.

To remedy this issue with private key sharing, public key cryptosystems were invented. In a public key cryptosystem, Alice makes the encryption key available to the public, so anyone can encrypt messages using the key but only Alice can decrypt the messages, and Bob can do the same. So, there is no need to secretly communicate to share keys prior to communicating in secret. Using such trapdoor function (also called one-way function ) is crucial for public key cryptosystems. The most famous public key cryptosytem is RSA (named after its inventors Ronald Rivest, Adi Shamir and Leonard Adleman) which was (officially) introduced in 1978 (unofficially, it was already invented years before they did by researchers secretly working in the Communications-Electronics Security Group at GCHQ, the British counterpart of NSA). RSA is based on the difficulty of factoring. Here is a basic idea of the textbook RSA cryptosystem.

Suppose that Alice wants to receive secret messages. She selects two large primes $p$ and $q$ and then forms the product $n=pq$. Alice also chooses an integer $E<n$ coprime to $\phi(n)=(p-1)(q-1)$. The integers $n$ and $E$ are made public and constitute the encryption key, so everybody can encrypt messages. We assume that our message is a sequence of positive integers $T<n$. Bob encypts each integer $T$ as $C\equiv T^E\mod n$, and send the ciphertext to Alice. Alice can decrypt the ciphertext as follows: Let $m=\phi(n)=(p-1)(q-1)$. Since $(E,m)=1$, there exists $D\in\mathbb{Z}/m\mathbb{Z}$ such that $DE\equiv 1\mod m$ or equivalently $DE=1$ in $\mathbb{Z}/m\mathbb{Z}$. Thus, $DE=\phi(n)k+1$ for some $k\in\mathbb{Z}$. The prime numbers $p$ and $q$ are supposedly huge, so $T$ being one of them is improbable and we can safely assume that $(T,n)=1$. Then by the Euler-Fermat theorem, we have $T^{\phi(n)}\equiv 1\mod n$. Finally, we see that the paintext $T$ is recovered by computing $C^D$ modulo $n$. \begin{align*} C^D&\equiv (T^E)^D\mod n\\ &\equiv T^{ED}\mod n\\ &\equiv T^{\phi(n)k+1}\mod n\\ &\equiv T\mod n \end{align*}
Now, assume that Celia is is eavesdropping. She knows the public key $(n,E)$. She also knows the ciphertext $C$. However, in order to decrypt $C$ she needs the decryption key $D$, the inverse of $E$ in $\mathbb{Z}/m\mathbb{Z}$ where $m=\phi(n)=(p-1)(q-1)$, and she needs to know the prime factors $p$ and $q$ of $n$ in order to compute $D$.

Example. Let $n=1073$, $p=29$, and $q=37$. The public key is $(n,E)=(1073,25)$. The plaintext $T$ is “MISS PIGGY” and the numerical equivalents are
$$13\ 9\ 19\ 19\ 27\ 16\ 9\ 7\ 7\ 25$$
Enciphering $T$: $C\equiv T^{25}\mod n=1073$
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T & 13 & 9 & 19 & 19 & 27 & 16 & 9 & 7 & 7 & 25\\ \hline C & 671 & 312 & 901 & 901 & 656 & 1011 & 312 & 922 & 922 & 546\\ \hline \end{array}$$
Deciphering: Compute $D$, the inverse of 25 modulo $\phi(n)=(p-1)(q-1)=1008$. Since $1=25\cdot 121+1008(-3)$, $D=121$ is the decipering key and the paintext $T$ is retrieved by
$$C^{121}\equiv T\mod n=1073$$
For example, $671^{121}\equiv 13\mod 1073$.

Remark. In practical sense, there is a problem with the above example. If we encrypt the message letter for letter, the cryptosystem can be easily broken by frequency analysis. This problem can be remedied if we encrypt the message in blocks of about 100 letters. The chance that any two message blocks of 100 letters coincide is practically none.

Remark. Of course in practice we wouldn’t be using such small key sizes shown in the above example. Here is an example of practically usable keys: \begin{align*}E&=198778434778923476493186960677288219412181391439289859633481192496758260063\\n&=2555942223974189195272679217974555794863882765417656848825203904501780583533\\D&=1774134686349434385697798709945131299127046225553502224286279549365461014283\end{align*} Messages can be encypted more securely if one uses key sizes of about 200 digits in addition to using many-letter message blocks suggested in the above remark.

Remark. As mentioned earlier, the presumed security of RSA is based on the belief that factoring is a difficult problem to crack on a computer. So, how difficulty can it be? Umesh Vazirani, a computer scientist at UC Berkely, summed it up using the example of factoring a 2,000-digit number back in 1994: “It’s not just a case that all the computers in the world today would be unable to factor that number. Even if you imagine that every particle in the universe was a computer and was computing at full speed for the entire life of the universe, that would be insufficient to factor that number.”

Remark. RSA protocol begins with picking prime numbers to make the key. We know there are infinitely many prime numbers although we don’t know if that is still the case for a particular type of prime numbers. For example, it is an open problem in number theory if there are infinitely many Mersenne prime numbers, i.e. primes numbers of the form $2^n-1$. (The conjecture is there are infinitely many Mersenne prime numbers.) The largest prime number known to date is a Mersenne prime $2^{82589933}-1$. Especially from computational perspective, it would be interesting to see how prime numbers are distributed, and prime number theorem gives us a pretty good picture about how many prime numbers are there within a certain bound. Let $\pi(x)$ denotes the number of prime numbers less than or equal to $x$. $\pi(x)$ is called prime-counting function. Then Prime Number Theorem sates that $$\lim_{x\to\infty}\frac{\pi(x)}{\left[\frac{x}{\log(x)}\right]}=1$$ which can be restated as $$\pi(x)\sim\frac{x}{\log(x)}$$ for large $x$. This can be interpreted that for large $x$, the probability that a random integer not greater than $x$ is prime is very closed to $\frac{1}{\log(x)}$. This theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Pousin in 1896. For example, if one wants to know how many prime numbers there are between $\frac{x}{2}$ and $x$ for a given lager number $x$, we can get an estimate from prime number theorem: \begin{align*}\pi(x)-\pi\left(\frac{x}{2}\right)&\sim\frac{x}{\log(x)}-\frac{x}{2\log\left(\frac{x}{2}\right)}\\&\sim\frac{x}{\log(x)}-\frac{x}{2\log(x)}\ (\mbox{because $x$ is large})\\&=\frac{x}{2\log(x)}\end{align*} Figure 1 shows the comparison between the asymptotic distribution of prime number between $\frac{x}{2}$ and $x$ (in blue), and its approximation (in red).

For $x=100000$, using the approximation $\frac{x}{2\log(x)}$ there are 4343 estimated prime numbers between 50000 and 100000, so there are plentiful of them to choose from.

# Enciphering Matrices

Suppose we have an $N$-letter alphabet and want to send digraphs as our message units. As we have seen here, we can let each digraph correspond to an integer considered modulo $N^2$, i.e. to an element of $\mathbb{Z}/N^2\mathbb{Z}$. An alternate possibility is to let each digraph correspond to a vector $\begin{pmatrix} x\\ y \end{pmatrix}$ with $x,y\in\mathbb{Z}/N\mathbb{Z}$. For example, if we are using the 26-letter alphabet A- Z with numerical equivalents 0-25, respectively, then the digraph NO corresponds to the vector $\begin{pmatrix} 13\\ 14 \end{pmatrix}$. We consider the $xy$-plane as the finite lattice $\mathbb{Z}/N\mathbb{Z}\times\mathbb{Z}/N\mathbb{Z}=(\mathbb{Z}/N\mathbb{Z})^2$.

Let $M_2(\mathbb{Z}/N\mathbb{Z})$ denote the set of all $2\times 2$ matrices with entries in $\mathbb{Z}/N\mathbb{Z}$. Let $A=\begin{pmatrix} a & b\\ c & d \end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and suppose that $D=\det(A)=ad-bc\in(\mathbb{Z}/N\mathbb{Z})^*$. Let $D^{-1}$ denote the multiplicative inverse of $D$ in $\mathbb{Z}/N\mathbb{Z}$. Then \begin{align*}
\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}&=\begin{pmatrix}
D^{-1}(da-bc) & 0\\
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}
\end{align*}
Similarly,
$$\begin{pmatrix} a & b\\ c & d \end{pmatrix}\begin{pmatrix} D^{-1}d & -D^{-1}b\\ -D^{-1}c & D^{-1}a \end{pmatrix}=\begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}$$
Thus, we see that

\label{eq:invmat}
A^{-1}=\begin{pmatrix}
D^{-1}d & -D^{-1}b\\
-D^{-1}c & D^{-1}a
\end{pmatrix}

Example. Find the inverse of $A=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$.

Solution. $D=16-21=-5\equiv 21\mod 26$. Since $(21,26)=1$, there exists $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$. Remember that finding $21^{-1}\in\mathbb{Z}/26\mathbb{Z}$ is equivalent to solving the diophantine equation $21x+26y=1$.
\begin{align*} 26&=21\cdot 1+5\\ 21&=5\cdot 4+1 \end{align*}
and
\begin{align*} 1&=21-5\cdot 4\\ &=21-(26-21)4\\ &=5\cdot 21+26(-4) \end{align*}
Thus, we find $21^{-1}\equiv 5\mod 26$.
\begin{align*} A^{-1}&=\begin{pmatrix} 5\cdot 8 & -5\cdot 3\\ -5\cdot 7 & 5\cdot 2 \end{pmatrix}\\ &=\begin{pmatrix} 40 & -15\\ -35 & 10 \end{pmatrix}\\ &\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix} a & b\\ c & d \end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$. Then
$$\begin{pmatrix} x’\\ y’ \end{pmatrix}=A\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} a & b\\ c & d \end{pmatrix}\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} ax+by\\ cx+dy \end{pmatrix}$$
This gives a linear map or a linear transformation from vectors to vectors.

We introduce the following theorem without proof.

Theorem. Let $A=\begin{pmatrix} a & b\\ c & d \end{pmatrix}\in M_2(\mathbb{Z}/N\mathbb{Z})$ and set $D=ad-bc$ as before. Then the following are equivalent:

1. $(D,N)=1$.
2. $A$ has an inverse matrix.
3. if $x$ and $y$ are not both $0$ in $\mathbb{Z}/N\mathbb{Z}$, then $A\begin{pmatrix}x\\y \end{pmatrix}\ne\begin{pmatrix}0\\0\end{pmatrix}$.
4. $A$ gives a one-to-one correspondence of $(\mathbb{Z}/N\mathbb{Z})^2$ with itself.

Example. Solve the following systems of simultaneous congruences.

1. \begin{align*}2x+3y&\equiv 1\mod 26\\ 7x+8y&\equiv 2\mod 26 \end{align*}
2. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 2\mod 26 \end{align*}
3. \begin{align*} x+3y&\equiv 1\mod 26\\ 7x+9y&\equiv 1\mod 26 \end{align*}

Solution.

1. The system of simultaneous congruences can be written as the matrix congruence $AX\equiv B\mod 26$ or as the matrix equation $AX=B$ in $\mathbb{Z}/26\mathbb{Z}$, where $$A=\begin{pmatrix}2 & 3\\7 & 8\end{pmatrix},\ X=\begin{pmatrix}x\\y\end{pmatrix},\ B=\begin{pmatrix}1\\2\end{pmatrix}$$ $D=16-21=-5$ and $(-5,26)=1$, so by above Theorem, we see that $A^{-1}$ exists. In fact, we have already found $A^{-1}$ in the previous example. The solution $X$ is given by \begin{align*} X&\equiv A^{-1}B\mod 26\\&\equiv\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 26\\ &\equiv\begin{pmatrix} 10\\ 11 \end{pmatrix}\mod 26 \end{align*}
2. The matrix in parts 2 and 3 does not have an inverse matrix in $\mathbb{Z}/26\mathbb{Z}$ because $D=9-21=-12$ and $(-12,26)=2\ne 1$. However, it does have an inverse matrix in $\mathbb{Z}/13\mathbb{Z}$ and the solution is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 2 \end{pmatrix}\mod 13\\ &\equiv\begin{pmatrix} 3\\ 8 \end{pmatrix}\mod 13 \end{align*} We now examine the possibilities of having solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 3\mod 13$ and $y\equiv 8\mod 13$, $x$ and $y$ can be written as $x=3+13k_1$ and $y=8+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Suppose that $k_1+k_2$ is even, so that $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 15+13(k_1+k_2)\mod 26\\ &\equiv 15\mod 26\\ &\not\equiv 2\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are no solutions for part 2.
3. Similarly to part 2, the solution in $\mathbb{Z}/13\mathbb{Z}$ is given by \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 9 & 10\\ 6 & 1 \end{pmatrix}\begin{pmatrix} 1\\ 1 \end{pmatrix}\mod 13\ &\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 13 \end{align*} We test the possibilities of solutions in $\mathbb{Z}/26\mathbb{Z}$. Since $x\equiv 6\mod 13$ and $y\equiv 7\mod 13$, $x$ and $y$ can be written as $x=6+13k_1$ and $y=7+13k_2$ for some $k_1,k_2\in\mathbb{Z}$. \begin{align*} x+3y&\equiv 1+13(k_1+k_2)\mod 26\ &\equiv 1\mod 26 \end{align*} if and only if $k_1+k_2$ is even. Now we assume that $k_1+k_2$ is even, so that we have $x+3y\equiv 1\mod 26$. \begin{align*} 7x+9y&\equiv 1+13(k_1+k_2)\mod 26\\ &\equiv 1\mod 26 \end{align*} since $k_1+k_2$ is even. Hence, there are solutions for part 3. Let $0\leq x,y\leq 25$. Then $k_1, k_2=0,1$. Since $k_1+k_2$ is even, we have either $k_1=k_2=0$ or $k_1=k_2=1$. Therefore, the solutions are \begin{align*} \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 6\\ 7 \end{pmatrix}\mod 26\ \mbox{or}\ \begin{pmatrix} x\\ y \end{pmatrix}&\equiv\begin{pmatrix} 19\\ 20 \end{pmatrix}\mod 26 \end{align*}

Let $A=\begin{pmatrix} a & b\\ c & d \end{pmatrix} \in M_2(\mathbb{Z}/N\mathbb{Z})$ with $(D,N)=1$ where $D=ad-bc$ be an enciphering matrix. Then it defines the enciphering transformation $C=AP$ where $P=\begin{pmatrix} x\\ y \end{pmatrix}$ and $C=\begin{pmatrix} x’\\ y’ \end{pmatrix}$ are plaintext message unit and ciphertext, respectively. That is,
$$\begin{pmatrix} x’\\ y’ \end{pmatrix}=\begin{pmatrix} a & b\\ c & d \end{pmatrix}\begin{pmatrix} x\\ y \end{pmatrix}$$
The deciphering transformation is then given by $P=A^{-1}C$, i.e.
$$\begin{pmatrix} x\\ y \end{pmatrix}=\begin{pmatrix} D^{-1}d & -D^{-1}b\\ -D^{-1}c & D^{-1}a \end{pmatrix}\begin{pmatrix} x’\\ y’ \end{pmatrix}$$

Example. Wokring in the 26-letter alphabet, use the matrix $A=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\in M_2(\mathbb{Z}/26\mathbb{Z})$ to encipher the message unit “NO”. $$AP=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13\\ 14 \end{pmatrix}=\begin{pmatrix} 68\\ 103 \end{pmatrix}\equiv\begin{pmatrix} 16\\ 21 \end{pmatrix}\mod 26$$ Thus the ciphertext $C=AP$ is “QV”.

Remark. To encipher a plaintext sequence of $k$ digraphs $P=P_1P_1P_3\cdots P_k$, we can write the $k$ vectors as columns of a $2\times k$ matrix and then multiply $A$ by the $2\times k$ matrix $P$ to get a $2\times k$ matrix $C=AP$ of coded digraph vectors.

Solution. The numerical equivalence of “NOANSWER” is $$\begin{pmatrix} 13\\ 14 \end{pmatrix}\begin{pmatrix} 0\\ 13 \end{pmatrix}\begin{pmatrix} 18\\ 22 \end{pmatrix}\begin{pmatrix} 4\\ 17 \end{pmatrix}$$ \begin{align*} C&=AP\\ &=\begin{pmatrix} 2 & 3\\ 7 & 8 \end{pmatrix}\begin{pmatrix} 13 & 0 & 18 & 4\\ 14 & 13 & 22 & 17 \end{pmatrix}\\ &=\begin{pmatrix} 68 & 39 & 102 & 59\\ 203 & 104 & 302 & 164 \end{pmatrix}\\ &\equiv\begin{pmatrix} 16 & 13 & 24 & 7\\ 21 & 0 & 16 & 8 \end{pmatrix}\mod 26 \end{align*} i.e. the coded message is “QVNAYQHI”.

Example. In the situation of previous example, decipher the ciphertext “FWMDIQ”.

Solution.
\begin{align*} P&=A^{-1}C\\ &=\begin{pmatrix} 14 & 11\\ 17 & 10 \end{pmatrix}\begin{pmatrix} 5 & 12 & 8\\ 22 & 3 & 16 \end{pmatrix}\\ &=\begin{pmatrix} 312 & 201 & 288\\ 305 & 234 & 296 \end{pmatrix}\\ &\equiv\begin{pmatrix} 0 & 19 & 2\\ 19 & 0 & 10 \end{pmatrix}\mod 26 \end{align*}
Hence, the deciphered plaintext is “ATTACK”.

# 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$.

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

\label{eq:shiftransf}
C=f(P)\equiv P+b\mod N

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

\label{eq:affine}
C\equiv aP+b\mod N

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

\label{eq:affine2}
\begin{aligned}
P&\equiv a^{-1}C-a^{-1}b\mod N\\
P&\equiv a’C+b’\mod N
\end{aligned}

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 $$\label{eq:phiprime} \phi(p)=p-1.$$

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 $$\label{eq:phi}\phi(ka)=k\phi(a).$$

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 $$\label{eq:phi2}\phi(pa)=(p-1)\phi(a).$$

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
$$\label{eq:phiprime2}\phi(p^\alpha)=p^\alpha\left(1-\frac{1}{p}\right).$$

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{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}
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$,$$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right).$$

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 $$\label{eq:euler} a^{\phi(m)}\equiv 1\mod m.$$

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. $$\sum_{d|n}\phi(d)=n.$$

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