E.9 Tutor-assessed exercises from week 2

Exercise 2.16. Statement $p$ is true because, for any $m,n\in\mathbb{N}$, let $k=m+1\in\mathbb{N}$. Then, as $n\geqslant 1$, we have $kn\geqslant k=m+1>m$, as required.

Statement $q$ is false as the following counterexample shows. Let $r=2/3\in\mathbb{Q}$ and $s=1/3\in\mathbb{Q}$. Then $r>s$, but there is no integer $n$ such that $r\geqslant n\geqslant s$. (Many other counterexamples exist, of course.)

Exercise 2.17. Suppose that $a$ is a factor of $mn$. Then we can take $t\in{\mathbb{Z}}$ such that $mn=ta$. Theorem 4.2.17 implies that there are $p,q,r,s\in{\mathbb{Z}}$ such that $\mathrm{hcf}(a,m)=pa+qm$ and $\mathrm{hcf}(a,n)=ra+sn$, and hence we have

so that $a$ is a factor of $\mathrm{hcf}(a,m)\cdot\mathrm{hcf}(a,n)$.

Bonus exercise 2.22. Suppose that $\mathrm{hcf}(a,b)=1$, and let $d=\mathrm{hcf}(a,a+b)$. Then $d$ is a factor of $a$ and of $a+b$, and therefore $d$ is also a factor of $(a+b)+(-1)a=b$ by Lemma 4.2.13. Hence $d$ is a positive common factor of $a$ and $b$, so as $\mathrm{hcf}(a,b)=1$, we must have $d=1$, that is, $\mathrm{hcf}(a,a+b)=1$. Similarly we see that $\mathrm{hcf}(b,a+b)=1$. By Exercise 2.12, this implies that $\mathrm{hcf}(ab,a+b)=1$.

Alternative proof, using material from Section 4.6. Suppose contrapositively that $a+b$ and $ab$ are not coprime. Then, by the Fundamental Theorem of Arithmetic, they have a common prime factor; that is, we can find a prime number $p$ which divides both $a+b$ and $ab$. The latter condition implies that $p$ divides $a$ or $b$ by Proposition 4.6.2. If $p$ divides $a$, it also divides $(a+b)-a=b$ by Lemma 4.2.13, whereas if $p$ divides $b$, it also divides $(a+b)-b=a$. Hence in both cases $p$ is a common factor of $a$ and $b$, which are therefore not coprime.