Answers and Hints

1. Prime Numbers

   2.

   They are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,$
   $61, 67, 71, 73, 79, 83, 89, 97$ .

   3.

   Emulate the proof of Proposition 1.2.6.

   
   
   
   

2. The Ring of Integers Modulo $n$

   2.

   They are $5$ , $13$ , $3$ , and $8$ .

   3.

   For example $x=22$ , $y=-39$ .

   4.

   Hint: Use the binomial theorem and prove that if $r\geq 1$ then $p$ divides $\binom{p}{r}$ .

   7.

   For example, $S_1 = \{0,1,2,3,4,5,6\}$ , $S_2 = \{1,3,5,7,11,13,23\}$ , $S_3 = \{0,2,4,6,8,10,12\}$ , and $S_4 = \{2,3,5,7,11,13,29\}.$ In each we find $S_i$ by listing the first seven numbers satisfying the $i$ th condition, then adjusted the last number if necessary so that the reductions would be distinct modulo $7$ .

   8.

   An integer is divisible by $5$ if and only if the last digits is 0 or $5$ . An integer is divisible by $9$ if and only if the sum of the digits is divisible by $9$ . An integer is divisible by $11$ if and only if the alternating sum of the digits is divisible by $11$ .

   9.

   Hint for part (a): Use the divisibility rule you found in Exercise 1.8.

   10.

   $71$

   11.

   $8$

   12.

   As explained on page , we know that $\mathbb{Z}/n\mathbb{Z}{}$ is a ring for any $n$ . Thus to show that $\mathbb{Z}/p\mathbb{Z}{}$ is a field it suffices to show that every nonzero element $\overline{a}\in\mathbb{Z}/p\mathbb{Z}{}$ has an inverse. Lift $a$ to an element $a\in\mathbb{Z}$ , and set $b=p$ in Proposition 2.3.1. Because $p$ is prime, $\gcd(a,p)=1$ , so there exists $x,y$ such that $ax + py = 1$ . Reducing this equality modulo $p$ proves that $\overline{a}$ has an inverse $x\pmod{p}$ . Alternative one could argue just like after Definition 2.1.15 that $\overline{a}^m=1$ for some $m$ , so some power of $\overline{a}$ is the inverse of $\overline{a}$ .

   13.

   $302$

   15.

   Only for $n=1,2$ . If $n>2$ , then $n$ is either divisible by an odd prime $p$ or $4$ . If $4\mid n$ , then $2^e-2^{e-1}$ divides $\varphi (n)$ for some $e\geq 2$ , so $\varphi (n)$ is even. If an odd $p$ divides $n$ , then the even number $p^e-p^{e-1}$ divides $\varphi (n)$ for some $e\geq 1$ .

   16.

   The map $\psi$ is a homomorphism since both reduction maps

   $$\mathbb{Z}/mn\mathbb{Z}{}\to \mathbb{Z}/m\mathbb{Z}{}$$   and$$\quad \mathbb{Z}/mn\mathbb{Z}{}\to \mathbb{Z}/n\mathbb{Z}{}$$

   are homomorphisms. It is injective because if $a\in\mathbb{Z}$ is such that $\psi(a)=0$ , then $m\mid a$ and $n\mid a$ , so $mn\mid a$ (since $m$ and $n$ are coprime), so $a\equiv 0\pmod{mn}$ . The cardinality of $\mathbb{Z}/mn\mathbb{Z}{}$ is $mn$ and the cardinality of the product $\mathbb{Z}/m\mathbb{Z}{}\times \mathbb{Z}/n\mathbb{Z}{}$ is also $mn$ , so $\psi$ must be an isomorphism. The units $(\mathbb{Z}/mn\mathbb{Z}{})^*$ are thus in bijection with the units $(\mathbb{Z}/m\mathbb{Z}{})^* \times (\mathbb{Z}/n\mathbb{Z}{})^*$ .

   For the second part of the exercise, let $g=\gcd(m,n)$ and set $a=mn/g$ . Then $a\not\equiv 0\pmod{mn}$ , but $m\mid a$ and $n\mid a$ , so $a\ker(\psi)$ .

   17.

   We express the question as a system of linear equations modulo various numbers, and use the Chinese remainder theorem. Let $x$ be the number of books. The problem asserts that

   $$x \equiv 6\pmod{7}$$

   $$x \equiv 2\pmod{6}$$

   $$x \equiv 1\pmod{5}$$

   $$x \equiv 0\pmod{4}$$

   
   

   Applying CRT to the first pair of equations we find that $x\equiv 20\pmod{42}$ . Applying CRT to this equation and the third we find that $x\equiv 146\pmod{210}$ . Since $146$ is not divisible by $4$ , we add multiples of $210$ to $146$ until we find the first $x$ that is divisible by $4$ . The first multiple works, and we find that the aspiring mathematicians have $356$ math books.

   18.

   Note that $p=3$ works, since $11=3^2+2$ is prime. Now suppose $p\neq$ is any prime such that $p$ and $p^2+2$ are both prime. We must have $p\equiv 1\pmod{3}$ or $p\equiv 2\pmod{3}$ . Then $p^2\equiv 1\pmod{3}$ , so $p^2+2\equiv 0\pmod{3}$ , which contradicts the fact that $p^2+2$ is prime.

   19.

   For (a) $n=1,2$ , see solution to Exercise 2.15. For (b), yes there are many such examples. For example, $m=2$ , $n=4$ .

   20.

   By repeated application of multiplicativity and Equation (2.2.2) on page , we see that if $n=\prod_i p_i^{e_i}$ is the prime factorization of $n$ , then

   $$\varphi (n) = \prod_i (p_i^{e_i} - p_i^{e_i-1}) = \prod_i p_i^{e_i-1} \cdot \prod_i (p_i-1).$$

   23.

   1, 6, 29, 34

   24.

   Let $g=\gcd(12n+1,30n+2)$ . Then $g\mid 30n+2 - 2\cdot (12n+1) = 6n$ . For the same reason $g$ also divides $12n+1 - 2\cdot (6n) = 1$ , so $g=1$ , as claimed.

   27.

   There is no primitive root modulo $8$ , since $(\mathbb{Z}/8\mathbb{Z}{})^*$ has order $4$ , but every element of $(\mathbb{Z}/8\mathbb{Z}{})^*$ has order $2$ . Prove that if $\zeta$ is a primitive root modulo $2^n$ , for $n\geq 3$ , then the reduction of $\zeta$ mod $8$ is a primitive root, a contradiction.

   28.

   $2$ is a primitive root modulo $125$ .

   29.

   Let $\prod_{i=1}^m p_i^{e_i}$ be the prime factorization of $n$ . Slightly generalizing Exercise 16 we see that

   $$(\mathbb{Z}/n\mathbb{Z}{})^* \cong \prod (\mathbb{Z}/p_i^{e_i}\mathbb{Z}{})^*.$$

   Thus $(\mathbb{Z}/n\mathbb{Z}{})^*$ is cyclic if and only if the product $(\mathbb{Z}/p_i^{e_i}\mathbb{Z}{})^*$ is cyclic. If $8\mid n$ , then there is no chance $(\mathbb{Z}/n\mathbb{Z}{})^*$ is cyclic, so assume $8\nmid n$ . Then by Exercise 2.28 each group $(\mathbb{Z}/p_i^{e_i}\mathbb{Z}{})^*$ is itself cyclic. A product of cyclic groups is cyclic if and only the orders of the factors in the product are coprime (this follows from Exercise 2.16). Thus $(\mathbb{Z}/n\mathbb{Z}{})^*$ is cyclic if and only if the numbers $p_i(p_i-1)$ , for $i=1,\ldots, m$ are pairwise coprime. Since $p_i-1$ is even, there can be at most one odd prime in the factorization of $n$ , and we see that $(\mathbb{Z}/n\mathbb{Z}{})^*$ is cyclic if and only if $n$ is an odd prime power, twice an odd prime power, or $n=4$ .

   
   
   
   

3. Public-Key Cryptography

   1.

   The best case is that each letter is A. Then the question is to find the largest $n$ such that $1 + 27 + \cdots + 27^n \leq 10^{20}$ . By computing $\log_{27}(10^{20})$ , we see that $27^{13}<10^{20}$ and $27^{14}>10^{20}$ . Thus $n\leq 13$ , and since $1 + 27 + \cdots + 27^{n-1} < 27^n$ , and $2\cdot 27^{13}<10^{20}$ , it follows that $n=13$ .

   2.

   This is not secure, since it is just equivalent to a ``Ceaser Cipher'', that is a permutation of the letters of the alphabet, which is well-known to be easily broken using a frequency analysis.

   3.

   If we can compute the polynomial

   $$f = (x-p)(x-q)(x-r) = x^3 - (p+q+r)x^2 + (pq+pr+qr)x - pqr,$$

   then we can factor $n$ by finding the roots of $f$ , e.g., using Newton's method (or Cardona's formula for the roots of a cubic). Because $p$ , $q$ , $r$ , are distinct odd primes we have

   $$\varphi (n) =(p-1)(q-1)(r-1) = pqr-(pq+pr+qr)+p+q+r,$$

   and

   $$\sigma(n) = 1 + (p+q+r)+(pq+pr+qr) + pqr.$$

   Since we know $n$ , $\varphi (n)$ , and $\sigma(n)$ , we know

   $$\sigma(n)-1-n = (p+q+r)+(pq+pr+qr),$$

   $$\varphi (n)-n = (p+q+r)-(pq+pr+qr).$$

   
   

   We can thus compute both $p+q+r$ and $pq+pr+qr$ , hence deduce $f$ and find $p,q,r$ .

   
   
   
   

4. Quadratic Reciprocity

   1.

   They are all $1$ , $-1$ , 0 , and $1$ .

   3.

   By Proposition 4.3.4 the value of $\left(\frac{3}{p}\right)$ depends only on the reduction $\pm p\pmod{12}$ . List enough primes $p$ such that the $\pm p$ reduce to $1,5,7,11$ modulo $12$ and verify that the asserted formula holds for each of them.

   7.

   Since $p=2^{13}-1$ is prime there are either two solutions or no solutions to $x^2\equiv 5\pmod{p}$ , and we can decide which using quadratic reciprocity. We have

   $$\left(\frac{5}{p}\right) = (-1)^{(p-1)/2\cdot (5-1)/2}\left(\frac{p}{5}\right) = \left(\frac{p}{5}\right),$$

   so there are two solutions if and only if $p=2^{13}-1$ is $\pm 1$ mod $5$ . In fact $p\equiv 1\pmod{5}$ , so there are two solutions.

   8.

   We have $4^{48} = 2^{96}$ . By Fermat's Little Theorem $2^{96}=1$ , so $x=1$ .

   9.

   For (a) take $a=19$ and $n=20$ . We found this example using the Chinese remainder theorem applied to $4\pmod{5}$ and $3\pmod{4}$ , and used that $\left(\frac{19}{20}\right) = \left(\frac{19}{5}\right)\cdot\left(\frac{19}{4}\right) = (-1)(-1)=1$ , yet $19$ is not a square modulo either $5$ or $4$ , so is certainly not a square modulo $20$ .

   10.

   Hint: First reduce to the case that $6k-1$ is prime, by using that if $p$ and $q$ are primes not of the form $6k-1$ , then neither is their product. If $p=6k-1$ divides $n^2+n+1$ , it divides $4n^2+4n+4 = (2n+1)^2+3$ , so $-3$ is a quadratic residue modulo $p$ . Now use quadratic reciprocity to show that $-3$ is not a quadratic residue modulo $p$ .

   
   
   
   

5. Continued Fractions

   9.

   Suppose $n=x^2 + y^2$ , with $x,y\in\mathbb{Q}$ . Let $d$ be such that $dx, dy\in\mathbb{Z}$ . Then $d^2 n = (dx)^2 + (dy)^2$ is a sum of two integer squares, so by Theorem 5.6.1 if $p\mid d^2 n$ and $p\equiv 3 \pmod{4}$ , then $\ord _p(d^2n)$ is even. We have $\ord _p(d^2n)$ is even if and only if $\ord _p(n)$ is even, so Theorem 5.6.1 implies that $n$ is also a sum of two squares.

   11.

   The squares modulo $8$ are $0,1,4$ , so a sum of two squares reduces modulo $8$ to one of $0,1,2,4$ or $5$ . Four consecutive integers that are sums of squares would reduce to four consecutive integers in the set $\{0,1,2,4,5\}$ , which is impossible.

   
   
   
   

6. Elliptic Curves

   2.

   The second point of intersection is $(129/100, 383/1000)$ .

   3.

   The group is cyclic of order $9$ , generated by $(4,2)$ . The elements of $E(K)$ are

   $$\{\O, (4,2), (3,4), (2,4), (0,4), (0,1), (2,1), (3,1), (4,3)\}.$$

   4.

   In part (a) the pattern is that $N_p=p+1$ . For part (b), a hint is that when $p\equiv 2\pmod{3}$ , the map $x\mapsto x^3$ on $(\mathbb{Z}/p\mathbb{Z}{})^*$ is an automorphism, so $x\mapsto x^3+1$ is a bijection. Now use what you learned about squares in $\mathbb{Z}/p\mathbb{Z}{}$ from Chapter 4.

   5.

   For all sufficiently large real $x$ , the equation $y^2=x^3+ax+b$ has a real solution $y$ . Thus the group $E(\mathbb{R})$ is not countable, since $\mathbb {R}$ is not countable. But any finitely generated group is countable.

   6.

   In a course on abstract algebra one often proves the nontrivial fact that every subgroup of a finitely generated abelian group is finitely generated. In particular, the torsion subgroup $G_{\tor }$ is finitely generated. However, a finitely generated abelian torsion group is finite.

   7.

   Hint: Multiply both sides of $y^2=x^3+ax+b$ by a power of a common denominator, and ``absorb'' powers into $x$ and $y$ .

   8.

   Hint: see Exercise 4.6.