## Review Exercises (Set B)

1. Find all solutions to $26x \equiv 14\pmod{82}$

First, we convert the congruence to an equation:

$$14-26x = 82y$$

Dividing both sides by 2, we have

$$7-13x = 41$$

Putting this back in congruence form gives us something familiar:

$$13x \equiv 7\pmod{41}$$

We will need the multiplicative inverse of $13$. To give it a name, suppose $13^{-1} = a$. Then $13a \equiv 1\pmod{7}$.

Translating this back to an equation, we have for some integer $b$:

$$13a + 41b = 1$$

Use the Euclidean Algorithm and "back-solving" to find integers $a$ and $b$ that make the above statement. Here $a=19$, $b=-6$ work. Now we can use $13^{-1} \equiv 19\pmod{41}$ in the earlier congruence to eliminate the $13$:

$$\begin{array}{rcl} 19 \cdot 13x &\equiv& 19 \cdot 7\pmod{41}\\ x &\equiv& 133\pmod{41}\\ x &\equiv& 10\pmod{41} \end{array}$$
2. Consider the set $S$ of numbers of the form $a + b\sqrt{7}$ where $a$ and $b$ are integers. Find a number is this form that serves as a unit for the set $S$.

Several answers are possible. Any number of the form $c+d\sqrt{7}$ where $c^2-7d^2=\pm1$ is a unit. As one (non-trivial) example, consider $8-3\sqrt{7}$.

3. Using the properties of vector addition and scalar multiplication, prove $x \cdot (y+z) = x \cdot y + x \cdot z$, when $x$ and $y$ are the following $n$-dimensional vectors. $$x=\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \vdots \\x_n \end{array} \right) \textrm{ and } y=\left( \begin{array}{c} y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_n \end{array} \right)$$
$$\begin{array}{rcl} x \cdot (y + z) & = & x_1 (y_1 + z_1) + x_2 (y_2 + z_2) + \cdots x_n (y_n + z_n)\\ & = & x_1 y_1 + x_1 z_1 + x_2 y_2 + x_2 z_2 + \cdots + x_n y_n + x_n z_n\\ & = & (x_1 y_1 + x_2 y_2 \cdots + x_n y_n) + (x_1 z_1 + x_2 z_2 \cdots + x_n z_n)\\ & = & x \cdot y + x \cdot z \end{array}$$
4. Prove the sum of two linear transformations on 2 dimensional vectors is itself a linear transformation.

We simply need to show that $(F+G)$ follows the two defining properties of a linear transformation:

$$\begin{array}{rcl} (F+G)(\bar{x}+\bar{y}) &=& F(\bar{x}+\bar{y})+G(\bar{x}+\bar{y})\\ &=& F(\bar{x}) + F(\bar{y}) + (G(\bar{x}) + G(\bar{y}))\\ &=& F(\bar{x}) + G(\bar{x}) + F(\bar{y}) + G(\bar{y})\\ &=& (F+G)(\bar{x}) + (F+G)(\bar{y})\\\\ (F-G)(c \bar{x}) &=& F(c \bar{x}) - G(c \bar{x})\\ &=& cF(\bar{x}) - cG(\bar{x})\\ &=& c(F(\bar{x}) - G(\bar{x}))\\ &=& c(F-G)(\bar{x}) \end{array}$$
5. Prove the converse of Wilson's theorem is true.

We argue indirectly...

Suppose $n$ is not prime. Then $n$ is composite and has some positive divisor $a$ with $1 \lt a \lt n$.

As $(n-1)!$ is the product of all integers between $1$ and $n$, exclusive -- it must be the case that $a$ is one of these factors, which tells us that $$a \mid (n-1)!$$

Turning our attention to the given hypothesis that $(n-1)! \equiv -1 \pmod{n}$, we see this implies $n \mid (n-1)! + 1$.

Recalling that $a$ is a presumed divisor of $n$, we must then also have $$a \mid (n-1)! + 1$$

Knowing that $a \mid (n-1)!$ and $a \mid (n-1)! + 1$ forces us to conclude that $a \mid 1$, and the only positive divisor of $n$ that satisfies this would be $a=1$. This contradicts the statement that $1 \lt a \lt n$, however.

As such, our assumption must be incorrect and its opposite must be true.

$n$ is indeed prime.

6. Encode the message "HILLCODE" with a Hill Cipher and encoding matrix given by

$$E=\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right]$$

First, we translate "HILLCODE" into appropriate numbers $\pmod{26}$: $$\textrm{HILLCODE } \rightarrow 7,8,11,11,2,14,3,4$$

Then, treating each successive pair as a vector, we apply the given encoding matrix $\pmod{26}$:

$$\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right] \left( \begin{array}{c} 7 \\ 8 \end{array} \right) = \left( \begin{array}{c} 111 \\ 70 \end{array} \right) \equiv \left( \begin{array}{c} 7 \\ 18 \end{array} \right)$$ $$\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right] \left( \begin{array}{c} 11 \\ 11 \end{array} \right) = \left( \begin{array}{c} 154 \\ 99 \end{array} \right) \equiv \left( \begin{array}{c} 24 \\ 21 \end{array} \right)$$ $$\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right] \left( \begin{array}{c} 2 \\ 14 \end{array} \right) = \left( \begin{array}{c} 184 \\ 102 \end{array} \right) \equiv \left( \begin{array}{c} 2 \\ 24 \end{array} \right)$$ $$\left[ \begin{array}{cc} 1 & 13 \\ 2 & 7 \end{array} \right] \left( \begin{array}{c} 3 \\ 4 \end{array} \right) = \left( \begin{array}{c} 55 \\ 34 \end{array} \right) \equiv \left( \begin{array}{c} 3 \\ 8 \end{array} \right)$$

Lastly, we re-interpret the resulting values as letters to arrive at the encrypted message: $$7,18,24,21,2,24,3,8 \rightarrow \textrm{ HSYVCYDI}$$

7. Encode the message "RUN AWAY NOW" with a Vigenere cipher using the keyword "YELLOW"

First, we write the letters of our keyword above the letters of our message (repeating the keyword as necessary), noting the appropriate values for each such letter $\pmod{26}$:

$$\begin{array}{cccccccccc} 24 & 4 & 11 & 11 & 14 & 22 & 24 & 4 & 11 & 11\\ Y & E & L & L & O & W & Y & E & L & L\\ 17 & 20 & 13 & 0 & 22 & 0 & 24 & 13 & 14 & 22\\ R & U & N & A & W & A & Y & N & O & W\\ \end{array}$$

Then, we add the shifts corresponding to the keyword letters to their matching values corresponding to the letters of our message $\pmod{26}$:

$$\begin{array}{cccccccccc} 24 & 4 & 11 & 11 & 14 & 22 & 24 & 4 & 11 & 11\\ Y & E & L & L & O & W & Y & E & L & L\\ 17 & 20 & 13 & 0 & 22 & 0 & 24 & 13 & 14 & 22\\ R & U & N & A & W & A & Y & N & O & W\\\hline 15 & 24 & 24 & 11 & 10 & 22 & 22 & 17 & 25 & 7 \end{array}$$

Finally, we reinterpret this last list of numbers as letters to arrive at our encrypted message:

$$15,24,24,11,10,22,22,17,25,7 \rightarrow \textrm{ PYYLKWWRZH}$$

8. Vector $W$ gives the distribution of A's, B's, C's, D's, and E's in a particular Kryptonian plaintext message, respectively. The other three vectors give the probability distributions of these letters (in the same order) for messages encoded with simple shift of 1, 2, or 3 letters, respectively. Which of the three probability vectors most closely matches $W$? (To be more precise, in terms of vectors, the one that most closely matches $W$ will form the smallest angle with $W$.)>

$$\begin{array}{c} W=(0.35, 0.3, 0.1, 0.05, 0.2)\\\\ P_1 = (0.35, 0.05, 0.1, 0.2, 0.3)\\ P_2 = (0.3, 0.35, 0.05, 0.1, 0.2)\\ P_3 = (0.2, 0.3, 0.35, 0.05, 0.1) \end{array}$$

Since vectors $P_1, P_2,$ and $P_3$ contain the exact same values, just in a different order, they all have the same magnitude.

Recall that the cosine of the angle between two vectors $x$ and $y$ is given by $$\cos \theta = \frac{x \cdot y}{|x||y|} \quad \textrm{ where } |v| \textrm{ is the magnitude of vector } v$$

This means that the vector that most closely matches $W$ (in the sense that the angle between $W$ and this vector is minimized) will have the largest dot product with $W$.

So, we compute the three dot products:

$$\begin{array}{rcl} W \cdot P_1 &=& (0.35)(0.35)+(0.3)(0.05)+(0.1)(0.1)+(0.05)(0.2)+(0.2)(0.3) = 0.2175\\ W \cdot P_2 &=& (0.35)(0.3)+(0.3)(0.35)+(0.1)(0.05)+(0.05)(0.1)+(0.2)(0.2) = 0.2555\\ W \cdot P_3 &=& (0.35)(0.2)+(0.3)(0.3)+(0.1)(0.35)+(0.05)(0.05)+(0.2)(0.1) = 0.2175 \end{array}$$

Thus $P_2$ most closely matches $W$.

9. Suppose $M$ is a linear transformation that both operates on, and produces 2-dimensional vectors. If the following are true
$$M\begin{pmatrix}2\\0\end{pmatrix} = \begin{pmatrix}1\\3\end{pmatrix} \quad \quad \textrm{and} \quad \quad M\begin{pmatrix}4\\6\end{pmatrix} = \begin{pmatrix}1\\-3\end{pmatrix}$$
Find $\displaystyle{M\begin{pmatrix}2\\5\end{pmatrix}}$

One way to proceed would be to realize that $M$ will have some matrix form $$M = \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right]$$ where

$$\left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] \left(\begin{array}{c} 2 \\ 0 \end{array} \right) = \left(\begin{array}{c} 1 \\ 3 \end{array} \right) \quad \textrm{ and } \quad \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] \left(\begin{array}{c} 4 \\ 6 \end{array} \right) = \left(\begin{array}{c} 1 \\ -3 \end{array} \right)$$

This leads to the system of equations given by

$$\begin{array}{rcl} 2a &=& 1\\ 2c &=& 3\\ 4a + 6b &=& 1\\ 4c + 6d &=& -3 \end{array}$$

Using the first two equations, we quickly find $a=1/2$ and $c = 3/2$.

Substituting these values into the second pair of equations, we find $b=-1/6$ and $d=-3/2$.

Thus, $$M = \left[ \begin{array}{cc} 1/2 & -1/6 \\ 3/2 & -3/2 \end{array} \right]$$ and $$M\begin{pmatrix} 2 \\ 5 \end{pmatrix} = \left[ \begin{array}{cc} 1/2 & -1/6 \\ 3/2 & -3/2 \end{array} \right] \begin{pmatrix} 2 \\ 5 \end{pmatrix} = \begin{pmatrix}1/6 \\ -9/2 \end{pmatrix}$$

10. Find $23^{534} \pmod{29}$ using the method of successive squaring (i.e., "fast exponentiation").

First we convert $534$ to binary:

$$\begin{array}{rcl} 534 &=& 2 \cdot 267 + 0\\ 267 &=& 2 \cdot 133 + 1\\ 133 &=& 2 \cdot 66 + 1\\ 66 &=& 2 \cdot 33 + 0\\ 33 &=& 2 \cdot 16 + 1\\ 16 &=& 2 \cdot 8 + 0\\ 8 &=& 2 \cdot 4 + 0\\ 4 &=& 2 \cdot 2 + 0\\ 2 &=& 2 \cdot 1 + 0\\ 1 &=& 2 \cdot 0 + 1\\ \end{array}$$

So $534 = 1000010110_2$.

Thus, $534 = 512 + 16 + 4 + 2$.

Now we compute some powers of $23\pmod{29}$ by successive squaring...

$$\begin{array}{rcccl} 23^{1} &\equiv& 23\\ 23^{2} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{4} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{8} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ 23^{16} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{32} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{64} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ 23^{128} &\equiv& 23^2 &\equiv& 529 &\equiv& 7\\ 23^{256} &\equiv& 7^2 &\equiv& 49 &\equiv& 20\\ 23^{512} &\equiv& 20^2 &\equiv& 400 &\equiv& 23\\ \end{array}$$

Note: not all of the calculation above is necessary, once when you get to $23^16 \equiv 7$ things have to repeat after that...

Multiplying the appropriate powers $\pmod{29}$, we have

$$\begin{array}{rcl} 23^{534} &=& 23^{512} \cdot 23^{16} \cdot 23^{4} \cdot 23^{2}\\ &\equiv& 23 \cdot 7 \cdot 20 \cdot 7\\ &=& 22540\\ &\equiv& 7 \end{array}$$

11. Find $23^{534} \pmod{29}$ using Fermat's Little Theorem.

Note, $29$ is prime and $29 \not\mid 23$, so Fermat's Little Theorem guarantees that $29^{28} \equiv 1\pmod{29}$, so...

$$23^{534} = (23^{28})^{19} \cdot 23^2 \equiv 1 \cdot 23^2 \equiv 529 \equiv 7 \pmod{29}$$
12. Find the value of $\varphi(75600)$.

Note that the prime factorization of $75600$ is given by $$75600 = 2^4 \cdot 3^3 \cdot 5^2 \cdot 7$$ Thus, $$\begin{array}{rcl} \varphi(75600) &=& \varphi(2^4) \varphi(3^3) \varphi(5^2) \varphi(7)\\ &=& (2^4-2^3)(3^3-3^2)(5^2-5)(7-1)\\ &=& 8 \cdot 18 \cdot 20 \cdot 6\\ &=& 17280 \end{array}$$

13. $$2^{340} \equiv 1 \pmod{341} \quad \quad \textrm{and} \quad \quad 3^{340} \equiv 56 \pmod{341}$$

Can you immediately tell (without further calculation) if 341 is prime or composite? Explain how.

$341$ must be composite, as Fermat's Little Theorem guarantees that if it were prime, and noting that $3 \not\equiv 0\pmod{341}$, then it would be the case that $3^{340} \equiv 1 \pmod{341}$.

Note, this theorem does not prohibit $2^{340} \equiv 1 \pmod{341}$ from occurring when the modulus is composite.

14. Solve the following system of congruences:

$$\begin{array}{rcl} x &\equiv& 8\pmod{11}\\ x &\equiv& 3\pmod{9} \end{array}$$

The first congruence tells us that $x = 11k+8$ for some integer $k$. So we substitute this into the second congruence:

$$11k + 8 \equiv 3\pmod{9}$$

Now, we can solve for $k$...

$$11k \equiv -5\pmod{9}$$

We'll need to find $11^{-1}\pmod{9}$ using the Euclidean Algorithm and "back-solving". Doing this yields $11^{-1} \equiv 5\pmod{9}$. Then, we multiply both sides by this value to eliminate the $11$:

$$k \equiv -25\pmod{9}$$

Adding three nines to the right side doesn't violate the congruence, but allows us to work with a positive value less than the modulus (which in general is desirable).

$$k \equiv 2\pmod{9}$$

This means that there is some integer $k_2$ such that

$$k = 9k_2 + 2$$

Recall, $x = 11k + 8$, so substitute the value for $k$ into this equation to find:

$$x = 11(9k_2+2)+8$$

Equivalently,

$$x = (11\cdot9)k_2 + 30$$

In congruence form, we then have:

$$x \equiv 30\pmod{99}$$