Let $d=12$. For each of the following four values of $a$, find $q,r\in\mathbb{Z}$ such that $a=qd+r$ and $0\leqslant r<d$ (as in Theorem 4.1.8):

1. (i)

   Use the Euclidean algorithm to find the highest common factor of $90$ and $66$, and express it as an integral linear combination of $90$ and $66$.

2. (ii)

   For each of the two numbers $54$ and $56$, either write it as an integral linear combination of $90$ and $66$ or explain why this is impossible, using Proposition 4.4.2.

Apply the Self-Explanation strategy from Appendix C to the proof of Bézout’s Theorem (Theorem 4.2.17).

Prove the following two statements about integers $m$ and $n$:

1. (i)

   if $m$ and $n$ are both even, then $m^{2}+n^{2}$ is even;

2. (ii)

   if $mn$ is even, then at least one of $m$ and $n$ is even. [Hint: contraposition.]

Let $a$, $b$ and $c$ be non-zero integers. Prove that if $c$ is a factor of $ab$, then $c$ is also a factor of $\mathrm{hcf}(a,c)\cdot b$. [Hint: use Theorem 4.2.17.]

Show that, for each real number $x$, at least one of $\sqrt{2}+x$ and $\sqrt{2}-x$ is irrational. [Hint: proof by contradiction — what would follow if both were rational? Recall from Example 3.4.2 that $\sqrt{2}$ is irrational.]

1. (i)

   Find the sets of factors of $36$ and $48$.

2. (ii)

   Using (i), determine the set of common factors of $36$ and $48$, and hence find their highest common factor.

3. (iii)

   For each of the numbers $-28$, $-24$, $276$ and $284$, decide whether or not it can be written as an integral linear combination of $36$ and $48$.

Use the Euclidean algorithm to find the highest common factor of $190$ and $266$, and express it as an integral linear combination of $190$ and $266$.

For integers $m$ and $n$, prove that the integer $m^{2}n+mn^{2}$ is always even. [Hint: consider cases separately.]

Show that one of the following two statements is true, whereas the other is false:

1. (i)

   $(\forall m\in\mathbb{Z})(\exists\,n\in\mathbb{Z})(m-n=5);$

2. (ii)

   $(\exists\,m\in\mathbb{Z})(\forall n\in\mathbb{Z})(m-n=5).$

Apply the Self-Explanation strategy from Appendix C to the proof that $\sqrt{2}$ is irrational (Example 3.4.2) and to the proof of the Division-with-Remainder Theorem (Theorem 4.1.8).

Let $a$, $b$ and $c$ be non-zero integers, and suppose that $a$ and $c$ are coprime and that $b$ and $c$ are coprime. Show that $ab$ and $c$ are coprime. [Hint: use Corollary 4.2.19.]

Let $a$, $b$ and $c$ be non-zero integers. Prove that if $a$ and $b$ are coprime and $c$ is a factor of $a$, then $c$ and $b$ are coprime. [Hint: use Corollary 4.2.19.]

List the sets of factors of $72$ and $175$, and hence find the set of their common factors and their highest common factor.

For integers $m$ and $n$, prove that the integer $m^{2}+mn+n^{2}$ is even if and only if $m$ and $n$ are both even.

(6 points) For each of the following two statements, decide whether it is true or false, and justify your answer by giving a proof or a counterexample, as appropriate:

• $p:$

  $(\forall m\in\mathbb{N})(\forall n\in\mathbb{N})(\exists\,k\in\mathbb{N})(kn>m);$

• $q:$

  $(\forall r\in\mathbb{Q})(\forall s\in\mathbb{Q})\Bigl((r>s)\Rightarrow\bigl((\exists\,n\in\mathbb{Z})(r\geqslant n\geqslant s)\bigr)\Bigr)$.

(4 points) For non-zero integers $a$, $m$ and $n$, prove that if $a$ is a factor of $mn$, then $a$ is also a factor of $\mathrm{hcf}(a,m)\cdot\mathrm{hcf}(a,n)$. [Hint: use Theorem 4.2.17.]

(Division with remainder) Let $d=17$. For $a=137$, find $q,r\in\mathbb{Z}$ such that $a=qd+r$ with $0\leqslant r<d$ (as in Theorem 4.1.8). Moreover, for $b=-137$, find $s,t\in\mathbb{Z}$ such that $b=sd+t$ with $0\leqslant t<d$. Then choose the correct answer from the following list:

1. (A)

   $q=7$ and $r=18$; $s=-9$ and $t=16$;

2. (B)

   $q=7$ and $r=18$; $s=-8$ and $t=-1$;

3. (C)

   $q=8$ and $r=1$; $s=-9$ and $t=16$;

4. (D)

   $q=8$ and $r=1$; $s=-8$ and $t=-1$;

5. (E)

   none of the above.

Use the Euclidean algorithm to find the highest common factor $d$ of $2222$ and $611$, and then reverse the steps of the algorithm to find integers $r$ and $s$ such that $d=2222r+611s$. Then answer the following two questions.

1. (i)

   (The highest common factor $d$) The value of $d$ is:

   1. (A)

      $d=-1;$

   2. (B)

      $d=1;$

   3. (C)

      $d=3;$

   4. (D)

      $d=7;$

   5. (E)

      none of the above.

2. (ii)

   (The integers $r$ and $s$) The values of $r$ and $s$ found by this method are:

   1. (A)

      $r=-900$ and $s=3273;$

   2. (B)

      $r=900$ and $s=-3273;$

   3. (C)

      $r=-2100$ and $s=7637;$

   4. (D)

      $r=2100$ and $s=-7637;$

   5. (E)

      none of the above.

(Integral linear combinations and the highest common factor) Find the highest common factor of $24$ and $42$, and then decide which one of the following five statements is true:

1. (A)

   each of the numbers $30$, $32$ and $34$ can be written as an integral linear combination of $24$ and $42$;

2. (B)

   none of the numbers $30$, $32$ and $34$ can be written as an integral linear combination of $24$ and $42$;

3. (C)

   the number $30$ can be written as an integral linear combination of $24$ and $42$, whereas $32$ and $34$ cannot be written as integral linear combinations of $24$ and $42$;

4. (D)

   the number $32$ can be written as an integral linear combination of $24$ and $42$, whereas $30$ and $34$ cannot be written as integral linear combinations of $24$ and $42$;

5. (E)

   the number $34$ can be written as an integral linear combination of $24$ and $42$, whereas $30$ and $32$ cannot be written as integral linear combinations of $24$ and $42$.

(Correctness of a proof) Four students, Alice, Bob, Claire and Dave, have each attempted to prove that the following statement is false.

‘‘Let $a\in\mathbb{Z}$ be a multiple of $12$, and let $b\in\mathbb{Z}$ be a multiple of $18$. Then $180$ is an integral linear combination of $a$ and $b$, but $96$ is not an integral linear combination of $a$ and $b$.’’

Their answers are as follows:

Alice:

We have $\mathrm{hcf}(12,18)=6$ and $\mathrm{hcf}(180,96)=12$. Since $6\neq 12$, the statement is false.

Bob:

The statement is false because $\mathrm{hcf}(12,18)=6$, which divides both $180$ and $96$, so both numbers are integral linear combinations of $a$ and $b$ by Proposition 4.4.2.

Claire:

The statement is false because $a=72$ is a multiple of $12$, and $b=72$ is a multiple of $18$, but since $72\!\!\!\!\;\not\!\!\!\;|\!\;180$, we cannot write $180$ as an integral linear combination of $a$ and $b$.

Dave:

We begin by negating the statement:

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

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

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

To prove that this is true, we choose $a=8$, which is not a multiple of $12$, and $b=16$, which is not a multiple of $18$. Then $\mathrm{hcf}(a,b)=8$, which divides $96$, but not $180$, so Proposition 4.4.2 shows that $96$ is an integral linear combination of $a$ and $b$, but $180$ is not. This shows that the negation is true, so the original statement is false.

Decide which one of the following five statements about these answers is true:

1. (A)

   only one student gave a correct answer;

2. (B)

   Alice’s and Bob’s solutions are the only correct ones;

3. (C)

   Claire’s and Dave’s solutions are the only correct ones;

4. (D)

   only one student gave an incorrect answer;

5. (E)

   none of the above.

(3 points) Let $a$ and $b$ be non-zero integers. Prove that if $a$ and $b$ are coprime, then $ab$ and $a+b$ are also coprime. [Hint: Exercise 2.12 may be helpful.]