E.3 Workshop exercises from week 3

Exercise 3.1. By Theorem 4.5.5,

Exercise 3.2.

1. (i)

   The remainder on dividing $237$ by $54$ is $237-4\cdot 54=21$, so Proposition 5.1.5(ii) shows that $n=21$ is the smallest positive integer such that $n\equiv 237\bmod 54$.

2. (ii)

   The remainder on dividing $2391$ by $142$ is $119$ (because $2391=16\cdot 142+119$), so Proposition 5.1.5(ii) implies that $119$ is the smallest positive integer congruent to $2391$ modulo $142$. Thus the largest negative integer congruent to $2391$ modulo $142$ is $119-142=-23$.

Exercise 3.3.

1. (i)

   We use the Euclidean algorithm:

   	$\displaystyle 237$	$\displaystyle=5\cdot 45+12$	$\displaystyle\qquad\text{and}\qquad 3$	$\displaystyle=12-9$
   	$\displaystyle 45$	$\displaystyle=3\cdot 12+9$		$\displaystyle=12-(45-3\cdot 12)=4\cdot 12-45$
   	$\displaystyle 12$	$\displaystyle=9+3$		$\displaystyle=4(237-5\cdot 45)-45=4\cdot 237-21\cdot 45.$
   	$\displaystyle 9$	$\displaystyle=3\cdot 3$

   Thus $\mathrm{hcf}(237,45)=3=4\cdot 237-21\cdot 45$, and Theorem 4.5.5 shows that

   $$\mathrm{lcm}(237,45)=\frac{237\cdot 45}{3}=3555.$$

2. (ii)
   1. (a)

      Solutions exist by Theorem 5.2.2 because $\mathrm{hcf}(45,237)=3$ divides $54$.
      Lemma 5.2.8 enables us to simplify the congruence by dividing by $3$:

      $$(45x\equiv 54\bmod 237)\ \Leftrightarrow\ \biggl(\frac{45}{3}x\equiv\frac{54}{3}\bmod\frac{237}{3}\biggr)\ \Leftrightarrow\ (15x\equiv 18\bmod 79).$$

      Moreover, dividing by $3$ in the identity $3=4\cdot 237-21\cdot 45$ from (i), we obtain

      $$1=4\cdot 79-21\cdot 15.\tag{$*$}$$

      In particular, $15$ and $79$ are coprime, and Theorem 5.2.6 shows the complete solution is given by

      $$x\equiv 18(-21)=-378=(-5)\cdot 79+17\equiv 17\bmod 79.$$

   2. (b)

      $\mathrm{hcf}(45,54)=9$ (because $9|45$ and $9|54$ and $9=(-1)\cdot 45+54$, or by prime factorization), and $9\!\!\!\!\;\not\!\!\!\;|\!\;237$, so no solutions exist to this congruence.

   3. (c)

      Since $\mathrm{hcf}(237,45)=3$ divides $54$, solutions exist. We simplify the congruence by dividing by $3$:

      $$(237x\equiv 54\bmod 45)\ \Leftrightarrow\ \biggl(\frac{237}{3}x\equiv\frac{54}{3}\bmod\frac{45}{3}\biggr)\ \Leftrightarrow\ (79x\equiv 18\bmod 15).$$

      Since $79$ and $15$ are coprime, Theorem 5.2.6 and (a) imply that the complete solution is given by

      $$x\equiv 4\cdot 18=72=4\cdot 15+12\equiv 12\bmod 15.$$

Exercise 3.5. By Proposition 5.3.5, if simultaneous solutions exist, $\mathrm{hcf}(1176,363)=3$ must divide $36-50=-14$. As $3$ does not divide $-14$, no simultaneous solutions exist.

Exercise 3.6.

1. (i)

   A bit of experimentation shows that $1=5\cdot 5-2\cdot 12$, and thus $5$ and $12$ are coprime. (Alternatively, use the Euclidean algorithm.)

2. (ii)

   The Chinese Remainder Theorem (Theorem 5.3.2) applies because $5$ and $12$ are coprime by (i). In the notation used in Theorem 5.3.2, we have $a=3$, $b=9$, $m=5$, $n=12$, $r=5$ and $s=-2$, so that $asn+brm=3\cdot(-2)\cdot 12+9\cdot 5\cdot 5=153$ and $mn=5\cdot 12=60$, and the complete solution is given by $x\equiv 153\bmod 60$. Since $153=2\cdot 60+33$, we can simplify this answer to $x\equiv 33\bmod 60$.

Exercise 3.7.

1. (i)

   $1176=2^{3}\cdot 3\cdot 7^{2}$ and $363=3\cdot 11^{2}$, where $2$, $3$, $7$ and $11$ are prime numbers (as we showed using the Sieve of Eratosthenes in Section 4.6).

2. (ii)

   Proposition 4.7.10 and the prime factorizations found in (i) imply that

   $$\mathrm{hcf}(1176,363)=2^{0}\cdot 3\cdot 7^{0}\cdot 11^{0}=3\ \ \text{and}\ \ \mathrm{lcm}(1176,363)=2^{3}\cdot 3\cdot 7^{2}\cdot 11^{2}=142\,296.$$

3. (iii)

   Combining Corollary 4.7.5 with the prime factorizations found in (i), we see that $1176$ has $(3+1)\cdot(1+1)\cdot(2+1)=24$ positive factors, while $363$ has $(1+1)\cdot(2+1)=6$ positive factors.

Exercise 3.8. If $x$ denotes the number of pupils, then $x$ is a simultaneous solution to the two congruences $x\equiv 6\bmod 8$ and $x\equiv 4\bmod 11$; further, we know that $0<x<100$. We find $1=3\cdot 11-4\cdot 8$ by experimentation (or the Euclidean algorithm), so that $8$ and $11$ are coprime, and the Chinese Remainder Theorem applies. The complete solution is given by

As $70-88<0$ and $70+88>100$, we conclude that the number of pupils is $70$.

Exercise 3.9. First note that if $n$ is a number in the grid and is not prime, then $n=ab$ where $1<a\leqslant b<n$; then $a^{2}\leqslant ab=n\leqslant 10\,000$, so $a\leqslant 100$. Thus every number in the grid which is not prime has a factor less than $100$, and thus in particular a prime factor less than $100$. It is therefore only necessary to go through crossing out multiples of $p$ if $p\leqslant 100$. As we have seen in Section 4.6 of the lecture notes, there are $25$ such primes, so it is necessary to go through the grid $25$ times.

Exercise 3.10.

1. (i)

   We have $\mathrm{hcf}(14,35)=7$ (either by prime factorization or by the facts that $7|14$, $7|35$ and $7=35-2\cdot 14$). As $7\!\!\!\!\;\not\!\!\!\;|\!\;27$, Theorem 5.2.2 implies that the congruence has no solutions.

2. (ii)

   Since $1=13-2\cdot 6$, we have $\mathrm{hcf}(6,13)=1$, so solutions exist, and Theorem 5.2.6 implies that the complete solution is given by

   $$x\equiv 5(-2)=-10\equiv 3\bmod 13.$$

3. (iii)

   We have $\mathrm{hcf}(15,21)=3$ (using prime factorization) and $3|12$, so solutions exist. Lemma 5.2.8 enables us to simplify the congruence; we have $15x\equiv 12\bmod 21$ if and only if $5x\equiv 4\bmod 7$. Now $5$ and $7$ are coprime, and we have $1=3\cdot 5-2\cdot 7$, so Theorem 5.2.6 shows that the complete solution to the congruence is given by

   $$x\equiv 3\cdot 4=12\equiv 5\bmod 7.$$

4. (iv)

   As $\mathrm{hcf}(12,45)=3$ (by prime factorization) and $3|30$, solutions exist. Again we apply Lemma 5.2.8 to simplify; we have $12x\equiv 30\bmod 45$ if and only if $4x\equiv 10\bmod 15$. Now $\mathrm{hcf}(4,15)=1=4\cdot 4-15$, and the complete solution is therefore given by

   $$x\equiv 4\cdot 10=40\equiv 10\bmod 15.$$

Exercise 3.11. In the notation of The Chinese Remainder Theorem (Theorem 5.3.2), we have $a=36$, $b=48$, $m=217$ and $n=247$. We apply the Euclidean algorithm to show that $m$ and $n$ are coprime (so that Theorem 5.3.2 applies) and to write $1=rm+sn$:

Hence $r=107$ and $s=-94$. Now

is a simultaneous solution to the two congruences, and the complete solution is given by $x\equiv c\bmod mn$, that is, $x\equiv 278664\bmod 53599$.

Division with remainder shows that $278664=5\cdot 53599+10669$, so the answer can (and should) be simplified to $x\equiv 10669\bmod 53599$.

Exercise 3.13. All primes other than $2$ are odd, and thus are of the form either $4n+1$ or $4n+3$ for some $n\in{\mathbb{N}}_{0}$. Suppose that there are only finitely many primes of the form $4n+3$, say $p_{1},p_{2},\dots,p_{k}$, where $k\in{\mathbb{N}}$, and let $N=4p_{1}p_{2}\cdots p_{k}-1$. Then no $p_{j}$ divides $N$ (as $N$ is of the form $rp_{j}-1$), and $2\!\!\!\!\;\not\!\!\!\;|\!\;N$ (as $N$ is odd); thus if $N=q_{1}q_{2}\cdots q_{m}$ is the prime factorization of $N$, then each $q_{j}$ must be of the form $4n+1$, say $q_{j}=4n_{j}+1$, where $n_{1},\ldots,n_{m}\in\mathbb{N}$. However, the product $q_{1}q_{2}\cdots q_{m}$ is then also of the form $4n+1$ because

for some $n\in\mathbb{N}$, whereas $N=4(p_{1}p_{2}\cdots p_{k}-1)+3$. This contradiction proves that there must be infinitely many primes of the form $4n+3$.

Note: the last part of the argument can be elegantly written using congruence notation; indeed, we have

whereas

so we cannot have $N=q_{1}q_{2}\cdots q_{m}$.

Exercise 3.14.

1. (i)

   The result is obvious for $n=1$. For $n\geqslant 2$, write $n={p_{1}}^{a_{1}}{p_{2}}^{a_{2}}\cdots{p_{r}}^{a_{r}}$, where $r\in\mathbb{N}$, $p_{1},p_{2},\ldots,p_{r}$ are distinct prime numbers, and $a_{1},a_{2},\ldots,a_{r}\in\mathbb{N}$. Corollary 4.7.5 implies that $n$ has $(a_{1}+1)(a_{2}+1)\cdots(a_{r}+1)$ positive factors. If any of the terms $a_{j}+1$ is even, then this product is even, and vice versa, so we conclude that the number of positive factors of $n$ is odd if and only if $a_{j}+1$ is odd for each $j\in\{1,2,\ldots,r\}$. Now $a_{j}+1$ is odd precisely when $a_{j}$ is even, say $a_{j}=2b_{j}$ for some $b_{j}\in\mathbb{N}$. Thus the number of factors of $n$ is odd if and only if

   $$n={p_{1}}^{2b_{1}}{p_{2}}^{2b_{2}}\cdots{p_{r}}^{2b_{r}}=({p_{1}}^{b_{1}}{p_{2}}^{b_{2}}\cdots{p_{r}}^{b_{r}})^{2},$$

   i.e., $n$ is a square.

2. (ii)

   If we pair together numbers $a,b$ with $n=ab$, this groups the factors of $n$ into pairs — the only possible exception is if $a=b$, in which case $n=a^{2}$. Thus if $n$ is a perfect square, the factors comprise various pairs with $\sqrt{n}$ left over, so the number of factors is odd; if $n$ is not a perfect square, the factors can be paired off with none left over, so the number of factors is even.