E.10 Tutor-assessed exercises from week 3

Exercise 3.15.

1. (i)

   By experimentation, we see that $(-7)9+2\cdot 32=1$, so that $9$ and $32$ are coprime. (Alternatively, use the Euclidean algorithm.) Hence solutions exist by Theorem 5.2.2, and the complete solution is given by

   $$x\equiv(-7)17=-119=(-4)32+9\equiv 9\bmod 32.$$

   [As a check, we verify that $x=9$ satisfies the congruence:

   $$9\cdot 9=81=2\cdot 32+17\equiv 17\bmod 32.]$$

2. (ii)

   We use the Euclidean algorithm to determine $\mathrm{hcf}(70,119)$:

   $$\begin{array}[]{rlrl}119&\!\!\!=1\cdot 70+49&7=&49-2\cdot 21\\ 70&\!\!\!=1\cdot 49+21&=&49-2(70-49)\\ 49&\!\!\!=2\cdot 21+7&=&3\cdot 49-2\cdot 70\\ 21&\!\!\!=3\cdot 7+0&=&3(119-70)-2\cdot 70\\ \hbox{so }\mathrm{hcf}(70,119)&\!\!\!=7;&=&3\cdot 119-5\cdot 70.\end{array}$$

   Since $7|42$, solutions exist by Theorem 5.2.2. Lemma 5.2.8 enables us to simplify the congruence by dividing by $7$:

   $$(70x\equiv 42\bmod 119)\ \Leftrightarrow\ \biggl(\frac{70}{7}x\equiv\frac{42}{7}\bmod\frac{119}{7}\biggr)\ \Leftrightarrow\ (10x\equiv 6\bmod 17).$$

   Moreover, dividing by $7$ in the identity $7=3\cdot 119-5\cdot 70$ found above, we obtain $1=3\cdot 17-5\cdot 10$, and the complete solution is given by

   $$x\equiv(-5)\cdot 6=-30=(-2)\cdot 17+4\equiv 4\bmod 17.$$

   [As a check, we verify that $x=4$ satisfies the original congruence:

   $$70\cdot 4=280=2\cdot 119+42\equiv 42\bmod 119.]$$

Exercise 3.16. Let $x$ denote the number of first-year maths students. Then $x$ is a simultaneous solution to the two congruences $x\equiv 7\bmod 15$ and $x\equiv 13\bmod 28$, and also $0<x<500$. We apply the Euclidean algorithm to find the highest common factor of $15$ and $28$ and express it as an integral linear combination of them:

Thus $15$ and $28$ are coprime, so that the Chinese Remainder Theorem applies. We have $a=7$, $b=13$, $m=15$, $n=28$, $r=-13$ and $s=7$, and the complete solution to the pair of congruences is given by

Since $15\cdot 28=420$ and $-1163=(-3)420+97$, we can rewrite this as $x\equiv 97\bmod 420$. Now $97-420<0$ and $97+420>500$, so we conclude that there are $x=97$ students.

Bonus exercise 3.22.

1. (i)

   Write $a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}$ and $b=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots p_{r}^{b_{r}}$, where $p_{1}<p_{2}<\cdots<p_{r}$ are prime numbers and $a_{1},\ldots,a_{r},b_{1},\ldots,b_{r}\in{\mathbb{N}}_{0}$. Then we have $a^{2}=p_{1}^{2a_{1}}p_{2}^{2a_{2}}\cdots p_{r}^{2a_{r}}$ and $b^{2}=p_{1}^{2b_{1}}p_{2}^{2b_{2}}\cdots p_{r}^{2b_{r}}$. Since $b^{2}|a^{2}$, we must have $2b_{j}\leqslant 2a_{j}$ for each $j\in\{1,\ldots,r\}$; thus $b_{j}\leqslant a_{j}$ for each $j\in\{1,\ldots,r\}$, and so $b|a$ as required.

2. (ii)

   Let $n\in\mathbb{N}$. We seek to prove that either $\sqrt{n}\in\mathbb{N}$ or $\sqrt{n}\notin\mathbb{Q}$. Now if $\sqrt{n}\notin\mathbb{Q}$, this is clearly satisfied, so suppose that $\sqrt{n}\in\mathbb{Q}$, say $\sqrt{n}=a/b$, where $a,b\in{\mathbb{N}}$. Squaring this identity, we obtain $n=a^{2}/b^{2}$, so that $a^{2}=nb^{2}$ and therefore $b^{2}|a^{2}$. By (i), this implies that $b|a$, and therefore $\sqrt{n}=a/b\in\mathbb{N}$.

Bonus exercise 3.23. We begin by reducing each of the congruences to the form $x\equiv a\bmod m$ (if possible), using the techniques from Section 5.2.

• •

  $140x\equiv 70\bmod 294$: We find the prime factorizations $140=2^{2}\cdot 5\cdot 7$ and $294=2\cdot 3\cdot 7^{2}$, so that $\mathrm{hcf}(140,294)=2\cdot 7=14$ which divides $70$. Hence solutions exist, and we can simplify the congruence by dividing it by $14$, giving $10x\equiv 5\bmod 21$. Now $\mathrm{hcf}(10,21)=1=(-2)10+21$, so that the complete solution is given by

  $$x\equiv 5(-2)=-10\equiv 11\bmod 21.$$

• •

  $65x\equiv 35\bmod 160$: We find the prime factorizations $65=5\cdot 13$ and $160=2^{5}\cdot 5$, so that $\mathrm{hcf}(65,160)=5$ which divides $35$. Hence solutions exist, and we can simplify the congruence by dividing it by $5$, giving $13x\equiv 7\bmod 32$. Now $\mathrm{hcf}(13,32)=1=5\cdot 13-2\cdot 32$, so that the complete solution is given by

  $$x\equiv 7\cdot 5=35\equiv 3\bmod 32.$$

We have thus shown that $x$ satisfies $140x\equiv 70\bmod 294$ and $65x\equiv 35\bmod 160$ if and only if

Since $\mathrm{hcf}(21,32)=1=(-3)21+2\cdot 32$, the Chinese Remainder Theorem applies, giving the complete solution