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!

• Problem 1: Suppose that $a$, $b$, and $c$ are arbitrary integers. Prove that if $a\mid b$ and $b\mid c$, then $a\mid c$.
  • 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.
• Problem 2: Suppose that $a$, $b$, and $d$ are arbitrary integers. Prove that if $d\mid a$ and $d\mid b$, then $d^2\mid ab$.
• Problem 3: Let $a,b\in \mathbb{Z}$ be integers. Prove that if $x^2 + ax + b = 0$ has an integer solution $r$, then $r$ divides $b$.
  • Hint: Try starting like this: “Assume that $x^2 + ax + b = 0$ has an integer solution $r$. Then $r^2 + ar + b = 0$.” Now keep going to show that $r$ divides $b$ according to the definition of divides.
  • Note: the assumption $a,b\in \mathbb{Z}$ only allows you to treat $a$ and $b$ as arbitrary integers, so make sure not to give them specific values.

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. Problem numbers refer to our book Elementary Number Theory, Second Edition.

• Page 3: Exercise 3
• Page 9: Problem 7

Homework 02

Problems to submit for grading

• Problem 1: Compute $\gcd(314,159)$ and $\gcd(4144,7696)$, each by using the Euclidean Algorithm. Please show all work.
• Problem 2: Find integers $x$ and $y$ so that $314x +159y = 1$. Please show all work.
• Problem 3: Let $a,b,c\in \mathbb{Z}$, and let $d = \gcd(a,c)$. Prove that if $c\mid ab$, then $c\mid db$.
  • Hint: consider using Theorem 4; the proof of Corollary 1 may provide extra inspiration.
• Problem 4: Assume that $p$ is prime number 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 4: Exercises 4,5
• Page 9: Problems 4,7
• Page 12: Exercise 3
• Page 19: Problem 8

Homework 03

Problems to submit for grading

• Problem 1: Let $n\in \mathbb{Z}$ with $n\ge 2$. Let $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ be the prime-power decomposition for $n$. Prove that if every exponent $e_1,\ldots,e_k$ is even, then $n$ is a perfect square (i.e. $n=m^2$ for some integer $m$).
• Problem 2: Let $n\in \mathbb{Z}$ with $n\ge 2$. Assume that $n$ is composite and that $p$ is the smallest prime factor of $n$. Prove that if $p > \sqrt[3]{n}$, then the number $\frac{n}{p}$ is prime.
  • Hint: Since $p$ is a divisor of $n$, you can write $n = mp$ for some $m\in \mathbb{Z}$. 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$?
• Problem 3: Determine if each equation has integer solutions or not.
  1. 14x + 34y = 90
  2. 14x + 35y = 91
  3. 14x + 36y = 93

Problems for extra practice

• Page 19: Problems 5, 9, 10
• Page 22: Exercise 2
• 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 04

Problems to submit for grading

• Problem 1: Find all integer solutions to each one of the following equations. Please show all work.
  1. $10x+15y = 14$
  2. $2x+6y = 20$
• Problem 2: Find all integer solutions to the system of equations: \[\begin{aligned}x+y+z &= 31 \\ x+2y+3z&=41 \end{aligned}\]
  • Hint: Try combining the two equations to get a new equation in two variables, which you can use the methods we developed to solve. Then plug your solutions into one of the original equations to solve for the remaining variable.
• Problem 3: Let $p$ be an arbitrary prime with $p\ge 5$. Prove that $p\equiv 1$ (mod 6) or $p\equiv 5$ (mod 6).
  • Hint: write out what $p\equiv a$ (mod 6) means according to the definition. Then use that $p$ is prime to explain why $p$ must not be equivalent to any of 0,2,3,4 when working mod 6.
• Problem 4: Find the least residue of each of the following without using a calculator. Please show your work.
  1. $(9876543)^3$ (mod $5$)
  2. $2^{113}$ (mod $5$)
     • Hint: $2^2 \equiv -1$ (mod $5$)

Problems for extra practice

• Page 26: Problems 6
• Page 32: Problems 2, 4
  • 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

• Problem 1: Determine the number of least residue solutions to each of the following congruences. Please explain how you determined the number of solutions, but you do not need to actually find the solutions.
  1. $3x\equiv 6$ (mod 15)
  2. $4x\equiv 8$ (mod 15)
  3. $5x\equiv 10$ (mod 15)
  4. $6x\equiv 11$ (mod 15)
• Problem 2: Find all least residue solutions to each of the following congruences.
  1. $3x\equiv 1$ (mod 19)
  2. $4x\equiv 6$ (mod 18)
  3. $20x\equiv 984$ (mod 1984)
• Problem 3: Find all least residue solutions to the system of congruences: \[\begin{aligned} x + 2y & \equiv 3 \text{ (mod 7)} \\ 3x + y & \equiv 2 \text{ (mod 7)}\end{aligned}\]
• Problem 4: 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: Suppose $n$ is the fourth power of some integer. Determine the possibilities (with proof) for the last digit of $n$.
  • Hint: look in your notes to see how we addressed when $n$ is a perfect square. The key idea was that if $d_0$ is the ones digit of an integer $a$, then $a\equiv d_0$ (mod $10$). Now, assume $n$ is a fourth power, so $n=m^4$ for some integer $m$. Then starting with the possibilities for $m$ (mod $10$), you should work out the possibilities for $n$ (mod $10$).
• 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

• Problem 1: Solve the following system of congruences: \[\begin{aligned} n & \equiv 1 \text{ (mod 3)} \\ 3n & \equiv 1 \text{ (mod 5)} \\ 6n & \equiv 1 \text{ (mod 7)}\end{aligned}\]
• Problem 2: Use Fermat’s Theorem to help you find the least residue of each of the following. Please justify your answers.
  1. $3^{32}$ (mod $31$)
  2. $13^{113}$ (mod $11$)
• Problem 3: Without using a calculator, determine the last digit of $7^{402}$. Please justify your answer.
• Problem 4: 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,2
• 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

• Problem 1: Let $p$ be an odd prime.
  1. Prove that $1+2+\cdots+(m-1) + m \equiv m(m+1)2^{-1} \text{ (mod p)}$.
     • Hint: you probably saw something like this in Calc 2; start by computing $2(1+2+\cdots+(m-1) + m)$ in the form $(1+2+\cdots(m-1) + m)+(m+ (m-1) + \cdots +2 + 1)$ and cleverly regrouping.
  2. Prove that $1^{p} + 2^{p} + \cdots + (p-1)^{p} \equiv 0 \text{ (mod p)}$.
     • Hint: Fermat.
• Problem 2: Let $p$ be a prime. Prove that $2(p-3)! + 1 \equiv 0 \text{ (mod p)}$.

• Problem 3: 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: If $p$ is prime and $a\not\equiv 0$ (mod $p$), then $a^{-1}$ is the unique solution to $ax\equiv 1$ (mod $p$).
• Problem 4: 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

• Problem 1: Compute $d$ and $\sigma$ of $10116=2^2\cdot 3^2\cdot 281$ and of $100116 = 2^2\cdot 3^5\cdot 103$
• Problem 2: Find two different numbers less than $8000$ that have exactly 60 positive divisors.

• Problem 3: Your friend wants to secretly send you the name of their favorite taqueria in Sacramento’s midtown area. 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

• Problem 1: Compute $\phi(20500)$. Note that $20500 = 2^2\cdot 5^3\cdot 41$.
• Problem 2: 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.
  1. $12^{202}$ (mod $125$)
  2. $5^{202}$ (mod $125$)
  3. $5^{363}$ (mod $297$)
  4. $3^{40}$ (mod $75$)
• Problem 3: Let $n$ be a positive integer, and suppose that $n$ is divisible by some odd prime $p$. Prove that $\phi(n)$ is even.
  • Hint: start by writing $n = mp^k$ with $\gcd(m,p)=1$ (which is to say that $p^k$ is the largest power of $p$ dividing $n$). Then try using Theorem 3.

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

• Problem 1: Compute $\operatorname{ord}_{13}(a)$ for each $a$ between $1$ and $12$. Which of the numbers are primitive roots of $13$? Please show your work.
• Problem 2: Compute $\operatorname{ord}_{20}(a)$ for each $a$ between $1$ and $20$ that is relatively prime to $20$. Which of the numbers are primitive roots of $20$? Please show your work.
• Problem 3: Let $p$ be a prime. Suppose that there is an integer $a$ such that $\operatorname{ord}_{p}(a) = k$. Prove that $p\equiv 1$ (mod $k$).
  • Hint: this proof can be very short. Notice that another way to state what you want to prove is that $k$ divides $p-1$. Now look back at our theorems.

Problems for extra practice

• Additional Problem: Let $p$ be a prime. Suppose that $p\equiv 1$ (mod $k$). Prove that there is an integer $a$ such that $\operatorname{ord}_{p}(a) = k$.
  • Hint: By a theorem, there exists a primitive root $g$ of $p$, so $\operatorname{ord}_{p}(g) = p-1$. Our main hypothesis is equivalent to $k$ dividing $p-1$; try considering $a = g^{(p-1)/k}$.

Homework 11

Problems for practice (nothing to submit this time)

• Problem 1: Determine which of the following congruences have solution. You can use any method you want including Euler’s Criterion or properties of the Legendre symbol.
  1. $x^2 \equiv 8$ (mod $53$)
  2. $x^2 \equiv 54$ (mod $7$)
  3. $x^2 \equiv 15$ (mod $31$)
  4. $x^2 \equiv 625$ (mod $9973$)
• Problem 2: Compute each of the following using properties of the Legendre symbol (including quadratic reciprocity).
  1. $\left(\frac{33}{71}\right)$
  2. $\left(\frac{34}{71}\right)$
  3. $\left(\frac{35}{71}\right)$
  4. $\left(\frac{36}{71}\right)$
• Problem 3: Find all solutions to $x^2\equiv 14$ (mod $31$) or explain why none exist.
• Problem 4: 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$.

Problems for extra practice

• Additional Problem: 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: 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$].”