E.2 Workshop exercises from week 2

Exercise 2.1.

Exercise 2.2.

1. (i)

   
   

   $$\begin{array}[]{rlrl}90&\!\!\!=66+24&6=&24-18\\ 66&\!\!\!=2\cdot 24+18&=&24-(66-2\cdot 24)\\ 24&\!\!\!=18+6&=&3\cdot 24-66\\ 18&\!\!\!=3\cdot 6+0&=&3(90-66)-66\\ &&=&3\cdot 90-4\cdot 66.\end{array}$$

   Thus $\mathrm{hcf}(90,66)=6=3\cdot 90-4\cdot 66$.

2. (ii)

   Proposition 4.4.2 states that an integer $n$ can be written as an integral linear combination of $90$ and $66$ if and only if $\mathrm{hcf}(90,66)$ is a factor of $n$. Since $\mathrm{hcf}(90,66)=6$ and $6|54$ and $6\!\!\!\!\;\not\!\!\!\;|\!\;56$, we conclude that $54$ can be written as an integral linear combination of $90$ and $66$, whereas $56$ cannot. We have

   $$54=9\cdot 6=9(3\cdot 90-4\cdot 66)=27\cdot 90-36\cdot 66.$$

Exercise 2.4.

1. (i)

   Suppose that $m$ and $n$ are both even, so that $m=2a$ and $n=2b$ for some integers $a$ and $b$; then $m^{2}+n^{2}=(2a)^{2}+(2b)^{2}=4a^{2}+4b^{2}=2(2a^{2}+2b^{2})$, so $m^{2}+n^{2}$ is even.

2. (ii)

   The contrapositive of the statement ‘‘($mn$ is even) $\Rightarrow$ ($m$ or $n$ is even)’’ is ‘‘($m$ and $n$ are odd) $\Rightarrow$ ($mn$ is odd)’’ which is true. Indeed, let $m=2a+1$ and $n=2b+1$ for some integers $a$ and $b$; then $mn=2(2ab+a+b)+1$ is odd.
   Alternatively, this can be proved by separate consideration of cases.

Exercise 2.5. Suppose that $c|ab$. Then there exists $q\in{\mathbb{Z}}$ such that $ab=qc$. Theorem 4.2.17 implies that $\mathrm{hcf}(a,c)=ra+sc$ for some $r,s\in{\mathbb{Z}}$, and hence we have

so that $c|\mathrm{hcf}(a,c)\cdot b$.

Exercise 2.6. Assume that the result is false; that is, there exists a real number $x$ such that $\sqrt{2}+x$ and $\sqrt{2}-x$ are both rational. Then $2\sqrt{2}=(\sqrt{2}+x)+(\sqrt{2}-x)$ is the sum of two rational numbers, hence is rational, and therefore $\sqrt{2}=\frac{1}{2}(2\sqrt{2})$ is also rational. This, however, contradicts Example 3.4.2, so one of $\sqrt{2}+x$ and $\sqrt{2}-x$ is irrational.

Exercise 2.7.

1. (i)

   The set of factors of $36$ is

   $$S=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 9,\pm 12\pm 18,\pm 36\},$$

   while the set of factors of $48$ is

   $$T=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 8,\pm 12,\pm 16,\pm 24,\pm 48\}.$$

2. (ii)

   By (i), the set of common factors of $36$ and $48$ is

   $$S\cap T=\{\pm 1,\pm 2,\pm 3,\pm 4,\pm 6,\pm 12\},$$

   and thus $\mathrm{hcf}(36,48)=12$.

3. (iii)

   We have $12\!\!\!\!\;\not\!\!\!\;|\!\;(-28)$, $12|(-24)$, $12|276$ and $12\!\!\!\!\;\not\!\!\!\;|\!\;284$, so Proposition 4.4.2 implies that $-24$ and $276$ can be written as integral linear combinations of $36$ and $48$, whereas $-28$ and $284$ cannot.

Exercise 2.8.

Thus $\mathrm{hcf}(190,266)=38=3\cdot 190-2\cdot 266$.

Exercise 2.9. If at least one of $m$ and $n$ is even, then $m^{2}n$ and $mn^{2}$ are both even by Example 3.2.4, and so $m^{2}n+mn^{2}$ is even as well. Otherwise $m$ and $n$ are both odd; then $m^{2}n$ and $mn^{2}$ are both odd, and so $m^{2}n+mn^{2}$ is even.

Exercise 2.10. Statement (i) is true: for each $m\in\mathbb{Z}$, we can find $n\in\mathbb{Z}$ such that $m-n=5$; simply take $n=m-5$.

On the other hand, statement (ii) is false: there is no $m\in\mathbb{Z}$ that will work for all $n\in\mathbb{Z}$; indeed, if $m$ were an integer such that $m-n=5$ for all $n\in\mathbb{Z}$, then in particular by taking $n=m$, we would get $5=m-n=m-m=0$ which is clearly absurd. Hence the statement is false.

Exercise 2.12. By Theorem 4.2.17 we can find $p,q,r,s\in\mathbb{Z}$ such that $pa+qc=1$ and $rb+sc=1$. Then

and so $\mathrm{hcf}(ab,c)=1$ by Corollary 4.2.19.

Exercise 2.13. Suppose that $\mathrm{hcf}(a,b)=1$ and $c|a$. Then there are $r,s,t\in{\mathbb{Z}}$ such that $ra+sb=1$ (by Theorem 4.2.17) and $a=tc$. Thus we have

so Corollary 4.2.19 implies that $\mathrm{hcf}(c,b)=1$.

Exercise 2.14. The set of factors of $72$ is

The set of factors of $175$ is

Thus the set of common factors of $72$ and $175$ is $S\cap T=\{\pm 1\}$, and $\mathrm{hcf}(72,175)=1$.

Exercise 2.15.$\Leftarrow$. Suppose that $m$ and $n$ are both even. Then $m^{2}$, $mn$ and $n^{2}$ are all even by Example 3.2.4, and therefore $m^{2}+mn+n^{2}$ is also even.

$\Rightarrow$. We prove this implication by contraposition. The contrapositive of the statement ‘‘($m^{2}+mn+n^{2}$ is even) $\Rightarrow$ ($m$ and $n$ are even)’’ is ‘‘($m$ or $n$ is odd) $\Rightarrow$ ($m^{2}+mn+n^{2}$ is odd)’’. We consider the possible cases for $m$ and $n$:

• •

  If $m$ is odd and $n$ is even, then $m^{2}$ is odd whereas $mn$ and $n^{2}$ are even, so $m^{2}+mn+n^{2}$ is odd.
  

• •

  Similarly, if $m$ is even and $n$ is odd, then $m^{2}+mn+n^{2}$ is odd.
  

• •

  Finally, if $m$ and $n$ are both odd, then $m^{2},mn$ and $n^{2}$ are all odd, so $m^{2}+mn+n^{2}$ is odd.
  

Thus $m^{2}+mn+n^{2}$ is odd in all three cases.

The following parity table summarizes this argument.