Due dates and submissions are managed in Canvas. Let me know if you have any questions!
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$, so your goal is to show that $c$ is $a$ times some integer.
Page 4: Exercises 4
Remember to show work and/or explain your answer.
Page 9: Problems 13 and 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: Exercise 5 and 6
Page 9: Problems 7
Homework 02
Problems to submit for grading
Page 9: Problems 1, 4, 14
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: Determine which prime numbers divide $30!$. After that, try to you describe in words (without computing) which prime numbers divide 100!.
Please make sure to justify your answer. 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 2: Suppose 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 12: Exercise 3
Page 19: Problem 8
Homework 03
Problems to submit for grading
Page 19: Problems 5, 6
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$.
On 6, you should also 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$.
Page 22: Exercise 2
Page 23: Exercise 3
Additional Problem 1: Suppose that $n$ is a positive even integer that is divisible by 7 and is also a cube (so $n=k^3$ for some $k\in \mathbb{Z}$). What is the smallest that $n$ could be? (Make sure to explain/justify.)
Problems for extra practice
Page 19: Problem 9
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 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!
Page 32: Problems 2, 9
Please remember to show work and/or explain your answers.
Additional Problem 1: Find all integer solutions to each of the following. Please show your work.
$3x-4y = 0$
$10x+15y = 14$
$2x+6y = 20$
Please solve each of these equations separately. It is not a system of equations.
Additional Problem 2: Find the least residue of each of the following. Please show your work.
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.)
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 35: Exercise 1
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
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.
$x^3 +1 \equiv 0$ (mod $7$)
$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$.
Here’s another one:
$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$
Develop and prove a similar rule for divisibility by $7$.
Homework 06
Problems to submit for grading
Page 40-41: Problem 13
Page 48-49: Problems 3, 6, 8
Make sure to show your work!
Additional Problem 1: This problem has two parts. First use the Euclidean Algorithm to find an integer solution to $15u + 101v = 1$. Second, use your solution to the first part to solve the congruence $15x \equiv 2\;\; (\text{mod $101$}).$
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.
Additional Problem 2: Let $p$ be a prime. Prove that for all $a,b\in \mathbb{Z}$, $(a+b)^p \equiv a^p + b^p$ (mod $p$).
Make sure to clearly state which theorem(s) you use.
Problems for extra practice
Page 40-41: Problem 3
Page 48-49: Problems 1, 2
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 $7$. Please show your work.
$a$
0
1
2
3
4
5
6
$a^{-1}$
DNE
Recall our definition of $a^{-1}$ from class:
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$ (mod $p$)}.
Additional Problem 2: This problem has two parts. First use the 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.
Additional Problem 3: You are communicating with a friend using ElGamal encryption with $p=107$ and $g = 8$ (see class notes in Canvas). 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.\)
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.
Convert the decrypted numbers to letters using the rule $A=1, B=2, \ldots, Z = 26$ to figure out your friend’s message.
Homework 08
Problems to submit for grading
Page 55-56: Problems 4, 9
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 $a$ and $m$ be relatively prime positive integers. Prove that $a^{\phi(m)} + m^{\phi(a)} \equiv 1$ (mod $m$).
Additional 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: 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 55-56: Problems 1, 2, 7
Page 71-72: Problems 1, 2, 7
Additional Problem: Find all positive integers $n$ such that $\phi(n)$ is odd.
Homework 09
Problems to submit for grading
Page 75: Exercise 2
Page 81-82: 1, 5, 6, 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…
Reminder: please make sure to show all of your work!
Additional Problem 1: Let $p$ be an odd prime. Show that there exists exactly one least residue $0\le a < p$ such that $a$ has order $2$ modulo $p$.
You need to do two things. First show, by example, that there is some element $a$ of order 2. Next, you need show that every element of order two is congruent to the $a$ that you found. 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
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 10
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.
