E.4 Workshop exercises from week 4

Exercise 4.1. We have $527=500+27\equiv 27=4\cdot 6+3\equiv 3\bmod 4$, so Corollary 6.3.7 implies that $527$ cannot be written as the sum of two squares.

Exercise 4.2.

1. (i)

   $2^{4}=16\equiv-1\bmod 17$, so $2^{16}=(2^{4})^{4}\equiv(-1)^{4}=1\bmod 17$.

2. (ii)

   $7^{2}=49\equiv-3\bmod 13$, so $7^{4}=(7^{2})^{2}\equiv(-3)^{2}=9\equiv-4\bmod 13$, and thus

   $$7^{12}=(7^{4})^{3}\equiv(-4)^{3}=-64\equiv 1\bmod 13.$$

Exercise 4.3.

1. (i)
   1. (a)

      Not reflexive, e.g., $2\not\sim 2$ because $2\cdot 2=4\neq 1$.

   2. (b)

      Symmetric: if $ab=1$ then $ba=1$.

   3. (c)

      Transitive: if $ab=1=bc$ then $a=b=c=\pm 1$ so $ac=1$.

2. (ii)
   1. (a)

      Not reflexive, e.g., $1\not\sim 1$ because $2\cdot 1=2>1$.

   2. (b)

      Not symmetric, e.g., $1\sim 3$ (because $2\cdot 1=2<3$), but $3\not\sim 1$ (because $2\cdot 3=6>1$).

   3. (c)

      Transitive: if $a\sim b$ and $b\sim c$, then $2a\leqslant b$ and $2b\leqslant c$, and thus $2a\leqslant b\leqslant 2b\leqslant c$, so that $a\sim c$.

Exercise 4.5. We have $4\equiv-1\bmod 5$ and $6\equiv 1\bmod 5$, and thus

$$4^{2n+1}+6^{2n+1}\equiv(-1)^{2n+1}+1^{2n+1}=-1+1=0\bmod 5,$$

so that $5|(4^{2n+1}+6^{2n+1})$ for each $n\in{\mathbb{N}}$.

Exercise 4.6. Given $\widehat{(a,b)}$, $\widehat{(c,d)}$ and $\widehat{(e,f)}$, we have

$$\widehat{(a,b)}\bigl(\widehat{(c,d)}+\widehat{(e,f)}\bigr)=\widehat{(a,b)}\widehat{(cf+de,df)}=\widehat{(acf+ade,bdf)}$$

and

$$\widehat{(a,b)}\widehat{(c,d)}+\widehat{(a,b)}\widehat{(e,f)}=\ \widehat{(ac,bd)}+\widehat{(ae,bf)}=\widehat{(acbf+bdae,b^{2}df)}.$$

Since

$$(acf+ade)b^{2}df=ab^{2}cdf^{2}+ab^{2}d^{2}ef=bdf(acbf+bdae),$$

the two equivalence classes are equal as required.

Exercise 4.7.

1. (i)

   $\widehat{1}=\{1\}$, $\widehat{2}=\{1,2\}$, $\widehat{3}=\{1,3\}$, $\widehat{4}=\{1,2,4\}$, $\widehat{5}=\{1,5\}$, $\widehat{6}=\{1,2,3,6\}$.

2. (ii)

   The sets $\widehat{b}$ do not form a partition of $S$ — all the sets are distinct, but no two of them are disjoint.

3. (iii)

   By (ii), $\sim$ cannot be an equivalence relation (see Proposition 6.2.3(iii)); this can also be seen directly: $\sim$ is reflexive and transitive, but not symmetric (e.g., $1\sim 2$ (because $1|2$), but $2\not\sim 1$ (because $2\!\!\!\!\;\not\!\!\!\;|\!\;1$)).

Exercise 4.8.

$$\begin{array}[]{|c|cccccc|}\hline+&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}\\ \hline\widehat{0}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}\\ \widehat{1}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}&\widehat{0}\\ \widehat{2}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}&\widehat{0}&\widehat{1}\\ \widehat{3}&\widehat{3}&\widehat{4}&\widehat{5}&\widehat{0}&\widehat{1}&\widehat{2}\\ \widehat{4}&\widehat{4}&\widehat{5}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \widehat{5}&\widehat{5}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}\\ \hline\end{array}\qquad\qquad\begin{array}[]{|c|cccccc|}\hline\times&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}\\ \hline\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}\\ \widehat{1}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{5}\\ \widehat{2}&\widehat{0}&\widehat{2}&\widehat{4}&\widehat{0}&\widehat{2}&\widehat{4}\\ \widehat{3}&\widehat{0}&\widehat{3}&\widehat{0}&\widehat{3}&\widehat{0}&\widehat{3}\\ \widehat{4}&\widehat{0}&\widehat{4}&\widehat{2}&\widehat{0}&\widehat{4}&\widehat{2}\\ \widehat{5}&\widehat{0}&\widehat{5}&\widehat{4}&\widehat{3}&\widehat{2}&\widehat{1}\\ \hline\end{array}$$

As $x$ runs through the elements of ${\mathbb{Z}}_{6}$, $\widehat{4}\,x$ runs through the row of the multiplication table headed $\widehat{4}$; as there is no entry $\widehat{5}$ in this row, there is no $x\in{\mathbb{Z}}_{6}$ satisfying $\widehat{4}\,x=\widehat{5}$.

Exercise 4.10.

1. (i)

   The multiplication table above shows that $\widehat{2}$, $\widehat{3}$ and $\widehat{4}$ are zero divisors in ${\mathbb{Z}}_{6}$ because $2,3,4\in\{1,2,3,4,5\}$ and $\widehat{2}\cdot\widehat{3}=\widehat{0}=\widehat{3}\cdot\widehat{4}$. There are no other zero divisors because the table shows that $\widehat{1}\cdot\widehat{k}\neq\widehat{0}$ and $\widehat{5}\cdot\widehat{k}\neq\widehat{0}$ for each $k\in\{1,2,3,4,5\}$.

2. (ii)

   Similarly, the multiplication table for ${\mathbb{Z}}_{5}$ in the notes shows that there are no zero divisors in ${\mathbb{Z}}_{5}$ because $\widehat{n}\cdot\widehat{k}\neq 0$ for $n,k\in\{1,2,3,4\}$.

Exercise 4.11. For each $a\in{\mathbb{N}}$, $aa=a^{2}$ is a square, so $a\sim a$, and $\sim$ is reflexive.

If $a\sim b$, then $ab$ is a square; thus $ba=ab$ is also a square, so $b\sim a$, and therefore $\sim$ is symmetric.

If $a\sim b$ and $b\sim c$, then $ab$ and $bc$ are squares, say $ab=m^{2}$ and $bc=n^{2}$ for some $m,n\in{\mathbb{N}}$; then

$$ac=\frac{m^{2}}{b}\cdot\frac{n^{2}}{b}=\frac{m^{2}n^{2}}{b^{2}}=\biggl(\frac{mn}{b}\biggr)^{2},$$

and as $ac\in{\mathbb{N}}$, Exercise 3.22(ii) implies that $mn/b\in{\mathbb{N}}$, so that $ac$ is a square, and hence $a\sim c$. This prove that $\sim$ is transitive, and therefore $\sim$ is an equivalence relation.

Exercise 4.12. The argument assumes that for each $a\in S$ there is an element $b\in S$ with $a\sim b$ — but this may fail as in Exercise 4.3(i) above where no $n\in{\mathbb{Z}}$ with $2\sim n$ exists.

Exercise 4.13. The squares modulo $10$ are

	$\displaystyle 0^{2}=0$	$\displaystyle\equiv 0\bmod 10,$	$\displaystyle 1^{2}=1$	$\displaystyle\equiv 1\bmod 10,$	$\displaystyle 2^{2}=4$	$\displaystyle\equiv 4\bmod 10,$
	$\displaystyle 3^{2}=9$	$\displaystyle\equiv 9\bmod 10,$	$\displaystyle 4^{2}=16$	$\displaystyle\equiv 6\bmod 10,$	$\displaystyle 5^{2}=25$	$\displaystyle\equiv 5\bmod 10,$
	$\displaystyle 6^{2}=36$	$\displaystyle\equiv 6\bmod 10,$	$\displaystyle 7^{2}=49$	$\displaystyle\equiv 9\bmod 10,$	$\displaystyle 8^{2}=64$	$\displaystyle\equiv 4\bmod 10,$
			$\displaystyle 9^{2}=81$	$\displaystyle\equiv 1\bmod 10.$

Since the numbers $2$, $3$, $7$ and $8$ do not appear on any of the right-hand sides, we conclude that no square is congruent to $2$, $3$, $7$ or $8$ modulo $10$. This proves the result because each natural number is congruent to its final digit modulo $10$.

Exercise 4.14. We have $3^{2}=9\equiv-2\bmod 11$, and thus

$$3^{10}=(3^{2})^{5}\equiv(-2)^{5}=-32\equiv 1\bmod 11.$$

Hence the remainder on dividing $3^{10}$ by $11$ is $1$.

Exercise 4.15. Let $n\in\mathbb{N}$. We have $5^{2}=25\equiv 4\bmod 7$ and $4^{3}=64\equiv 1\bmod 7$. It follows that

$$5^{6}=(5^{2})^{3}\equiv 4^{3}\equiv 1\bmod 7,$$

and thus

$$5^{6n+1}=(5^{6})^{n}\cdot 5\equiv 1^{n}\cdot 5=5\bmod 7.$$

Further, we have

$$4^{3n+2}=(4^{3})^{n}\cdot 4^{2}\equiv 1^{n}\cdot 16\equiv 2\bmod 7.$$

In conclusion,

$$5^{6n+1}+4^{3n+2}\equiv 5+2\equiv 0\bmod 7,$$

and therefore $7$ divides $5^{6n+1}+4^{3n+2}$ for each $n\in{\mathbb{N}}$.