Reminder: make sure to show all of your work.

Hint: Try "completing the square", but you will need to change the coefficient of $x$ first so that you can divide it by $2$.

Hint: Try using a property of the Legendre symbol together with Theorems 5 and 6.

• Reminder: make sure to show all of your work.
• Hint: on Problem 9, please change the hypothesis to $a\not\equiv 1$ (mod p), instead of $a\neq 1$ (mod p); otherwise, it isn't true. Then, start by showing that $a$ having order $t$ modulo $p$ implies that $a$ is a root of $x^t-1\equiv 0$ (mod $p$). Now factor the LHS...

Hint: if $a$ has order $2$, then $a$ is a solution to $x^2 \equiv 1$ (mod $p$). In Section 6, we determined the solutions to $x^2 \equiv 1$ (mod $p$); only one of them has order $2$, which one is it?

Hint: By Theorem 6, there exists a primitive root $g$ of $p$. Let $t$ be the order of $g$. (What is $t$ equal to?) Now, if $k$ divides $t$ and $a = g^{t/k}$, what is $a^k$ equal to?

Hint: on Problem 6, remember that Theorem 1 only applies when $\gcd(a,16) = 1$; in the other cases, you'll need to compute $a^8\;\text{(mod 16)}$ by hand (perhaps looking for patterns).

1. $12^{102}$ (mod $125$)
2. $25^{102}$ (mod $125$)

Hint: Theorem 3 is helpful.

You are communicating with a friend using ElGamal encryption with $p=107$ and $g = 8$ (see the notes). Your friend wants to send you a message, so you select the decryption key $a=66$. Your friend secretly selects an encryption key $b$. You then send your friend the number $g^a = 8^{66} \equiv 33$ (mod $107$), and in return, your friend sends you the number $g^b \equiv 68$ (mod $107$). Your are now ready to communicate.

Your friend sends you a nine-letter message by converting each letter to a number, encrypting the number, and then sending the encrypted numbers one at a time. You receive the nine encrypted numbers as $$c_1 = 47, c_2 = 27, c_3 = 7, c_4 = 103, c_5 = 38, c_6 = 56, c_7 = 29, c_8 = 45, c_9 = 18.$$

1. Decrypt each of the nine numbers. You can use WolframAlpha for your computations. For example, if you need to find $29^{-1}$ (mod $107$), you would type in 29^(-1) mod 107 or alternatively inverse of 29 mod 107.

   Hint: Once you decrypt $c_1$, you should be able to reuse much of your work to make it easier to decrypt the remaining letters.

2. Convert the decrypted numbers to letters using the rule $A=1, B=2, \ldots, Z = 26$ to figure out your friend's message.

Hint: there is a hint in the "Comments" section of the book for Problem 11. Try using Fermat's Theorem for Problem 15(a).

Definition: Let $p$ be prime. If $a\not\equiv 0$ (mod $p$), then the unique solution to $ax\equiv 1$ (mod $p$) is denoted $a^{-1}$. Thus, $$aa^{-1} \equiv 1\quad \text{(mod $p$)}.$$

When you are done, you can check your work using WolframAlpha: it understands commands like "inverse of 20 mod 71".

For the first part, you can look back at the notes from Section 1. For the second part, see the last example in the notes from Section 5. When you are done, you can check your work using WolframAlpha: it understands commands like "solve 15x = 2 mod 101".

Make sure to clearly state which theorem(s) you use.

Hint: on Problem 4, you should disprove the statement by giving a concrete example of $a$, $b$, and $m$ for which it fails. (There are many such examples, so everyone should try to find their own.)

Hint: on Problem 13, you should look in your notes to see how we addressed Problem 12. The key idea is that if $d_0$ is the ones digit of $n$, then $n\equiv d_0$ (mod $10$). Now, if $n$ is a fourth power, then $n=m^4$, so starting with the possibilities for $m$ modulo $10$, you should work out the possibilities for $n$ modulo $10$. Don't forget to explain your answer!

1. $x^3 +1 \equiv 0$ (mod $7$)
2. $x^2 + 2 \equiv 0$ (mod $7$)

• $n$ is divisible by $3$ precisely when the sum of the digits is divisible by $3$.
• $n$ is divisible by $11$ precisely when the alternating sum of the digits is divisible by $11$.

• $n$ is divisible by $13$ precisely when $(d_0 -3d_1 -4d_2 -d_3) + (d_4 -3d_5 -4d_6 -d_7) + \cdots$ is divisible by $13$

Clarification: on Problem 2, you are are asked to solve each of the three equations separately. It is not a system of equations.

Hint: Problem 5 is a system of equations. Try "combining" the equations to get a new equation in two variables, which you can use the methods of the book to solve. Then plug your solutions into the original equations to solve for the remaining variable. The answer is in the back of the book, but please show your work! Problem 6 is very similar to this one.

1. $7^3$ (mod $5$)
2. $2^{100}$ (mod $5$) Hint: $2^2 \equiv -1$ (mod $5$)
3. $2^{113} + 18$ (mod $5$)

Hint: On #5, please assume that $n\ge 2$. Now, you know that $n=m^2$ for some integer $m$. Assume you know the prime-power decomposition for $m$, and see what you can then infer about $n$. On #6, you are assuming that the prime power decomposition for $n$ is $n=p_1^{2a_1}p_2^{2a_2}\cdots p_k^{2a_k}$ (notice how the exponents are even). Now, you want to show $n=m^2$ for some integer $m$. Try to explicitly write down what $m$ is and then verify that $m^2 = n$.

1. $4x-10y = 50$
2. $4x-10y = 51$

Hint: on 14, consider using Theorem 4—the proof of Corollary 1 may provide extra inspiration.

Hint: What if $n$ is not prime? Then Lemma 4 of Section 2 tells you something about the prime divisors of $n$. But, $\operatorname{gcd}(n,100!) = 1$ also tells you something about the prime divisors of $n$.

Hint: can you factor $p$? But, $p$ is prime, so what are its possible factors? What does this imply about $n$?

Hint: try to start like this: "Assume that $a\mid b$ and $b\mid c$. Since $a\mid b$, there is some integer $d$ such that $b = ad$. Also since $b\mid c$, there is some integer $e$ such that…" (keep going to show that $a$ divides $c$)

Please make sure to briefly explain/justify your answers.

Hint: On #15, try to start like this: "Assume that $x^2 + ax + b = 0$ has an integer root. So there is some integer $r$ such that $r^2 + ar + b = 0$.…" (keep going to show that $r$ divides $b$)