Homework 6 was due on Thursday 6th March 2014. I graded Q2,3,5 and the grader graded Q1,4,6. All questions are marked out of 5.

**Question 1.** The errors on this question were almost exclusively arithmetical errors and citation errors; namely, people either weren't adding numbers up correctly, or they were citing the wrong theorems. Arithmetical errors are easily fixed: check your answer at the end, and if the numbers work out then your solution is likely to be correct. For the citation errors, much of this came from the fact that people weren't writing their answers as if they're proofs... but really they are! You're proving that the solutions to an equation form a particular set. Just like in other questions, you need to link together your sentences with words, implication arrows ($\Rightarrow$), and so on, and you need to cite results whenever they're used.

**Question 2.** The most common errors in this question arose because people were abusing their quantifiers. *All* the mathematics you do from now on is as much 'logic' as the stuff you were doing in the first part of the course was. So when you write something like: $$c \mid a\ \Rightarrow\ qc = a,\ q \in \mathbb{Z}$$ you're not quantifying properly, which is *baaad* and could lead to a loss of marks in an exam. Really you should write $$c \mid a\ \Rightarrow\ qc = a\ \text{for some}\ q \in \mathbb{Z}$$ or $$c \mid a\ \Rightarrow\ \exists q \in \mathbb{Z}.\ qc = a$$ Another common error was people writing $ax+by=\mathrm{gcd}(a,b)$ without introducing $x$ and $y$. Again, it's very important that you're saying that "*there exist* $x,y \in \mathbb{Z}$ such that ...". Frequently people ended up accidentally (and incorrectly) saying that $d \mid c$, largely because of these quantification errors.

**Question 3.** Q3 suffered from quantification errors similar to Q2. By far the most common omission, made by the majority of people, was failing to prove that $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime. This is a hypothesis of Theorem 7, so it needs to be mentioned, and it doesn't follow from the definition of $\mathrm{gcd}$, so it requires proof.

**Question 4.** The problems with this question were identical to the problems with Question 1.

**Question 5.** There were some rather sketchy answers to this question, but there were lots of different errors and no extremely common ones. Some details were left out, e.g. a lot of people assumed that $q \ge 1$ without proving it (and sometimes without even mentioning it), so that's one thing to look out for.

**Question 6.** Most people had the correct idea of proving that $\sqrt{p}$ is irrational for prime $p$ by assuming it's rational and deriving a contradiction. This is good. The idea of the intended proof was: assume $\sqrt{p} = \frac{a}{b}$ with $a,b \in \mathbb{Z}$ cancelled as far as possible (i.e. $\mathrm{gcd}(a,b) = 1$), and show that this implies that $p \mid a$ and $p \mid b$, contradicting 'cancelled as far as possible'. The most common error was forgetting to specify that the fraction be in reduced form, otherwise you don't get the desired contradiction. The key step was going from $p \mid a^2$ to $p \mid a$ (and the same for $b$): this follows immediately from Lemma 14 (the 'atomic property' of primes), but many people forgot to cite this. There were multiple alternative solutions to this problem, some of which were correct and some of which were not.