Homework 2
Due: Friday, September 2

In this and all subsequent assignments, [TW] refers to Introduction to Crytography with Coding Theory (2nd edition), Wade Trappe and Lawrence Washington, 2006. Specifically, [TW]3.13.4 refers to problem $4$ from Section 3.13 of the text.

  1. Prove that if $a\vert(b+c)$, and if $a\vert b$, then $a\vert c$.

  2. Prove that if $a \equiv c \bmod n$, and if $b\equiv d \bmod n$, then $ab\equiv cd \bmod n$. Hint: Use the fact that $cd-ab = (cd - cb) + (cb - ab)$.

  3. Compute the greatest common divisor of the following pairs of numbers.
    \begin{alphabetize} \item $(781,994)$ \item $(6963,7385)$ \item $(408,1071)$ \end{alphabetize}

  4. [TW]3.13.4.


  5. \begin{alphabetize} \item Prove that, for all $n$, $\gcd(n,n+1) = 1$. \item For which $n$\ is $\gcd(n,n+2) = 1$? \end{alphabetize}

  6. [TW]3.13.1.

  7. Identify the Roman alphabet with $\integ/26$ (``the integers, considered modulo 26'') by letting $A$ be $1$, $B$ be $2$, and so on; then $Z = 0$.


    \begin{alphabetize} \par \item Express the ROT13 cipher as a function from $\int... ...iagram}\par Which of these would make a good cipher? Why? \par \end{alphabetize}


Jeff Achter