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

**Question 1.** Most people who correctly identified that $\mathrm{lcm}(a,b)$ can be obtained by raising the prime factors of $a$ and $b$ to the maximum of their exponents got this question correct. A fairly prevalent error was people assuming that $\max \{ \alpha_i, \beta_i \} = \alpha_i$ for all $i$. Certainly, if we fix a value of $i$ then this is something we can assume without loss of generality because otherwise we can just swap $a$ and $b$ around; but which one is the max varies with $i$. Consider $2^2 \cdot 3$ and $2 \cdot 3^2$, for example.

There were a number of alternative solutions using various facts about divisibility. Some of these were correct, but most weren't, and tried to hide their incorrectness in a long and convoluted argument that ultimately didn't make sense. The moral of the story is: if you're given a hint in a question, try to use it!

**Questions 2-4.** These were quick questions that tested your ability to do modular arithmetic. Most people did fine. There was some dodgy reasoning about raising numbers to large powers, e.g. people said that the powers of $7$ cycled through $7,9,3,1$ modulo $10$ and 'the pattern continues'... sure, but you need to make this precise. A better idea is to use Proposition 19 (plus some hidden induction) to get that if $a \equiv b \pmod m$ then $a^k \equiv b^k \pmod m$ for all $k \in \mathbb{N}$.

**Question 5.** Most people who followed the proof of Theorem 21 did this correctly. People occasionally set the problem up correctly by introducting 'alternation' too early, i.e. writing the number as an alternating sum of powers of 10... but this isn't how decimal representations work. The alternating sum appears when you reduce modulo $11$ and use the fact that $10 \equiv -1 \pmod {11}$.

**Question 6.** The key with this question was to assume that $a$ and $b$ are both odd and derive a contradiction. The appropriate contradiction is that, in this case, if $a^2+b^2=c^2$ then $4 \mid c^2$ but $4 \not \mid a^2+b^2$. This could be done in a number of ways, the slickest of which was to reduce modulo 4, but there were plenty of other possibilities. There was some dodgy reasoning about square roots... as a general rule, when doing stuff in the number theory section of the course and reasoning about integers, avoid talking about square roots. One example was people deriving a 'contradiction' by saying $c^2 \equiv 2 \pmod 4$ and so $c \equiv \sqrt{2} \pmod 4$, which contradicts $c \in \mathbb{Z}$. This is invalid reasoning because the notion of 'square root modulo 4' is different from 'square root in $\mathbb{R}$'. For example, $\sqrt{3} \not \in \mathbb{Z}$ and yet $4^2 \equiv 3 \pmod{13}$... no contradiction!

This square rooting error leads is an example of a more general problem you might encounter with congruences: it's an example of where $\equiv$ *doesn't* behave like equality. With numbers under equality we can add, subtract, divide, multiply, take inverses, take square roots (and so on), and everything remains valid; under congruence we can only add, subtract and multiply. (This extends to exponentiation.) Anything else could cause things to go horribly wrong.