E.6 Online-assessed exercises from week 2

Exercise 2.18.$137=8\cdot 17+1$, so as $0\leqslant 1<17$, we have $q=8$ and $r=1$. Moreover, $-137=(-9)17+16$, where $0\leqslant 16<17$, so that $s=-9$ and $t=16$. Thus (C) is correct.

Exercise 2.19. The Euclidean algorithm gives

Thus $\mathrm{hcf}(2222,611)=1=1091\cdot 611-300\cdot 2222$, and therefore the correct answers are (i): (B) and (ii): (E).

Exercise 2.20. We find $6=2\cdot 24+(-1)42$, and $6$ divides both $24\,(=4\cdot 6)$ and $42\,(=7\cdot 6)$, so Corollary 4.2.15 implies that $\mathrm{hcf}(24,42)=6$. (If one does not see that $6=2\cdot 24+(-1)42$ straightaway, a more systematic approach is also possible, using the Euclidean algorithm.)

Proposition 4.4.2 states that an integer $n$ is an integral linear combination of $24$ and $42$ if and only if $6|n$. Hence we have:

• •

  $30$ is an integral linear combination of $24$ and $42$ because $6|30$;

• •

  $32$ and $34$ cannot be written as integral linear combinations of $24$ and $42$ because $6\!\!\!\!\;\not\!\!\!\;|\!\;32$ and $6\!\!\!\!\;\not\!\!\!\;|\!\;34$.

Therefore (C) is the correct answer.

Exercise 2.21. We find:

• •

  Alice’s answer is not correct; we have no theorem supporting her reasoning.

• •

  Bob’s answer is also not correct; his argument shows that $180$ and $96$ can both be written as linear combinations of $12$ and $18$, but that was not the question!

• •

  Claire’s answer, giving a counterexample to the statement, is correct.

• •

  Dave’s answer is not correct because his negation of the statement is wrong. The correct negation is:

  ‘‘There exist $a,b\in\mathbb{Z}$, where $a$ is a multiple of $12$ and $b$ is a

  multiple of $18$, such that $180$ is not an integral linear combination

  of $a$ and $b$, or $96$ is an integral linear combination of $a$ and $b$.’’

Hence (A) is the correct answer.