## Exercises2.5Exercises Set 2

###### 1.

Finish all investigations from in-class activities.

###### 2.

The encryption formula for a multiplicative cipher is $CT\equiv 15PT \pmod {26}\text{.}$

1. Solve the encryption formula for PT; that is, find the decryption formula.

2. Use your decryption formula to decyrpt the ciphertext, PAECN.

3. What decimation of the alphabet corresponds to $CT\equiv 15PT \pmod {26}\text{?}$

###### 3.

Consider a multiplicative cipher with the formula $CT\equiv aPT \pmod{26}$ for a valid choice of $a\text{.}$ (I.e., all choices of $a$ where the cipher can be decrypted.) Which two letters always (for all valid choices of $a$) get encrypted as themselves?

###### 4.

Consider a multiplicative cipher with the formula $CT\equiv aPT \pmod{26}$ for a valid choice of $a\text{.}$ (I.e., all choices of $a$ where the cipher can be decrypted.) Which of the following is possible? If possible, solve for $a\text{;}$ if not possible, explain why not.

1. A plaintext L corresponds to ciphertext of D.

2. A plaintext C corresponds to ciphertext of O.

3. A plaintext L corresponds to ciphertext of E

4. A plaintext E corresponds to ciphertext of L.

###### 5.

Suppose a language has only 12 letters, ABCDEFGHIJKL. Find all multipliers $a$ such that $CT\equiv aPT \pmod{12}$ is a valid cipher. (I.e., all choices of $a$ where the cipher can be decrypted.)

###### 6.

Suppose a language has only 12 letters, ABCDEFGHIJKL, for each of the multiplicative ciphers below, determine all letters which get encrypted as A:

1. $\displaystyle CT\equiv 3PT \pmod{12}$

2. $\displaystyle CT\equiv 10PT \pmod{12}$

3. $\displaystyle CT\equiv 8PT \pmod{12}$

4. $\displaystyle CT\equiv 4PT \pmod{12}$

5. $\displaystyle CT\equiv 6PT \pmod{12}$

6. $\displaystyle CT\equiv 5PT \pmod{12}$

7. Make a conjecture about what $a$ tells you about how many letters get encrypted as A in a multiplicative cipher $CT\equiv aPT \pmod{12}\text{.}$

###### 7.

Suppose a language has only 12 letters, ABCDEFGHIJKL. Consider a multiplicative cipher with the formula $CT\equiv aPT \pmod{12}\text{.}$ Find all possible values for $a$ that satisfy the conditions below or explain why there are no possible values for $a\text{.}$ If there are values for $a$ determine if they would be a valid choice of $a$ for this language. (I.e., a choice of $a$ where the cipher can be decrypted.)

1. A plaintext D corresponds to ciphertext of I.

2. A plaintext I corresponds to ciphertext of E.

3. A plaintext F corresponds to ciphertext of H.

4. A plaintext F corresponds to ciphertext of B.

###### 8.

Solve the equations below for PT.

1. $\displaystyle CT\equiv 5PT+1 \pmod{26}$

2. $\displaystyle CT\equiv 17PT+20 \pmod{26}$

###### 9.

Solve, if possible, the following congruences for $x\text{.}$

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

2. $\displaystyle 2x \equiv 1 \pmod{5}$

3. $\displaystyle 3x \equiv 1 \pmod{5}$

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

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

###### 10.

Solve, if possible, the following congruences for $x\text{.}$

1. $\displaystyle 1x \equiv 1 \pmod{6}$

2. $\displaystyle 2x \equiv 1 \pmod{6}$

3. $\displaystyle 3x \equiv 1 \pmod{6}$

4. $\displaystyle 4x \equiv 1 \pmod{6}$

5. $\displaystyle 5x \equiv 1 \pmod{6}$

6. $\displaystyle 6x \equiv 1 \pmod{6}$

###### 11.

Solve, if possible, the following congruences for $x\text{.}$

1. $\displaystyle 2x \equiv 1 \pmod{7}$

2. $\displaystyle 3x \equiv 1 \pmod{7}$

3. $\displaystyle 4x \equiv 1 \pmod{7}$

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

5. $\displaystyle 6x \equiv 1 \pmod{7}$

###### 12.

Solve, if possible, the following congruences for $x\text{.}$

1. $\displaystyle 2x \equiv 1 \pmod{8}$

2. $\displaystyle 3x \equiv 1 \pmod{8}$

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

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

5. $\displaystyle 6x \equiv 1 \pmod{8}$

6. $\displaystyle 7x \equiv 1 \pmod{8}$

###### 13.

Solve, if possible, the following congruences for $x\text{.}$

1. $\displaystyle 2x \equiv 1 \pmod{9}$

2. $\displaystyle 3x \equiv 1 \pmod{9}$

3. $\displaystyle 4x \equiv 1 \pmod{9}$

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

5. $\displaystyle 6x \equiv 1 \pmod{9}$

6. $\displaystyle 7x \equiv 1 \pmod{9}$

7. $\displaystyle 8x \equiv 1 \pmod{9}$

###### 14.

Solve, if possible, the following congruences for $x$ in terms of $y\text{.}$ Hint: use some of your previous work to help you.

1. $\displaystyle 2x+5 \equiv y \pmod{9}$

2. $\displaystyle 2x+1 \equiv y \pmod{5}$

3. $\displaystyle 3x-3 \equiv y \pmod{7}$

4. $\displaystyle 3x+5 \equiv y \pmod{8}$

###### 15.

Explain why $1x \equiv 1 \pmod{n}$ always has a solution for $x$ for any $n>1\text{.}$

###### 16.

Explain why $nx \equiv 1 \pmod{n}$ never has a solution for $x$ for any $n>1\text{.}$

###### 17.

Use results from your computational problems to make a conjecture about when $ax \equiv 1 \pmod{n}$ has a solution for $x\text{.}$

###### 18.

Suppose a language has only 12 letters, ABCDEFGHIJKL. Make a conjecture about how $a$ is related to the number of letters that get encrypted as A in a multiplicative cipher $CT\equiv aPT \pmod{12}\text{.}$

###### 19.

Using the definition of even and a definition of modular arithmetic prove that if $a$ is even then $ax \equiv a(x+13) \pmod {26}\text{.}$ Explain why this means that $a$ is a bad multiplier mod 26.

###### 20.

Use the definition of even and a definition of modular arithmetic to prove that if $a$ is even and $ax \equiv y \pmod{26}$ for any integer $x$ then $y$ must be an even integer.

###### 21.

Give a counterexample to show that if $a$ is even and $ax \equiv y \pmod{9}$ then it is possible for $y$ to be odd. That is, give an example of $a,x,y$ such that $a$ is even and $ax \equiv y \pmod{9}$ and $y$ is odd. Explain why this case is different from the previous problem.

###### 22.

Pick a definition of modular arithmetic and show that if $a,b,c$ are all integers and $n$ is a positive integer, then $a \equiv b \pmod n$ implies that $ac \equiv bc \pmod n\text{.}$

###### 23.

Show that the reverse direction need not apply even if all terms are integers. That is, find an example where $c \;{ \not\equiv} \;0 \pmod n$ and $ac \equiv bc \pmod n$ but $a\: {\not \equiv} \:b \pmod n\text{.}$ (I.e., $a$ is not congruent to $b$ mod $n\text{.}$).

###### 24.

Solve the following puzzles. (Puzzles taken from an NSA Women in Mathematics Symposium.)

1. if WASHINGTON equals 2311989147201514 and ANNAPOLIS equals 114141161512919, what does BALTIMORE equal?

2. if BALTIMORE equal 3237712341476111 and ANNAPOLIS equals 2434325347372367, what does WASHINGTON equal?

3. If WOMEN equals 140 and MATHEMATICS equals 224, what does IN equal?

###### 25.

A Puzzling PARAGRAPH: This conundrum is from PBS's Cartalk. Can you crack it? That is, find an oddity that this paragraph has.

“This paragraph is odd. What is its oddity? You may not find it at first, but this paragraph is not normal. What is wrong? It's just a small thing, but an oddity that stands out if you find it. What is it? You must know. Your days will not go on until you find out what is odd. You will pull your hair out. Your insomnia will push you until your poor brain finally short-circuits trying to find an oddity in this paragraph. Good luck.”