Reminder: make sure to show all of your work.

Hint: Complete the square. Change the coefficient of $x$ so 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 $x$ has order $2$, then $x$ is a solution to $x^2 \equiv 1$ (mod $p$). What are the solutions? Only one of them has order $2$, which one is it?

Hint: Theorem 2.

Hint: By Theorem 6, there exists a primitive root $g$ of $p$. Let $t$ be the order of $g$. What is the value of t? If $m$ divides $t$ and $a = g^{t/m}$, what is $a^m$?

Hint: on Problem 7, the theorems from the section are quite helpful, but make sure to cite which ones you use.

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

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 \equiv -1$ (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$)

1. $3x\equiv 2$ (mod $5$)
2. $3x\equiv 0$ (mod $9$)
3. $x^3 \equiv -1$ (mod $7$)
4. $x^2 - 2 \equiv 0$ (mod $7$)

Hint: we did something very similar to these in class.

Hint: look at our warm-up problems—try to factor $n^k - 1$.

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

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

Find all solutions (if any) to each of the following:

1. $x^2 = -1$ in $\mathbb{Z}$
2. $x^2 \equiv -1$ (mod 5)
3. $x^2 \equiv -1$ (mod 7)

1. $x^2 = 0$ in $\mathbb{Z}$
2. $x^2 \equiv 0$ (mod 5)
3. $x^2 \equiv 0$ (mod 8)

Draw a number line from -20 to 20.

• Label red all numbers $a$ such that $a\equiv 0$ mod 4.
• Label blue all numbers $a$ such that $a\equiv 1$ mod 4.
• Label green all numbers $a$ such that $a\equiv 2$ mod 4.

None ☹

It's my first day selling burgers and burritos on the beach. At the end of my shift, I sold $\$107$ worth of food. I just remembered that my boss wanted me to keep track of how many of each item I sold. I know that I definitely sold more burritos than burgers, and I bought two burgers myself. Can you help me? Oh, and burgers are $\$5$ a piece while burritos are $\$6$ a piece.

Suppose you know that $n$ is a square integer and that the only prime divisors of $n$ are 2 and 7. What is the smallest that $n$ can be?

Let $n$ be a postive integer.

1. For what values of $n$ (if any) is $n^2-1$ a prime number?
2. For what values of $n$ (if any) is $n^3-1$ a prime number?
3. For what values of $n$ (if any) is $n^4-1$ a prime number?
4. Can you make (and possibly prove) and conjectures based off of these observations?

Define a square filling of of a rectangle to be a subdivision of the rectangle into squares of the same size.

1. Find a square filling of a $2 \times 3$ rectangle. Repeat for a $4 \times 4$ rectangle—can you find different square fillings?
2. What is the fewest possible number of squares in a square filling of a $12 \times 20$ rectangle?
3. What is the fewest possible number of squares in a square filling of a $m \times n$ rectangle with $m,n\in \mathbb{Z}^+$?

1. Find $(21,22)$, $(35,36)$, and $(48,49)$.
2. Conjecture + Prove: if $n\in \mathbb{Z}^+$, then $(n,n+1) = $ ?
3. Conjecture + Prove: if $n\in \mathbb{Z}^+$, then $(n,n+2) = $ ?