| | |
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{41}$.
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}$$Find all solutions to $17x \equiv 15\pmod{41}$
Find all solutions to $9x \equiv 3\pmod{15}$
Find all solutions to $13x \equiv 5\pmod{26}$
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}$.
Show that if $S$ is the set of all values of the form $x+y\sqrt{3}$ where $x$ and $y$ are integers, and if $a+b\sqrt{3}$ is not a unit for $S$, then $a+b\sqrt{3} \neq 2-\sqrt{3}$.
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}$$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.
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}$$
Encode "VALLEY" with a Hill Cipher and encrypting matrix given by
$$E=\left[ \begin{array}{cc} 9 & 6 \\ 4 & 1 \end{array} \right]$$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}$$Encode the message "NUMBER THEORY" with a Vigenere cipher using the keyword "MATH"
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}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$.
Which angle is smaller: $\theta_1$, the angle between vectors $u = (.5,.3,.2)$ and $v_1=(.7,.2,.1)$; or $\theta_2$, the angle between vectors $u$ and $v_2 = (.2,.1.,.7)$?
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}$$
Suppose $M$ is a linear transformation that operates on, and produces 2D vectors. Find $M$'s matrix form if
$$M\left(\begin{array}{c}0\\3\end{array}\right)=\left(\begin{array}{c}6\\9\end{array}\right) \quad \quad \textrm{ and } \quad \quad M\left(\begin{array}{c}4\\1\end{array}\right) = \left(\begin{array}{c}6\\19\end{array}\right)$$Convert $\displaystyle{\frac{100}{17}}$ to its simple continued fraction form.
The fastest way to convert this value to continued fraction form is to pull the "quotients" (shown in red below) from the calculations made in the Euclidean Algorithm:
100 = 5 * 17 + 15 17 = 1 * 15 + 2 15 = 7 * 2 + 1 2 = 2 * 1 + 0 gcd(100,17) = 1
So the continued fraction we seek is $$5 + \cfrac{1}{1+\cfrac{1}{7+\cfrac{1}{2}}} = [5;1,7,2]$$
Express $\sqrt{17}$ in continued fraction form.
First, we separate the integer part and fractional part of $\sqrt{17}$. Since $4^2 \lt 17 \lt 5^2$, it must be the case that $4 \lt \sqrt{17} \lt 5$. Consequently, the integer part of $\sqrt{17}$ is 4, and the fractional part is what is left (i.e., $\sqrt{17}-4$).
$$\sqrt{17} = 4 + (\sqrt{17} - 4)$$
Now, to have $\sqrt{17}$ written as a continued fraction, we need the fractional part to be expressed as one over something. Reciprocating things twice produces the desired numerator of one, without changing the overall value:
$$\sqrt{17} = 4 + \frac{1}{\displaystyle{\frac{1}{\sqrt{17}-4}}}$$ Now, we wish to repeat the process - and write $1/(\sqrt{17}-4)$ as an integer plus some fractional part. However, it is harder to see clearly what the integer part will be. Consequently, we multiply by the conjugate to get rid of the square root in the denominator: $$\sqrt{17} = 4 + \frac{1}{\displaystyle{\frac{1}{\sqrt{17}-4} \cdot \frac{\sqrt{17} + 4}{\sqrt{17}+4}}}$$ This simplifies to $$\begin{array}{rcl} \sqrt{17} &=& 4 + \frac{\displaystyle{1}}{\displaystyle{\frac{\sqrt{17}+4}{1}}}\\\\ &=& 4 + \frac{\displaystyle{1}}{\displaystyle{\sqrt{17}+4}} \end{array}$$ Now, identifying the integer part of the denominator is more easily done. Recalling again that we know $4 \lt \sqrt{17} \lt 5$, the integer part of of $\sqrt{17}$ must be 4, which makes $8$ the integer part of $\sqrt{17}+4$. Noting that $\sqrt{17} + 4 = 8 + (\sqrt{17} - 4)$ means that $(\sqrt{17} - 4)$ must be the fractional part of the denominator. So we have: $$\sqrt{17} = 4 + \frac{\displaystyle{1}}{\displaystyle{8 + (\sqrt{17} - 4)}}$$ Seeing the duplication of $(\sqrt{17}-4)$, we immediately know that further double reciprocations would continue to produce integer parts in the denominators of $8$. Consequently, the continued fraction form we seek is $$\sqrt{17} = 4 + \frac{\displaystyle{1}}{8 + \frac{\displaystyle{1}}{\displaystyle{8} + \frac{\displaystyle{1}}{\displaystyle{8} + \cdots}}}$$ Of course, we can write this more simply, using the conventional way to write continued fractions with repeated values: $$\sqrt{17} = [4;\overline{8}]$$Express the continued fraction $[3;2,5,7]$ as a (regular) fraction.
$$[3;2,5,7] = 3 + \cfrac{1}{2 + \cfrac{1}{5 + \cfrac{1}{7}}} = 3 + \cfrac{1}{2 + \cfrac{7}{36}} = 3 + \cfrac{36}{79} = \cfrac{273}{79}$$
$[4;\overline{1,3,1,8}]$ is the square root of what value?
It will simplify things to focus just on the fractional part of the value in question. Let us denote this by $y= [0;\overline{1,3,1,8}]$.
The repeated part of the continued fraction above means that we can write $y$ in terms of itself, as shown below:
$$y = \frac{\displaystyle{1}}{\displaystyle{1+\frac{\displaystyle{1}}{\displaystyle{3+\frac{\displaystyle{1}}{\displaystyle{1 + \frac{\displaystyle{1}}{\displaystyle{8+y}}}}}}}}$$ The fraction on the right, however, can be greatly simplified in the normal way: $$\begin{array}{rcccl} y &=& \frac{\displaystyle{1}}{\displaystyle{1+ \frac{\displaystyle{1}}{\displaystyle{3 + \frac{\displaystyle{1}}{\frac{\displaystyle{9+y}}{\displaystyle{8+y}}}}}}} &=& \frac{\displaystyle{1}}{\displaystyle{1+ \frac{\displaystyle{1}}{\displaystyle{3 + \frac{\displaystyle{8+y}}{\displaystyle{9+y}}}}}}\\\\ &=& \frac{\displaystyle{1}}{\displaystyle{1 + \frac{\displaystyle{1}}{\frac{\displaystyle{4y+35}}{\displaystyle{9+y}}}}} &=& \frac{\displaystyle{1}}{\displaystyle{1}+\frac{\displaystyle{9+y}}{\displaystyle{4y+35}}}\\\\ &=& \frac{\displaystyle{1}}{\frac{\displaystyle{5y+44}}{\displaystyle{4y+35}}} &=& \frac{\displaystyle{4y+35}}{\displaystyle{5y+44}} \end{array}$$So then, we know $$y = \frac{4y+35}{5y+44}$$ However, multiplying both sides by $5y+44$ yields a quadratic equation. (This always happens!) $$5y^2+44y = 4y+35$$ which simplifies to $$y^2+8y-7 = 0$$ Using the quadratic formula (and noting that $y \gt 0$) we can solve for $y$: $$y = -4 + \sqrt{23}$$ Finally, adding back in the integer part (i.e., $4$) of the original continued fraction given, we have $$[4;\overline{1,3,1,8}] = 4 + y = \sqrt{23}$$
It is known that $1997$ is prime. Find the least positive residue of $\frac{2000!}{1997}\pmod{1997}$.
We know by Wilson's Theorem that $1996 \equiv -1\pmod{1997}$. Noting that $\frac{2000!}{1997} = 2000 \cdot 1999 \cdot 1998 \cdot 1996!$, we simply reduce $2000 \cdot 1999 \cdot 1998 \cdot (-1)\pmod{1997}$, or more simply, $3 \cdot 2 \cdot 1 \cdot (-1) \equiv -6$. Wanting the least positive residue, we add $1997$ to this to get our final answer: $1991$
Suppose it is known that 7247 is prime. Reduce $7245!$ to its least postive residue$\pmod{7247}$ (i.e., find $x$ where $0 \lt x \lt 7247$ and $7245! \equiv x\pmod{7247}$).
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}$$