Explain why the number $527$ cannot be written as the sum of two squares.

Find (i) $2^{16}\bmod 17$ and (ii) $7^{12}\bmod 13$ without actually calculating $2^{16}$ or $7^{12}$ (or any other numbers greater than $100$).

For each of the following two relations, decide if it is (a) reflexive,
(b) symmetric and (c) transitive:

1. (i)

   $S=\mathbb{Z}$, and $a\sim b$ if $ab=1$;

2. (ii)

   $S=\{x\in\mathbb{R}:x\geqslant 0\}$, and $a\sim b$ if $2a\leqslant b$.

In each case give a proof or a counterexample as appropriate.

Apply the Self-Explanation strategy from Appendix C to the proof of Lemma 6.3.2.

Show that $5$ divides $4^{2n+1}+6^{2n+1}$ for each $n\in\mathbb{N}$.

In the construction of $\mathbb{Q}$ from $\mathbb{Z}$ given in Section 6.4 of the lecture notes, show that for all $\widehat{(a,b)}$, $\widehat{(c,d)}$ and $\widehat{(e,f)}$ (where $a,b,c,d,e,f\in\mathbb{Z}$ with $b,d,f\neq 0$) we have

(This rule is called the distributive law.)

On the set $S=\{1,2,3,4,5,6\}$, define a relation $\sim$ by stipulating that $a\sim b$ if $a|b$ (where $a,b\in S$). For each $b\in S$, let $\widehat{b}=\{a\in S:a\sim b\}$.

1. (i)

   Find the set $\widehat{b}$ explicitly for each element $b\in S$.

2. (ii)

   Do the sets $\widehat{b}$ form a partition of $S$?

3. (iii)

   Is $\sim$ an equivalence relation?

Give the addition and multiplication tables in $\mathbb{Z}_{6}$. From the second of these, decide if the equation $\widehat{4}x=\widehat{5}$ has a solution in $\mathbb{Z}_{6}$, and justify your answer.

Apply the Self-Explanation strategy from Appendix C to the proof of the Chinese Remainder Theorem (Theorem 5.3.2) and to the construction of the integers from the natural numbers as it was carried out in Section 6.4.

Let $m\in\{2,3,4,\ldots\}$, and let $n\in\{1,2,3,\ldots,m-1\}$. We say that $\widehat{n}$ is a zero divisor in $\mathbb{Z}_{m}$ if $\widehat{n}\cdot\widehat{k}=\widehat{0}$ for some $k\in\{1,2,3,\ldots,m-1\}$.

1. (i)

   Use the multiplication table found in Exercise 4.8 to find the zero divisors in $\mathbb{Z}_{6}$.

2. (ii)

   Use the similar table in the notes to find the zero divisors in $\mathbb{Z}_{5}$.

Define a relation $\sim$ on the set $\mathbb{N}$ by

Show that $\sim$ is an equivalence relation.

[Hint: The result stated in Exercise 3.22(ii) may be useful.]

What is wrong with the following argument to show that any relation $\sim$ which is both symmetric and transitive must also be reflexive?

From $a\sim b$ we deduce that $b\sim a$ as $\sim$ is symmetric, and then we have $a\sim a$ as $\sim$ is transitive — so $\sim$ is reflexive.

[Hint: it may help to consider one of the relations in Exercise 4.3 above.]

Show that no number ending in $2$, $3$, $7$ or $8$ can be a perfect square.

Find the remainder on dividing $3^{10}$ by $11$ without actually calculating $3^{10}$ (or any other numbers greater than $100$).

Show that $7$ divides $5^{6n+1}+4^{3n+2}$ for each $n\in\mathbb{N}$.
[Hint: begin by considering $5^{2}$ and $4^{3}$ modulo $7$.]

(5 points) On the set $\mathbb{N}$, define a relation $\sim$ by stipulating that $a\sim b$ if $\mathrm{hcf}(a,b)=1$ (where $a,b\in\mathbb{N}$). Decide whether this relation is (a) reflexive, (b) symmetric and (c) transitive, in each case giving either a proof or a counterexample, as appropriate.

(1 point) Explain why the number $9283$ cannot be written as the sum of two squares, giving clear reference to any results that you use.

(4 points) Show that $63$ divides $8^{2n}+5^{6n-3}$ for each $n\in\mathbb{N}$.

(A relation) On the set of all real functions, define a relation $\sim$ by stipulating that $f\sim g$ if $f(0)\leqslant g(0)$ (where $f$ and $g$ are real functions). Decide which one of the following five statements is true:

1. (A)

   the relation $\sim$ is reflexive, but not symmetric or transitive;

2. (B)

   the relation $\sim$ is reflexive and symmetric, but not transitive;

3. (C)

   the relation $\sim$ is reflexive and transitive, but not symmetric;

4. (D)

   the relation $\sim$ is symmetric, but not reflexive or transitive;

5. (E)

   none of the above.

(The remainder $r$ on dividing $3^{154}$ by $24$) Find the remainder $r$ on dividing $3^{154}$ by $24$ without actually calculating $3^{154}$ (or any other numbers greater than $100$), and then decide which one of the following five statements is true:

1. (A)

   $r=0;$

2. (B)

   $r=3;$

3. (C)

   $r=9;$

4. (D)

   $r=15;$

5. (E)

   none of the above.

(The remainder $s$ on dividing $5^{202}$ by $7$) Find the remainder $s$ on dividing $5^{202}$ by $7$ without actually calculating $5^{202}$ (or any other numbers greater than $100$), and then decide which one of the following five statements is true:

1. (A)

   $s=1;$

2. (B)

   $s=2;$

3. (C)

   $s=3;$

4. (D)

   $s=5;$

5. (E)

   none of the above.

(Polynomial division) Suppose that we divide a polynomial $f(X)$ of degree $6$ by a polynomial $g(X)$ of degree $3$ using polynomial division with remainder (Theorem 7.1.10) to obtain a quotient $q(X)$ and a remainder $r(X)$. Suppose further that $r(X)\neq 0$, and then decide which one of the following five statements is true:

1. (A)

   $q(X)$ has degree $2$, and $r(X)$ has degree at most $1$;

2. (B)

   $q(X)$ has degree $2$, and $r(X)$ may have degree $2$;

3. (C)

   $q(X)$ has degree $3$, and $r(X)$ has degree at most $2$;

4. (D)

   $q(X)$ has degree $3$, and $r(X)$ may have degree $3$;

5. (E)

   none of the above.

(A polynomial relation) Ann, Bill, Chris, Dan and Ed use the exam paper from 2015 to revise for the MATH111 end-of-module test. However, they cannot agree on the correct answer to Question 4(a), which reads as follows:

Let $P$ denote the set of real polynomials, and let $P^{*}=P\setminus\{0\}$, so that $P^{*}$ is the set of non-zero real polynomials. Define a relation $\sim$ on $P\times P^{*}$ by stipulating that

(where $f(X),g(X),h(X),k(X)$ are polynomials and $g(X),k(X)\neq 0$). Decide whether

and whether

Ann says that both statements hold, Bill that only the first one holds, Chris that only the second one holds, Dan that neither holds, and Ed that the question does not make sense — there must be a typo in the exam paper because we do not have enough information to answer the question. Who is right?

(A) Ann,   (B) Bill,   (C) Chris,   (D) Dan,   (E) Ed.

(3 points) Let $m\in\{2,3,4,\ldots\}$, and let $n\in\{1,2,3,\ldots,m-1\}$. Recall from Exercise 4.10 that $\widehat{n}$ is a zero divisor in $\mathbb{Z}_{m}$ if $\widehat{n}\cdot\widehat{k}=\widehat{0}$ for some $k\in\{1,2,3,\ldots,m-1\}$. Prove that $\widehat{n}$ is a zero divisor in $\mathbb{Z}_{m}$ if and only if $\mathrm{hcf}(n,m)\geqslant 2$.