Solutions to Exercises

Chapter 1

Exercise 1.7.

Solution. This is covered in one of the Worksheets.

Exercise 1.8.

Solution. Recall that the truth table for $P\Leftrightarrow Q$ is given by \[ \begin{array}{c|c|c} P&Q&P\Leftrightarrow Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&T \end{array} \] If $P\equiv Q$ then $P$ and $Q$ are either both TRUE or both FALSE. We see then that $P\Leftrightarrow Q$ is TRUE and hence a tautology.

Conversely, if $P\Leftrightarrow Q$ is a tautology, then $P$ and $Q$ are either both TRUE or both FALSE and so $P\equiv Q$.

Exercise 1.19.

Solution. \[ 1 + 3 + \ldots + (2n-1) = n^2. \] We use induction on $n$. For $n=1$ the results is trivially true as $1 = 1^2$. Suppose then that it is true for some value $n\ge 1$ and consider \[ 1 + 3 + \ldots + (2n-1) + (2n+1). \] By our inductive assumption we know that $1 + 3 + \ldots + (2n-1) = n^2$ and so \[ 1 + 3 + \ldots + (2n-1) + (2n+1) = n^2 + 2n + 1 = (n+1)^2, \] and so the result follows by induction for all $n\ge1$.

Exercise 1.20.

Solution. Let $a\in\mathbb Z$. \[ (1+a)^n \ge 1+na \] We use induction on $n$. For $n=1$, $(1+a)^n = 1+a = 1+na$ and so the result is trivially true. Suppose now that the result is true for some $n\ge1$ and consider \[ (1+a)^{n+1} = (1+a)^n(1+a). \] By the inductive hypothesis, $(1+a)^n\ge 1+na$ and so \[ (1+a)^{n+1} = (1+a)^n(1+a)\ge (1+an)(1+a) = 1+a+an+a^2n\ge 1 + a(n+1), \] and the result is true for all $n\ge1$ by induction.

Chapter 2

Exercise 2.11

Solution. Let $a,b\in\mathbb Z$ with $b\ne0$. By the corollary to the Remainder Theorem, Corollary 2.10, there exists a unique pair of integers $q,r$ with \[ a = qb + r\text{ and } 0\le r<|b|. \] If $r$ is such that $r \le |b|/2$ then we can use these values. Otherwise it must be that $|b|/2 < r < |b|$. In this case, notice that if $b>0$ then \[ a = (q+1)b + (r-b) \] and that $-|b|/2 < r-b < 0\le |b|/2$, while if $b<0$ then \[ a = (q-1)b + (r+b) \] and $-|b|/2 =|b|/2-|b| = |b|/2+b< r+b<|b+b = 0\le|b|/2$. So in either case, there exists $q,r$ such that \[ a = qb + r, -|b|/2< r\le |b|/2. \] Suppose there exists $q',r'$ such that \[ a = q'b + r', -|b|/2< r'\le |b|/2. \] Then $qb+r = q'b+r'$ and so $(q-q')b = r'-r$ and $-|b|<r'-r<|b|$. It then follows that $r'-r = 0$ and so $r'=r$, from which we deduce that $q'=q$ as required.

Exercise 2.15

Solution. Proceeding as in Euclid’s algorithm but using Exercise 2.11 in place of the Remainder Theorem we get \[ \begin{array}{rclcr} a&=&q_1b+r_1&&-|b|/2< r_1\le |b|/2\\ b&=&q_2r_1+r_2&&-|r_1|/2< r_2\le |r_1|/2\\ r_1&=&q_3r_2+r_3&&-|r_2|/2< r_3\le |r_2|/2\\ &\ldots&\\ r_{i-1}&=&q_{i+1}r_i+r_{i+1}&&-|r_i|/2< r_{i+1}\le|r_i|/2\\ &\ldots&\\ r_{n-1}&=&q_{n+1}r_{n}+r_{n+1}&\qquad&-|r_n|/2< r_{n+1}\le|r_n|/2\\ r_n&=&q_{n+2}r_{n+1}+0.\\ \end{array} \] The proof that the algorithm halts and that $r_{n+1} = \gcd(a,b)$ is similar to that for Euclid’s algorithm.

Exercise 2.20

Solution. We use induction on $k$. For $k=2$ the result is obvious. Suppose then that it is true for some $k\ge2$ and consider $\gcd(a_1,\ldots,a_k, a_{k+1})$. Using the inductive hypothesis we see that

\[ \begin{array}{rl} \gcd(\ldots\gcd(\gcd(a_1,a_2), a_3), \ldots, a_{k+1}) &= \gcd(\gcd(\ldots\gcd(\gcd(a_1,a_2), a_3), \ldots, a_k),a_{k+1})\\ &= \gcd(\gcd(a_1,\ldots,a_k),a_{k+1}).\\ \end{array} \] Suppose then that $c|\gcd(a_1,\ldots,a_k)$ and $c|a_{k+1}$. Then $c|a_i$ for $1\le i\le k+1$. Conversely, if $c|a_1,\ldots,a_{k+1}$ then $c|\gcd(a_1,\ldots,a_k)$ and $c|a_{k+1}$. Therefore $\{a_1,\ldots,a_k\}$ and $\{\gcd(a_1,\ldots,a_k),a_{k+1}\}$ share common divisors and so have the same greatest common divisor.

Chapter 3

Exercise 3.5

Solution. \[\begin{gather*} 115 = 5\times23,\\188 = 2\times94 = 2^2\times47,\\ 2020 = 2\times1010 = 2^2\times505 = 2^2\times5\times101 \end{gather*}\]

Exercise 3.8

Solution. Notice that for $n\ge3, s_n>1$ and so by Theorem 3.3, $s_n$ has a prime divisor, $p$, say. If $p\le n$ then $p|n!$ and so $p|(n!-s_n)$ which is a contradiction. Hence $p>n$ and so there are arbitrarily large primes.

Chapter 4

Exercise 4.3

Solution. The last decimal digit is found by finding the remainder on division by 10. Let $n = a^2$ and use the Remainder theorem with $a$ and $10$ so that \[ a = 10q + r\text{ with }0\le r< 10. \] Then $n = a^2 = (10q+r)^2 = 100q^2 + 20qr + r^2$. But for $0\le r\le 9$ we have $r^2\in\{0,1,4,9,16,25,36,49,64,81\}$ and so the final digit can be either $0,1,4,5,6$ or $9$.

From above, if a perfect square has a final digit of $1$ then either $r=1$ or $r=9$. Notice then that $(n-1)/10$ is even whereas $(3190491-1)/10 = 319049$ is odd and so $3190491$ cannot be a perfect square.

Exercise 4.5

Solution. Since $(392-1) = 391 = 23\times17$ then $392\equiv1\text{ mod }(23)$.

Exercise 4.12

Solution. Axiom [A1] is obviously true by Lemma 4.11.

For axiom [A2], $[m]+[0] = [m+0] = [m] = [0+m] = [0]+[m]$ and $[m][1] = [m\times1] = [m] = [1\times m] = [1][m]$.

Since $[m] - [m] = [m-m] = [0]$ axiom [A3] holds.

For axiom [A4], $[m] = [n] = [m+n] = [n+m] = [n] + [m]$ and $[m][n] = [mn] = [nm] = [n][m]$.

Similarly, $([m]+[n])+[p] = [m+n] = [p] = [(m+n)+p] = [m+(n+p)] = [m] + ([n]+[p])$ and $([m][n])[p] = [(mn)p] = [m(np)] = [m]([n][p])$ and so axiom [A5] also holds.

For axiom [A6], m = [m][n+p] = [m(n+p)] = [mn+mp] = [mn]+[mp] = [m][n] + [m][p]$.

However, axiom [A7] may not hold. Forexample, if $n=6$ then $[2][3] = [6] = [0]$ but $[2]\ne[0]$ and $[3]\ne[0]$.

Exercise 4.16

Solution.

Working $\text{ mod }(23)$ we see that $31(33+35)\equiv 8(10+12)\equiv 8\times22\equiv8\times-1\equiv-8$.
Working $\text{ mod }(29)$ we have $31^{33}\equiv2^{33}=(2^5)^62^3\equiv3^6\times8\equiv(3^3)^2\times8\equiv(-2)^2\times8\equiv32\equiv3$.
Working $\text{ mod }10$ we see that $m!\equiv0$ for $m\ge5$ and so we need only consider 4 values of $n$, namely $n=1,2,3$ and $4$. We then have $1!=1, 1!+2! = 3, 1!+2!+3! = 9, 1!+2!+3!+4! = 33$. Hence the final decimal digit can only be either $1,3$ or $9$.

Exercise 4.22

Solution.

Let $f(x) = x^2-x+1$. Working $\text{ mod }(2)$ we have that $f(0)\equiv1, f(1)\equiv1$ and so the plynomial has no integer roots.
Let $f(x) = x^3+x^2-x+1$. Working $\text{ mod }(3)$ we have $f(0)\equiv1, f(1)\equiv2, f(-1)\equiv2$ and so the polynomial has no integer roots.
Let $f(x)=x^3+x^2-x+3$. Working $\text{ mod }(5)$ we see that $f(0)\equiv3, f(1)\equiv4, f(2)\equiv3, f(-2)\equiv1, f(-1)\equiv4$ and so the polynomial has no integer roots.

Exercise 4.24

Solution. Suppose that $f(x)$ is prime for all integers $x$, and is not constant. If we choose any integer $a$, then $f(a)$ is a prime $p$. For each $b\equiv a$ $\text{mod}~(p)$, Lemma 4.20 implies that $f(b)\equiv f(a)$ $\text{mod}~(p)$, so $f(b)\equiv 0$ $\text{mod}~(p)$ and hence $p$ divides $f(b)$. By our hypothesis, $f(b)$ is prime, so $f(b)=p$. There are infinitely many integers $b\equiv a$ $\text{mod}~(p)$, so the polynomial $g(x)=f(x)-p$ has infinitely many roots. However, this is impossible: having degree $d\geq 1$, $g(x)$ can have at most $d$ roots, so such a polynomial $f(x)$ cannot exist.

Exercise 4.28

Solution. Working $\text{ mod }(15)$ we have $12x\equiv9\text{ mod }(15)$ becomes $-3x\equiv9\text{ mod }(15)$ and so $-x\equiv3\text{ mod }5$. hence $x\equiv-3\equiv2\text{ mod }5$.

Exercise 4.32

Solution. Notice that $4\times2\equiv4\times0\text{ mod }8$ but $2\not\equiv0\text{ mod }8$.

Exercise 4.38

Solution. Let $x = 3 + 5t$ for $t\in\mathbb Z$. Then $3+5t\equiv1\text{ mod }4$ and so $t\equiv-2\equiv2\text{ mod }4$. Hence $t = 2 + 4s$ for $s\in\mathbb Z$ and so $x = 3+5(2+4s) = 13+20s$. Now $13+20s\equiv 2\text{ mod }3$ and so $-s\equiv1\text{ mod }3$. Hence $s = 2 + 3r$ for $r\in\mathbb Z$ and so $x= 13+20(2+3r) = 53+60r$.

Exercise 4.39

Solution. Let $x=7+9t$ for $t\in\mathbb Z$. Then $7+9t\equiv2\text{ mod }7$ and so $2t\equiv2\text{ mod }7$ or $t\equiv1\text{ mod }7$. Hence $t=1+7s$ for $s\in\mathbb Z$ and so $x=7+9(1+7s) = 16+63s$. Now $16+63s\equiv4\text{ mod }4$ and so $-s\equiv0\text{ mod }4$. Hence $s = 4r$ for $r\in\mathbb Z$ and so $x = 16+63(4r) = 16+252r$.

Exercise 4.41

Solution. We first solve the three given congruences (using our 4-point algorithm) to $x\equiv2\text{ mod }4$, $x\equiv6\text{ mod }7$ and $x\equiv2\text{ mod }5$.

Now let $x=6+7t$ for $t\in\mathbb Z$ so that $6+7t\equiv2\text{ mod }5$. Hence $2t\equiv1\text{ mod }5$ which means $t\equiv3\text{ mod }5$ or $t=3+5s$, for $s\in\mathbb Z$, and so $x = 6+7(3+5s) = 27+35s$. Hence $27+35s\equiv2\text{ mod }4$ and so $-s\equiv3\text{ mod }4$ or $s\equiv1\text{ mod }4$. Therefore $s = 1 + 4r$ and hence $x = 27+35(1+4r) = 62+140r$.

Exercise 4.43

Solution. Since $440 = 2^3\times 5\times 11$ we can replace the single congruence with the three congruences \[ 91x\equiv 419\text{ mod }8, 91x\equiv 419\text{ mod }5, 91x\equiv 419\text{ mod }11. \] These simplify to \[ 3x\equiv3\text{ mod }8, x\equiv4\text{ mod }5, 3x\equiv 1\text{ mod }11. \] Solving these individually gives \[ x\equiv1\text{ mod }8, x\equiv4\text{ mod }5, x\equiv4\text{ mod }11. \] Let $x=4+11t$ for $t\in\mathbb Z$ so that $4+11t\equiv1\text{ mod }8$. Then $3t\equiv-3\text{ mod }8$ and hence $t\equiv-1\equiv7\text{ mod }8$. Therefore $t = 7+8s$ and $x=4+11(7+8s) = 81+88s$. Now $81+88s\equiv4\text{ mod }5$ and so $3s\equiv3\text{ mod }5$ or $s\equiv1\text{ mod }5$. Hence $s = 1+5r$ for $r\in\mathbb Z$ and so $x=81+88(1+5r) = 169+440r$.

Chapter 5

Exercise 5.2

Solution. Taking primes $p=2,3,5,7,11,13,17$ and looking at each residue class we see that there are roots as follows: \[ \begin{array}{r|l} p&\text{roots}\\\hline 2&1\\ 3&\\ 5&2\text{ and }3\\ 7&\\ 11&\\ 13&5\text{ and }8\\ 17&4\text{ and }13\\ \end{array} \]

Exercise 5.8

Solution. Since $23$ is prime and since $\text{gcd}(3,23)=1$, we see by Fermat’s Little theorem that $3^{22}\equiv1\text{ mod }23$. Hence $3^{91} = (3^{22})^43^3\equiv1^43^3=27\equiv4\text{ mod }(23)$

Exercise 5.11

Solution. First of all notice that by Euclid’s theorem \[ \gcd(29!+29,30!+29) = \gcd(29!+29,30!+29-(29!+29)) = \gcd(29!+29,30!-29!). \] Notice now that $29|(29!+29)$ and $29|(30!-29!)$ and so $\gcd(29!+29,30!-29!) = 29\gcd(28!+1,29!)$ using Corollary 2.24. By Wilson’s theorem $28!+1\equiv0\text{ mod }29$ and so $29|28!+1$. Hence $\gcd(29!+29,30!+29) = 29^2\gcd((28!+1)/29,28!)$. Now if $(28!+1)/29$ and $28!$ have a common divisor greater than 1 then they have a common prime divisor $p$ and clearly $p\le 23$. Consequently $p|(28!+1)$ and so $28!+1\equiv0\text{ mod }p$. But this is a contradiction as $28!\equiv0\text{ mod }p$. Hence we deduce that $\gcd((28!+1)/29,28!)=1$ and so $\gcd(29!+29,30!+29) = 29^2$.

Chapter 6

Exercise 6.13

Solution. First of all, colour the entries that are coprime to $5$, red. \[ \begin{array}{|c|c|c|c|c|} \hline \strut{\color{red}1}&{\color{red}2}&{\color{red}3}&{\color{red}4}&5\cr \hline \strut {\color{red}6}&{\color{red}7}&{\color{red}8}&{\color{red}9}&10\cr \hline \strut {\color{red}{11}}&{\color{red}{12}}&{\color{red}{13}}&{\color{red}{14}}&15\cr \hline \strut {\color{red}{16}}&{\color{red}{17}}&{\color{red}{18}}&{\color{red}{19}}&20\cr \hline \end{array} \] There are $4$ columns coloured red, and so $\phi(5)=4$. Now, for those entries already coloured red, re-colour the entries that are coprime to $4$, blue. \[ \begin{array}{|c|c|c|c|c|} \hline \strut{\color{blue}1}&{\color{red}2}&{\color{blue}3}&{\color{red}4}&5\cr \hline \strut {\color{red}6}&{\color{blue}7}&{\color{red}8}&{\color{blue}9}&10\cr \hline \strut {\color{blue}{11}}&{\color{red}{12}}&{\color{blue}{13}}&{\color{red}{14}}&15\cr \hline \strut {\color{red}{16}}&{\color{blue}{17}}&{\color{red}{18}}&{\color{blue}{19}}&20\cr \hline \end{array} \] There are $2$ blue entries in each column and so $\phi(4)=2$. There are 8 entries that are coprime to both $5$ and $4$ and so $\phi(20)=8$.

Exercise 6.16

Solution. \[ \phi(42) = 42(1-\frac12)(1-\frac13)(1-\frac17) = 12 \] The twelve residues are $1,5,11,13,17,19,23,25,29,31,37,41$.

Exercise 6.17

Solution. Since $\phi(n) = n\prod_{p|n}(1-1/p)$ then if $n$ has an odd prime factor $p$, $\phi(n)$ is a multiple of $p-1$ and so is even. Consequently, either $n=1$, in which case $\phi(n)=1$, or $n = 2^m$, in which case $\phi(2^m) = 2^{m-1}$ and so for this to be odd, we require $m=1$.

Since $\phi(p) = p-1$ when $p$ is a prime, then $\phi(3)=2, \phi(5)=4, \phi(7)=6, \phi(11)=10, \phi(13)=12$. Now $8=2^3$ and so from the above argument, $\phi(2^4) = 8$.

Suppose then that $\phi(n) = 14 = 2\times7$. Then $n = 2^{n_1}3^{n_2}5^{n_3}7^{n_4}$ for suitable non-negative integers $n_1, n_2, n_3, n_4$. Since $7|\phi(n)$ then $7|n$ and we see that $n_4 = 2$. However the $1-\frac17$ term then includes a factor of $6=2\times3$ and there is no way to cancel the $3$ using the remaining prime factors. This is then a contradiction.

Exercise 6.18

Solution. Suppose that $p^e|n$. Then $p^{e-1}(p-1)|\phi(n)$ and so $p^{e-1}(p-1)\le \phi(n)=m$. Therefore $p^e\le pm/(p-1)\le 2m$. But for a fixed positive integer $m$ there are only finitely many prime powers $p^e$ that divide 4m$. Hence there are only finitely many possible values of $n$.

Exercise 6.19

Solution. Since $\phi(n)/n = \prod_{p|n}(1-1/p)$ and since $(1-1/2)(1-1/3)(1-1/5) = 4/15>1/4$, we require at least 4 distinct prime factors in the factorisation of $n$. The smallest 4 that work (trial and error) is $2\times3\times5\times7$ which gives $\phi(n)/n = 8/35$ and so the smallest value of $n$ with this property is $n=2\times3\times5\times7=210$.

Exercise 6.21

Solution. To find the lastthree decimal digits we work $\text{ mod }1000$. Now $\phi(1000) = 1000(1-1/2)(1-1/5) = 400$. Euler’s Theorem then tell us that $a^{400}\equiv 1\text{ mod }1000$ and so $a^{2001} = \left(a^{400}\right)^5a\equiv a\text{ mod }1000$, as required.

Chapter 7

Exercise 7.1

Solution. Using the standard encoding ‘A’=$0$, ‘B’ = $1$, etc, we see that ‘G’ = $6$, ‘A’ = $0$, ‘U’= $20$, ‘S’ = $18$. Then the affine shift sets $6\mapsto 19 =$ ‘T’, $0\mapsto 3=$ ‘D’, $20\mapsto 13 =$ ‘N’, $18\mapsto 25 =$ ‘Z’. So ‘GAUSS’ becomes ‘TDNZZ’.

Using the Euclidean Algorithm, or otherwise, we deduce that $7\times15\equiv1\text{ mod }26$ and so the inverse shift is given by $x\mapsto 15(x-3) = 15x + 7\text{ mod }26$. Using the same mechanism as above we then see that ‘MFSJDG’ decodes as ‘FERMAT’.

Exercise 7.3

Solution. $9\mapsto 9^5 \equiv 9\times81^2\equiv9\times(-6)^2\equiv9\times7\equiv63\equiv5\text{ mod }29$.

$11\mapsto 11^{17}\equiv 11\times121^8\equiv11\times5^8\equiv11\times(-4)^4\equiv11\times256\equiv24\equiv11\times-5\equiv3\text{ mod }29$.

Exercise 7.4

Solution. We try $e=0,1,\ldots$ and in each case calculate $10^e\text{ mod }29$ and find that $10^{25}\equiv27\text{ mod }29$.

Exercise 7.6

Solution. Since $n=10147 = 73\times139$ then $\phi(n) = 72\times138 = 9936$. We need to solve the congruence $119f\equiv1\text{ mod }9936$ to find the decoding transformation. Using the Euclidean Algorithm we have \[ \begin{array}{rcl} 9936&=&83\times119+59\\ 119&=&2\times59+1\\ 59&=&59*1+0.\\ \end{array} \] Now using Bezout’s Identity we see that \[ \begin{array}{rcl} 1&=&1\times119-2\times59\\ &=&1\times119-2\times(9936-83\times119)\\ &=&167\times119-2\times9936\\ \end{array} \]

We then have a decoding transformation of $x\mapsto x^{167}\text{ mod }10147$.