My role as your TA is to provide you with personalized support to help you learn the course content. I will be exactly as motivated to ensure you pass this course as I see that you are motivated to learn the material. So if you have questions or comments or concerns, please email me at . My office hours will be Wednesdays 4–6pm in Webber 1303C. You don't need to have questions to come to office hours. It's alright to show up just to work on homework with me there in case something comes up you want to talk about.
This course will follow Elements of Number Theory: Lecture Notes by Felix Lazebnik for the first half of the quarter. For the rest of the quarter the course will follow Elementary Number Theory by Wissam Raji, Chapter 5 and part of Chapter 4 in particular, and we’ll also look at representing integers as sums of squares and Pythagorean triples and roots of quadratic forms.
You may be interested to realize that there will be no quizzes in this discussion, and that homework is collected during lecture. Feel free to manage your time accordingly.
Considering the results of the survey I sent out, we’ll run the discussion section like this: If I receive an email well before our discussion hour asking about some specific topic, either something from lecture that could do with more explanation or something related but tangential to course curriculum, I can lecture on it. Otherwise I’ll prepare some exercises for you to work on either individually or in groups. So during discussion we won’t necessarily be talking about the homework exercises. We should talk about homework exercises during office hours, where I can more easily address individual questions. Here are the exercises from discussion:
One Two Three Four Five Six Seven Eight Nine
Speaking of which, I am in charge of grading your homework. Homework accounts for 15% of your grade in this course. You will be assigned some exercises out of the notes each week, and, at Dr Diaz’s suggestion, to maintain my sanity while grading your homework I will look over and grade your solutions to just two of those exercises. I will post solutions and feedback on your responses to those exercises on this webpage below. Click on an exercise to read my solution to it. And for individual feedback on your homework, and for feedback on the exercises I didn’t chose to grade, please come see me in office hours.
I graded problems two and four for this week’s homework.
Notice that $4$ divides both $48$ and $156$, so $4$ divides $48x-156y$. But $4$ does not divide $66$, so no integers $x$ and $y$ exist that satisfy the equation.
Some students noticed that $6$ divides both the left-hand side and the right-hand side of that equation, but then claimed that this means that there does exist integer solutions $x$ and $y$ to the equation. This doesn’t make sense. If you claim that there is a solution $x$ and $y$, this should make you pause and consider “what are the solutions $x$ and $y$?” The easiest way to prove that solutions $x$ and $y$ exist would be to simply find them, but the fact that this response doesn’t construct the solutions should cause you a moment’s thought that this response is incorrect. In fact, there are no integer solutions to this equation.
And the other exercise from the homework:
Every integer $n$ can be written as one of $3k$, or $3k+1$, or $3k+2$ by the division algorithm. The squares of these expressions for $n$, written suggestively, are \begin{equation*} 3\left(3k^2\right) \qquad 3\left(3k^2 +2k\right) +1 \qquad 3\left(3k^2 +4k + 1\right) +1 \end{equation*} respectively, and none of them are of the form $3k+2$ for an integer $k$.
Alternatively, one could think of it this way: Working modulo $3$, every integer $n$ is congruent to either $0$, $1$, or $2$, and the squares of these, modulo $3$, are $0$, $1$, and $1$ respectively. So $n^2$ cannot be of the form $3k+2$ because it cannot be congruent to $2$ modulo $3$.
My main criticism of students’ responses to this question was that there was often insufficient explanation for the calculations that needed to be done. Like, many students wrote a table containing the squares of $3k$ and $3k+1$ and $3k+2$, and then wrote down a conclusion, but didn't explain where the table came from, or why the calculations of the table were sufficient to make that conclusion. Just a short explanation would do.
I have few over-arching comments I have to say regarding this homework. Instead, I’ll write up my own version of the various solutions to each problem I saw to give an indication of quality of writing that I expect. First, question four from the homework.
Suppose that $d$ divides both $x$ and $y$. Then for some integers $w$ and $z$ we have $dw = x$ and $dz = y$, and $d^2\left(4w^2 -3z^2\right) = 1$. Then $d^2|1$, so $d = \pm 1$. But if the only numbers that divides both $x$ and $y$ are $\pm 1$, the $x$ and $y$ must be relatively prime.
Or, this is a much cleaner solution: Notice that the original equation can be written as \begin{equation*} 4x(x) - 3y(y) = 1\,. \end{equation*} This is a linear combination of $x$ and $y$ that is equal to $1$, so $\mathrm{gcd}(x,y)|1$, which only happens if $\mathrm{gcd}(x,y)=1$, so $x$ and $y$ are relatively prime.
Now question five from the homework. The first two solutions are good, and which one is most elegant to use depends on how you initially define the greatest common divisor of two numbers $x$ and $y$; either as the minimal $d$ such that there exists $a$ and $b$ where $ax+by=d$, or as the result of performing the Euclidean algorithm on $x$ and $y$. The third solution though is less elegant than the first two since it relies a proposition that is (1) not obviously true, and (2) is really overkill considering the small amount of work required to answer the question without it.
One way to show this would be to notice that $1$ can be expressed as a linear combination of $n$ and $2n+1$ as \begin{equation*} -2(n) + 1(2n+1) = 1\,. \end{equation*} This means that $\mathrm{gcd}(n, 2n+1) | 1$, but only $\pm 1$ divide $1$, so $\mathrm{gcd}(n, 2n+1) = 1$.
Or an alternative solution: performing the Euclidean algorithm on $n$ and $2n+1$, \begin{align*} 2n+1 &= (2)n + (1) \\ n &= (n)1 + (0)\, \end{align*} which tells us that $\mathrm{gcd}(n, 2n+1) = 1$. so we’re done.
Or a third alternative: recall from a proposition from lecture that \begin{equation*} \mathrm{gcd}(a,b) = \mathrm{gcd}(a,b + ka) \end{equation*} for any $k \in \mathbf{Z}$. In our particular case then, \begin{equation*} \mathrm{gcd}(n,2n+1) = \mathrm{gcd}(n,2n+1+(-2n)) = \mathrm{gcd}(n,1) = 1\,. \end{equation*}
Each of the questions that I graded on this homework are kinda tough, but almost solely because they involve calculations that one must do very carefully.
It may take some time to notice, but we can see that $25$ is an inverse of $3$ modulo $37$ and $27$ is an inverse of $2$ modulo $53$. Multiplying each of the congruences by these inverses respectively, we get an equivalent system: \begin{cases} x \equiv 1 \pmod{37} \\ x \equiv 34 \pmod{53} \end{cases} The first of these congruences implies that there exists some $t \in \mathbf{Z}$ such that $x = 37t +1$. Plugging this into the second congruence we get that $37t \equiv 33 \pmod{53}$. Working methodically through the integers we can find that $43$ is an inverse to $37$ modulo $53$ (one might sooner see that $37 \times 10 \equiv -1 \pmod{53}$, and then conclude that an inverse of $37$ must be $53-10$). Multiplying by this inverse, we get that $t \equiv 41 \pmod{53}$, which means that there exists some $s \in \mathbf{Z}$ such that $t = 53s + 41$. Substituting this back into our expression for $x$ in terms of $t$, we see that $x$ can be $1961s+1518$ for any $s \in \mathbf{Z}$. In other words, $x \equiv 1518 \pmod{1961}$.
First, we perform the Euclidean algorithm: \begin{align*} (345118) &= 51(6753) + 715 \\(6753) &= 9(715) + 318 \\(715) &= 2(318) + 79 \\(318) &= 4(79) + 2 \\(79) &= 39(2) + 1 \quad (\star) \\(39) &= 39(1) + 0 \end{align*} This confirms that $\mathrm{gcd}(345118,6753) = 1$. Next, to find the complete solution set to $6753x + 345118y = 1$, starting with the line $(\star)$ where that $1$ is the greatest common divisor, we want to “back propagate” through the Euclidean algorithm and for the divisor on each line (right-most number in parenthesis) substitute in for the remainder (right-most number) on the previous line: \begin{align*} -39(2) &+ 1(79) = 1 \\-39(318) &+ 157(79) = 1 \\-353(318) &+ 157(715) = 1 \\-353(6753) &+ 3334(715) = 1 \\-170387(6753) &+ 3334(345118) = 1 \end{align*}
So $(x,y) = (-170387,3334)$ is a solution to the equation, but we must notice that the pair $(-170387 + 345118n, 3334 - 6753n)$ will also be a solution for any $n \in \mathbf{Z}$.
These exercises were calculations that I just graded on completion, so I did not post solutions.
Since this last homework was optional and I talked about these solutions in discussion, I didn’t put any feedback here.
There are effectively four cases to work through for $p$ congruent to $1$ or $-1$ or $5$ or $-5$ modulo $12$. Suppose first that $p \equiv 5 \pmod{12}$, so $p = 12k+5$ for some $k \in \mathbf{Z}$. Using the law of quadratic reciprocity, and the facts that $12k+5 \equiv 2 \pmod{3}$ and that $2$ is not a square modulo $3$, we have \begin{align*} \left(\frac{3}{p}\right) \left(\frac{p}{3}\right) &= (-1)^{\frac{1}{4}(p-1)(3-1)} \\ \left(\frac{3}{p}\right) \left(\frac{12k+5}{3}\right) &= (-1)^{\frac{1}{4}\left((12k+5)-1\right)(2)} \\ \left(\frac{3}{p}\right) \left(\frac{2}{3}\right) &= (-1)^{\frac{1}{2}(12k+4)} \\ \left(\frac{3}{p}\right) \left(-1\right) &= 1 \,. \end{align*} and so $\left(\frac{3}{p}\right)$ must equal $-1$, as we were told it should. Verifying the other three cases where $p$ is congruent to $1$ or $-1$ or $-5$ modulo $12$ is done similarly.
Recall that if $a$ and $b$ are relatively prime, then $\varphi(ab) = \varphi(a)\varphi(b)$. So in the case that $n$ is odd we have $\varphi(2n) = \varphi(2)\varphi(n) = 1 \varphi(n) = \varphi(n)$. Otherwise suppose $n$ is even and so $n = 2^km$ for $m$ odd and $k \gt 0$. So long as $n \gt 1$, we have \begin{equation*} \varphi(p^n) = p^{n-1}(p-1) = p p^{n-2}(p-1) = p\varphi(p^{n-1}) \,. \end{equation*} In particular, \begin{equation*} \varphi(2n) = \varphi(2^{k+1}m) = \varphi(2^{k+1})\varphi(m) = 2\varphi(2^k)\varphi(m) = 2\varphi(2^km) = 2\varphi(n) \,. \end{equation*}