## Exercises2.8Exercises Set 3

###### 1.

Finish all investigations from in-class activities.

###### 2.

A message was encrypted with the affine cipher $CT\equiv 5PT+1 \pmod{26}\text{.}$

1. Solve for the DECRYPTION formula.

2. Then use the decryption formula to decrypt the ciphertext, OPOUB.

###### 3.

Find all possible values of $a$ and $b$ that would solve the pairs of linear congruences below. Then determine which, if any, values of $a$ and $b$ would be a valid affine cipher (i.e., would be decryptable). If there are no possible values of $a$ and $b$ explain why not.

1. The pair of equations:

\begin{equation*} 15 \equiv 2a+b \mod 26 \\ 18 \equiv 3a+b \mod 26 \end{equation*}
2. The pair of equations:

\begin{equation*} 15 \equiv 2a+b \mod 26 \\ 19 \equiv 3a+b \mod 26 \end{equation*}
3. The pair of equations:

\begin{equation*} 15 \equiv 4a+b \mod 26 \\ 18 \equiv 14a+b \mod 26 \end{equation*}
4. The pair of equations:

\begin{equation*} 15 \equiv 4a+b \mod 26 \\ 19 \equiv 14a+b \mod 26 \end{equation*}
5. The pair of equations:

\begin{equation*} 15 \equiv 3a+b \mod 26 \\ 2 \equiv 8a+b \mod 26 \end{equation*}
6. The pair of equations:

\begin{equation*} 19 \equiv 3a+b \mod 26 \\ 3 \equiv 7a+b \mod 26 \end{equation*}
###### 4.

Suppose we have a language with only 12 letters. How many affine ciphers would there be? (You should know how many multiplicative ciphers from a previous homework).

###### 5.

For each number $\{0,1,2,3, \cdots ,12 \}$ which has a multiplicative inverse mod 13, give the multiplicative inverse.

###### 6.

Find all solutions to the equations below or explain why there are none.

1. $\displaystyle 4x \equiv 5 \pmod{16}$

2. $\displaystyle 4x \equiv 12 \pmod{16}$

3. $\displaystyle 8x \equiv 4 \pmod{16}$

4. $\displaystyle 8x \equiv 8 \pmod{16}$

5. $\displaystyle 10x \equiv 6 \pmod{16}$

6. $\displaystyle 10x \equiv 5 \pmod{16}$

7. $\displaystyle 12x \equiv 4 \pmod{16}$

8. $\displaystyle 12x \equiv 10 \pmod{16}$

###### 7.

Show using the definition of modular arithmetic that 2 does not have a multiplicative inverse mod $n$ if $n$ is even. That is, you should show this directly from the definition and not using any theorems about multiplicative inverses.

###### 8.

Assume that $a$ is a valid multiplier for an affine cipher,

\begin{equation*} PT_1-PT_2 \equiv a(CT_1-CT_2) \pmod {26} \end{equation*}

and $(CT_1-CT_2)$ is even. Use an integer equation and what you know about even and odd numbers to show that $(PT_1-PT_2)$ must be even. (That is, do not use the theorem that we haven't fully proved about when congruences have a solution mod $n\text{.}$)

###### 9.

Assume that $a$ is a valid multiplier for an affine cipher,

\begin{equation*} PT_1-PT_2 \equiv a(CT_1-CT_2) \pmod {26} \end{equation*}

and $(CT_1-CT_2)$ is odd. Use an integer equation and what you know about even and odd numbers to show that $(PT_1-PT_2)$ must be odd. (That is, do not use the theorem that we haven't fully proved about when congruences have a solution mod $n\text{.}$)

###### 10.

Find the solution for $x$ in the following congruences:

\begin{equation*} 2x \equiv 1 \pmod{5} \end{equation*}
\begin{equation*} 2x \equiv 1 \pmod{7} \end{equation*}
\begin{equation*} 2x \equiv 1 \pmod{9} \end{equation*}
\begin{equation*} 2x \equiv 1 \pmod{11} \end{equation*}

Make a conjecture about the multiplicative inverse of 2 mod $n$ for odd $n\text{.}$ Prove it.

###### 11.

Find the solution for $x$ in the following congruences:

\begin{equation*} 3x \equiv 1 \pmod{5} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{8} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{11} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{14} \end{equation*}

Make a conjecture about the multiplicative inverse of 3 mod $n$ for $n$ of this form. Also come up with a definition for what of this form means.

###### 12.

Find the solution for $x$ in the following congruences:

\begin{equation*} 3x \equiv 1 \pmod{4} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{7} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{10} \end{equation*}
\begin{equation*} 3x \equiv 1 \pmod{13} \end{equation*}

Make a conjecture about the multiplicative inverse of 3 mod $n$ for $n$ of this form. Also come up with a definition for what of this form means.

###### 13.

Explain what each line of the following Sage code does.

###### 14.

Solve for $a,b,c,d,e\text{.}$

\begin{equation*} a^2c^2d=9900 \end{equation*}
\begin{equation*} a^3b^2e=17199 \end{equation*}
\begin{equation*} b^2d^2e^2=1002001 \end{equation*}