Review Exercises (Set B)

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

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

  3. Prove the converse of Wilson's theorem is true.  

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

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

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

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

  8. Express $\sqrt{17}$ in continued fraction form.  

  9. $[4;\overline{1,3,1,8}]$ is the square root of what value?  

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

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

  12. Find the value of $\varphi(75600)$.  

  13. Suppose you know the following:
    $$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.  

  14. Find one solution for $x$ if
    $$x \equiv 8 \pmod{23} \quad \quad \textrm{and} \quad \quad x \equiv 15 \pmod{17}$$

◆ ◆ ◆