Course Information

Homework Assignments

Due dates and submissions are managed in Canvas. Let me know if you have any questions!

Jump to specific assigment: HW01 | HW02 | HW03 | HW04 | HW05 | HW06 | HW07 | HW08 | HW09 | HW10 | HW11

Homework 01

Problems to submit for grading

These are the problems to turn in. Please organize your work, justify your steps, and write in complete sentences with correct punctuation. Once your finish these problems, please follow the directions in the Canvas assignment to submit them. If you have any questions (about the math or writing or submission process or anything), please let me know!

• Page 2: Exercise 2
  • Remember that $a$, $b$, and $c$ denote arbitrary integers.
  • Also remember that $a\mid b$ means “$a$ divides $b$” or “$a$ is a divisor of $b$”, so $a\mid b$ implies that there is some integer $x$ such that $b = ax$.
  • Hint: try to start like this: “Assume that $a\mid b$ and $b\mid c$. Since $a\mid b$, there is some integer $x$ such that $b = ax$. Also since $b\mid c$, there is some integer $y$ such that…” Now keep going to show that $a$ divides $c$; your goal is to show that $c$ is $a$ times some integer.
• Page 9: Problems 13, 15(a)
  • Hint: On #15(a), 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$…” Now keep going to show that $r$ divides $b$.

Problems for extra practice

Please try to solve these problems, but you do not turn them in. I’m happy to talk about these problems (or any others) if you have questions.

• Page 3: Exercise 3
• Page 4: Exercises 4,5,6
• Page 9: Problems 7

Homework 02

Problems to submit for grading

• Page 9: Problems 1, 3, 14
  • On 1, please use the Euclidean Algorithm, and make sure to show all work.
  • Remember to show all of your work on Problem 3; please do not just give the answer.
  • On 14, consider using Theorem 4. The proof of Corollary 1 may provide extra inspiration. Remember that $a$, $b$, and $c$ denote arbitrary integers.
• Additional Problem 1: Assume that $p$ is prime and that $p = n^3 - 1$ for some positive integer $n$. Prove that $p=7$.
  • Hint: think about how you can factor $n^3 - 1$? But, $p$ is prime, so what are its possible factors? What does this imply about $n$?

Problems for extra practice

• Page 9: Problems 4
• Page 12: Exercise 3
• Page 19: Problem 8
• Additional Problem: Determine which prime numbers divide $30!$ (i.e. “thirty factorial”). After that, try to describe in words (without computing) which prime numbers divide 100!.
  • Please make sure to justify your answer. You can use Lemma 6 from Section 2 even if we did not cover it in class yet.
  • Remember that $30! = 30\cdot 29 \cdot 28 \cdots 3\cdot 2\cdot 1$.
  • Hint: you do not need to completely factor $30!$ into prime powers to answer this question.
• Additional Problem: Suppose that $n$ is any four-digit integer and that $\operatorname{gcd}(n,100!) = 1$. Prove that $n$ must be prime.
  • Hint: What happens if you assume $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$; think about what the prime divisors of $100!$ are.

Homework 03

Problems to submit for grading

• Page 19: Problems 6, 12
  • On 6, please assume that $n\ge 2$. On this problem, the hypothesis is telling you that the prime-power decomposition for $n$ is $n=p_1^{2b_1}p_2^{2b_2}\cdots p_k^{2b_k}$ for some $b_1,b_2,\ldots,b_k \in \mathbb{Z}_{> 0}$ (notice how the exponents are even). Your goal is to show $n=m^2$ for some integer $m$. Try to make a guess for what $m$ should be and then verify that $n=m^2$.
  • On 12, please assume that $n$ is positive. Since $p$ is a divisor of $n$, you can write $n = mp$ for some $m\in \mathbb{Z}$. Now, assuming $p$ is the smallest prime divisor of $n$, you want to show that if $p > \sqrt[3]{n}$ then $m$ is prime. To do that, try considering what happens if $m$ is not prime. That would mean you can factor $m$ as $m = ab$ for some integers $a$ and $b$ with $1 < a,b < m$. What does this tell you about $n$? Can you show that this implies $p^3 \le n$?
• Page 23: Exercise 3
• Additional Problem 1: Suppose that $n$ is a positive integer that is divisible by both 3 and 7. Also assume that $n$ is a cube (so $n=m^3$ for some $m\in \mathbb{Z}$). What is the smallest that $n$ could be? (Make sure to explain/justify.)

Problems for extra practice

• Page 19: Problems 5, 9, 10
  • On 5, please assume that $n\ge 2$. Now, you know that $n=m^2$ for some integer $m$. Write out the prime-power decomposition for $m$ as $m=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ for some $a_1,a_2,\ldots,a_k \in \mathbb{Z}_{> 0}$, and see what you can then infer about $n$.
• Page 22: Exercise 2

Homework 04

Problems to submit for grading

• Page 26: Problems 5
  • 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 we developed 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!
• Page 32: Problems 9
  • Please remember to explain your answer.
• Additional Problem 1: Find all integer solutions to each of the following, and please show your work. Solve each of these equations separately—it is not a system of equations.
  1. $3x-4y = 0$
  2. $10x+15y = 14$
  3. $2x+6y = 20$
• Additional Problem 2: Find the least residue of each of the following. Please show your work.
  1. $7^3$ (mod $5$)
  2. $2^{100}$ (mod $5$) Hint: $2^2 \equiv -1$ (mod $5$)
  3. $2^{113} + 18$ (mod $5$)

Problems for extra practice

• Page 26: Problems 6
• Page 32: Problems 2, 4, 10
  • 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 can find their own.)

Homework 05

Problems to submit for grading

• Page 32-33: Problem 13
  • 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$ (mod $10$), you should work out the possibilities for $n$ (mod $10$). Don’t forget to explain your answer!
• Page 38: Exercise 5
  • Please explain how you determined the number of solutions, but you do not need to actually find the solutions.
• Page 40-41: Problems 2, 9(a)
  • Clarification: Please solve each equation in Problem 2 separately, so there are 4 parts to solve for this one. However, Problem 9(a) is a system of equations that you need to solve simultaneously.
• Additional Problem 1: Let $n\in \mathbb{Z}$ be a five digit number. Let $d_4d_3d_2d_1d_0$ be the digits of $n$, so $n = d_410^4 + d_310^3 + 10^2d_2 + 10d_1 + d_0.$ Prove that $n$ is divisible by $11$ precisely when $d_4 - d_3 + d_2 - d_1 + d_0$ is divisible by $11$ (i.e. when the “alternating sum of the digits” is divisible by $11$.)

Problems for extra practice

• Page 35: Exercise 1
• Additional Problem: Find all solutions to each of the following. If no solutions exist, explain why not. Please show your work—you’re welcome to use a table if you like.
  1. $x^3 +1 \equiv 0$ (mod $7$)
  2. $x^2 + 2 \equiv 0$ (mod $7$)
• Additional Problem: Let $n\in \mathbb{Z}$. Let $d_kd_{k-1}\cdots d_2d_1d_0$ be the digits of $n$, so $n = d_k10^k + d_{k-1}10^{k-1}+ \cdots + 10^2d_2 + 10d_1 + d_0.$ We have seen that
  • $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$.

  Develop and prove a rule for divisibility by $7$.

Homework 06

Problems to submit for grading

• Page 40-41: Problem 13
• Page 48-49: Problems 2, 3, 6
  • Make sure to show your work!
• Additional Problem 1: This problem has three parts.
  1. Use the Euclidean Algorithm to find an integer solution to $15x + 101y = 1$.
     • Look back at your notes from Section 1.
  2. Use the first part to find a solution to $15x \equiv 1 \;\; (\text{mod $101$})$.
     • Please briefly explain how you found your answer using part 1.
  3. Use your answer to the second part to solve $15x \equiv 2\;\; (\text{mod $101$}).$
     • See the notes from Section 5. Also, you can check your answer using WolframAlpha: it understands commands like solve 15x = 2 mod 101.

Problems for extra practice

• Page 40-41: Problem 3
• Page 48-49: Problems 1, 8
• Additional Problem: Let $p$ be a prime. Prove that for all $x,y\in \mathbb{Z}$, $(x+y)^p \equiv x^p + y^p$ (mod $p$).
  • Consider using the Corollary on page 45.

Homework 07

Problems to submit for grading

• Page 48-49: Problems 11, 15(a)
  • Try using Wilson’s Theorem for Problem 11 and Fermat’s Theorem for Problem 15(a).

• Additional Problem 1: Complete the following table of inverses modulo $13$. Please justify your answers by showing work.

  $a$	0	1	2	3	4	5	6	7	8	9	10	11	12
  $a^{-1}$	DNE	1	7

  • Recall our definition of $a^{-1}$ from class. Let $p$ be prime. Assume $a\not\equiv 0$ (mod $p$). The inverse of $a$, denoted $a^{-1}$, is the unique solution to $ax\equiv 1$ (mod $p$).
• Additional Problem 2: This problem has two parts. First use the (extended) Euclidean Algorithm to find an integer solution to $20u + 71v = 1$. Second, use your solution to the first part to find $20^{-1}$ modulo 71.
  • When you are done, you can check your work using WolframAlpha: it understands commands like inverse of 20 mod 71.

Homework 08

Problems to submit for grading

• Page 55-56: Problems 4, 9

• Additional Problem 1: Your friend wants to secretly send you the name of their favorite taqueria in Sacramento’s midtown area (because they don’t want it to become too popular). You decide to communicate using ElGamal encryption with $p=107$ and $g = 8$ (see class notes in Canvas). You select the decryption key $a=52$. Your friend secretly selects an encryption key $b$. You then send your friend the number $g^a = 8^{52} \equiv 40$ (mod $107$), and in return, your friend sends you the number $g^b \equiv 16$ (mod $107$). Your are now ready to communicate.

  Your friend sends you a seven-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 seven encrypted numbers as: \(c_1 = 14, c_2 = 87, c_3 = 81, c_4 = 34, c_5 = 48, c_6 = 47, c_7 = 21.\)

  1. Decrypt each of the seven 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.

Problems for extra practice

• Page 55-56: Problems 1, 2, 7

Homework 09

Problems to submit for grading

• Page 71-72: Problems 4, 6
  • 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$ (mod 16) by hand (perhaps looking for patterns).
• Additional Problem 1: Compute the least residue of each of the following. Use Theorem 1 of Section 9 when it applies. Show all of your work, but feel free to check your answers with WolframAlpha.
  • $12^{102}$ (mod $125$)
  • $25^{102}$ (mod $125$)
• Additional Problem 2: Let $n$ be a positive integer, and suppose that $n$ is divisible by some odd prime $p$. Prove that $\phi(n)$ is even.
  • Hint: factoring out the largest power of $p$ in $n$, you can write $n = mp^e$ with $\gcd(m,p)=1$. Theorem 3 from Section 9 is helpful.

Problems for extra practice

• Page 71-72: Problems 1, 2, 7
• Additional Problem: Find all positive integers $n$ such that $\phi(n)$ is odd.
• Additional Problem: Let $a$ and $m$ be relatively prime positive integers. Prove that $a^{\phi(m)} + m^{\phi(a)} \equiv 1$ (mod $m$).

Homework 10

Problems to submit for grading

• Page 81-82: 1, 5, 6
  • Reminder: please make sure to show all of your work!
• Additional Problem 1: Let $p$ be an odd prime. Prove there is exactly one least residue $0\le a < p$ such that $a$ has order $2$ modulo $p$.
  • 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?

Problems for extra practice

• Page 75: Exercise 2
• Page 81-82: 9
  • On Problem 9, please change the hypothesis from “$a\neq 1$” to “$a\not\equiv 1$ (mod p)”. 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 left-hand side…
• Additional Problem: Let $p$ be a prime of the form $4k +1$ for some $k\in \mathbb{Z}$. Show that there exists some $a \in \mathbb{Z}$ such that $a$ has order $4$ modulo $p$.
  • 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?

Homework 11

Problems for practice (nothing to submit this time)

• Page 93: Problems 2, 5
  • Remember to sure to show all of your work.
• Additional Problem 1: Find all solutions to $x^2\equiv 14$ (mod $31$) or explain why none exist.
• Additional Problem 2: Determine if $x^2+57x-21 \equiv 0$ (mod $59$) has solutions or not.
  • Hint: Try “completing the square”, but you will need to change the coefficient of $x$ first so that you can divide it by $2$.
• Additional Problem 3: Consider the sequence \(3,6,11,18,27,38,\ldots,n^2+2,\ldots\) Are any of the terms of this infinite sequence divisible by 113? Explain. (If your answer is yes, you do NOT need to find which terms are divisible by 113.)
• Additional Problem 4: Develop and prove a theorem, similar to Theorems 5 and 6, for computing $\left(\frac{-2}{p}\right)$. Your theorem should have the form:

  “Let $p$ be an odd prime. Then $\left(\frac{-2}{p}\right) = 1$ if [something is true about $p$ mod 8] and $\left(\frac{-2}{p}\right) = -1$ if [something else is true about $p$ mod $8$].”

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