Chapter 1. Unique Factorization
Loading mathematical notation… If it does not load, check your connection or allow the MathJax script.
Exercise 1
For every \(d\in\mathbb{Z}\), \[d\mid a\text{ and }d\mid b \iff d\mid b\text{ and }d\mid(a-qb)=r.\] Thus \((a,b)\) and \((b,r)\) have the same common divisors, so \((a,b)=(b,r)\).
Exercise 2
By Problem 1, \[(a,b)=(b,r)=(r,r_1)=(r_1,r_2)=\cdots.\] The nonnegative remainders strictly decrease until one is zero, so the process terminates. If \(r_{k+1}\) is the last nonzero remainder, then \[(a,b)=\cdots=(r_k,r_{k+1})=(r_{k+1},0)=r_{k+1}.\]
Exercise 3
\[\begin{aligned} (187,221) &=(187,34)=(34,17)=17,\\ (6188,4709) &=(4709,1479)=(1479,272)=(272,119)\\ &=(119,34)=(34,17)=17,\\ (314,159) &=(159,155)=(155,4)=(4,3)=(3,1)=1. \end{aligned}\]
Exercise 4
Index the Euclidean divisions by \[r_{i-1}=q_i r_i+r_{i+1}, \qquad r_{-1}=a,\quad r_0=b.\] To obtain Bézout coefficients, track each remainder as a linear combination \(r_i=s_i a+t_i b\). For the initial remainders, define \[(s_{-1},t_{-1})=(1,0),\qquad (s_0,t_0)=(0,1),\] so \[s_{-1}a+t_{-1}b=a=r_{-1}, \qquad s_0a+t_0b=b=r_0.\] Suppose two consecutive remainders have already been expressed as \(r_{i-1}=s_{i-1}a+t_{i-1}b\) and \(r_i=s_i a+t_i b\). The next Euclidean remainder is therefore \[\begin{aligned} r_{i+1} &=r_{i-1}-q_i r_i \\ &=(s_{i-1}-q_i s_i)a+(t_{i-1}-q_i t_i)b. \end{aligned}\] This calculation tells us to update the coefficients by \[s_{i+1}=s_{i-1}-q_i s_i, \qquad t_{i+1}=t_{i-1}-q_i t_i.\] Consequently every remainder remains an integer linear combination of \(a\) and \(b\). By Problem 2, the last nonzero remainder \(r_N\) equals \(d=(a,b)\), so \[d=r_N=as_N+bt_N,\] so the required integers are \(m=s_N\) and \(n=t_N\).
Exercise 5
Use the indexing from Problem 4: \[r_{i-1}=q_i r_i+r_{i+1}, \qquad r_i=s_i a+t_i b.\] Rows \(i=-1,0\) are the initial data. In row \(i\), the quotient \(q_i\) produces the next remainder \(r_{i+1}\); the quotient in the final row produces zero. The bold entries give \(d\), \(m\), and \(n\).
\((a,b)=(187,221)\)
| \(i\) | \(q_i\) | \(r_i\) | \(s_i\) | \(t_i\) |
|---|---|---|---|---|
| \(-1\) | \(187\) | \(1\) | \(0\) | |
| \(0\) | \(0\) | \(221\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(187\) | \(1\) | \(0\) |
| \(2\) | \(5\) | \(34\) | \(-1\) | \(1\) |
| \(3\) | \(2\) | \(\mathbf{17}\) | \(\mathbf{6}\) | \(\mathbf{-5}\) |
\((a,b)=(6188,4709)\)
| \(i\) | \(q_i\) | \(r_i\) | \(s_i\) | \(t_i\) |
|---|---|---|---|---|
| \(-1\) | \(6188\) | \(1\) | \(0\) | |
| \(0\) | \(1\) | \(4709\) | \(0\) | \(1\) |
| \(1\) | \(3\) | \(1479\) | \(1\) | \(-1\) |
| \(2\) | \(5\) | \(272\) | \(-3\) | \(4\) |
| \(3\) | \(2\) | \(119\) | \(16\) | \(-21\) |
| \(4\) | \(3\) | \(34\) | \(-35\) | \(46\) |
| \(5\) | \(2\) | \(\mathbf{17}\) | \(\mathbf{121}\) | \(\mathbf{-159}\) |
\((a,b)=(314,159)\)
| \(i\) | \(q_i\) | \(r_i\) | \(s_i\) | \(t_i\) |
|---|---|---|---|---|
| \(-1\) | \(314\) | \(1\) | \(0\) | |
| \(0\) | \(1\) | \(159\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(155\) | \(1\) | \(-1\) |
| \(2\) | \(38\) | \(4\) | \(-1\) | \(2\) |
| \(3\) | \(1\) | \(3\) | \(39\) | \(-77\) |
| \(4\) | \(3\) | \(\mathbf{1}\) | \(\mathbf{-40}\) | \(\mathbf{79}\) |
Thus \[\begin{aligned} 17&=6\cdot187-5\cdot221,\\ 17&=121\cdot6188-159\cdot4709,\\ 1&=-40\cdot314+79\cdot159. \end{aligned}\]
Exercise 6
Let \(d=(a,b)\). If \(ax+by=c\) for some \(x,y\in\mathbb{Z}\), then \(d\) divides both \(ax\) and \(by\), hence \(d\mid c\).
Conversely, suppose \(d\mid c\), say \(c=kd\). By Problem 4, there exist \(m,n\in\mathbb{Z}\) such that \(d=am+bn\). Therefore \[c=kd=a(km)+b(kn),\] so \(x=km\) and \(y=kn\) give an integer solution.
Exercise 7
By Problem 4, there exist \(m,n\in\mathbb{Z}\) such that \[d=am+bn=d(a'm+b'n).\] Since \(d\neq0\), division by \(d\) gives \(1=a'm+b'n\). Every common divisor of \(a'\) and \(b'\) therefore divides \(1\), so \((a',b')=1\).
Exercise 8
Put \(a=da'\) and \(b=db'\), where \((a',b')=1\). For every \(t\in\mathbb{Z}\), \[a\left(x_0+t\frac{b}{d}\right) +b\left(y_0-t\frac{a}{d}\right)=ax_0+by_0=c,\] so every displayed pair is a solution.
Conversely, if \((x,y)\) is any solution, subtracting the equation for \((x_0,y_0)\) gives \[a'(x-x_0)=-b'(y-y_0).\] Thus \(b'\mid a'(x-x_0)\). Since \((a',b')=1\), Bézout’s identity implies \(b'\mid x-x_0\); hence \(x-x_0=tb'\) for some \(t\in\mathbb{Z}\). Substitution then gives \(y-y_0=-ta'\). Therefore \[x=x_0+t\frac{b}{d},\qquad y=y_0-t\frac{a}{d},\qquad t\in\mathbb{Z}.\]
Exercise 9
Write \(n=uk\). Since \(v\mid n=uk\) and \((u,v)=1\), Bézout’s identity gives \(v\mid k\). Thus \(k=v\ell\) for some \(\ell\in\mathbb{Z}\), and \[n=uv\ell,\] so \(uv\mid n\).
The coprimality assumption is necessary: for \(u=v=n=2\), both \(u\) and \(v\) divide \(n\), but \(uv=4\nmid2\).
Exercise 10
Let \(g=(u+v,u-v)\). Then \(g\mid2u\) and \(g\mid2v\). Since \((u,v)=1\), there exist \(m,n\in\mathbb{Z}\) such that \(um+vn=1\). Hence \[g\mid 2um+2vn=2.\] As \(g>0\), it follows that \(g=1\) or \(g=2\).
Exercise 11
If \(d=(a,a+k)\), then \(d\mid a\) and \(d\mid a+k\). Therefore \[d\mid(a+k)-a=k,\] so \((a,a+k)\mid k\).
Exercise 12
Let the regular polygon have \(n\) sides, and suppose \(k\) copies meet at the vertex. Its interior angle is \[\frac{(n-2)\pi}{n}.\] Since the \(k\) interior angles meet without gaps or overlaps, their sum is a full angle \(2\pi\). Hence \[k\frac{(n-2)\pi}{n}=2\pi.\] Canceling \(\pi\) and multiplying by \(n\) gives \[\begin{aligned} k(n-2)&=2n,\\ kn-2k-2n&=0. \end{aligned}\] To factor the left-hand side, add \(4\) to both sides: \[\begin{aligned} kn-2k-2n+4&=4,\\ (k-2)(n-2)&=4. \end{aligned}\] Since \(k,n\geq3\), both factors are positive integers. The positive factorizations of \(4\) give \[(k-2,n-2)=(1,4),(2,2),(4,1),\] and hence \[(k,n)=(3,6),(4,4),(6,3).\] Thus the three possibilities are three regular hexagons, four squares, and six equilateral triangles.
Exercise 13
Define \((n_1,\ldots,n_s)\) to be the unique nonnegative integer \(d\) such that \[d\mid n_i\quad(1\leq i\leq s),\] and every common divisor of \(n_1,\ldots,n_s\) divides \(d\). This definition also gives \(d=0\) when all the \(n_i\) are zero, in which case the desired identity is immediate. Otherwise, after relabeling, assume \(n_1\neq0\).
Set \[d_1=|n_1|, \qquad d_j=(d_{j-1},n_j)\quad(2\leq j\leq s).\] Inductively, \(d_j\) is the greatest common divisor of \(n_1,\ldots,n_j\): it divides all these integers, while every common divisor of them divides both \(d_{j-1}\) and \(n_j\), and hence divides \(d_j\). In particular, \(d_s=d\).
It remains to track a linear combination. We have \(d_1=\varepsilon n_1\), where \(\varepsilon\in\{1,-1\}\). Suppose \[d_{j-1}=n_1c_1+\cdots+n_{j-1}c_{j-1}.\] By the two-integer Bézout identity, there exist \(u_j,v_j\in\mathbb{Z}\) such that \[d_j=u_jd_{j-1}+v_jn_j.\] Substituting the preceding expression gives \[d_j=n_1(u_jc_1)+\cdots+n_{j-1}(u_jc_{j-1})+n_jv_j.\] Thus each \(d_j\) is an integer linear combination of \(n_1,\ldots,n_j\). Taking \(j=s\) yields \[d=n_1m_1+\cdots+n_sm_s\] for suitable integers \(m_1,\ldots,m_s\).
Exercise 14
Let \[d=(a_1,\ldots,a_s).\] If integers \(x_1,\ldots,x_s\) satisfy \(a_1x_1+\cdots+a_sx_s=c\), then \(d\) divides every term on the left, and hence \(d\mid c\).
Conversely, suppose \(d\mid c\), say \(c=kd\). By Problem 13, there exist \(m_1,\ldots,m_s\in\mathbb{Z}\) such that \[d=a_1m_1+\cdots+a_sm_s.\] Multiplying by \(k\) gives \[c=a_1(km_1)+\cdots+a_s(km_s),\] so \(x_i=km_i\) gives an integer solution. Therefore the equation is solvable in integers if and only if \(d\mid c\).
Exercise 15
For \(a>0\), write its prime factorization as \[a=\prod_p p^{e_p}, \qquad e_p=\mathop{\mathrm{ord}}_p(a),\] where only finitely many \(e_p\) are nonzero. If \(a=b^2\) and \(|b|=\prod_p p^{f_p}\), then \(e_p=2f_p\) for every prime \(p\), so every \(e_p\) is even.
Conversely, if every \(e_p\) is even, then \[a=\left(\prod_p p^{e_p/2}\right)^2,\] so \(a\) is a square.
More generally, for any integer \(r\geq2\), a positive integer \(a\) is an \(r\)th power if and only if \[r\mid\mathop{\mathrm{ord}}_p(a)\] for every prime \(p\). For arbitrary nonzero integers, one must additionally require \(a>0\) when \(r\) is even; when \(r\) is odd, there is no sign restriction.
Exercise 16
For every prime \(p\), \[\mathop{\mathrm{ord}}_p(u)+\mathop{\mathrm{ord}}_p(v)=\mathop{\mathrm{ord}}_p(uv)=2\mathop{\mathrm{ord}}_p(a),\] which is even. Since \((u,v)=1\), at most one of \(\mathop{\mathrm{ord}}_p(u)\) and \(\mathop{\mathrm{ord}}_p(v)\) is nonzero. Hence each nonzero exponent occurring in either \(u\) or \(v\) is even. By Problem 15, both \(u\) and \(v\) are squares.
Exercise 17
Suppose \(\sqrt{2}=a/b\), where \(a,b\in\mathbb{Z}\) and \(b\neq0\). Then \[a^2=2b^2.\] Taking the exponent of \(2\) on both sides gives \[2\mathop{\mathrm{ord}}_2(a)=1+2\mathop{\mathrm{ord}}_2(b).\] The left-hand side is even and the right-hand side is odd, a contradiction. Thus \(\sqrt{2}\) is irrational.
Exercise 18
Suppose \(\sqrt[n]{m}=a/b\in\mathbb{Q}\), written in lowest terms with \(b>0\). Then \[a^n=mb^n,\] so \(b^n\mid a^n\). But \((a,b)=1\) implies \((a^n,b^n)=1\); hence \(b^n=1\) and \(b=1\). Therefore \[m=a^n,\] contrary to the assumption. Thus \(\sqrt[n]{m}\) is irrational.
Exercise 19
If \(ab=0\), then \(m=0\) has the required property. Assume \(ab\neq0\), let \(d=(a,b)\), and write \[a=du,\qquad b=dv,\qquad (u,v)=1.\] Set \[m=duv=\frac{ab}{d}.\] Since \(m=av=bu\), it is a common multiple of \(a\) and \(b\). If \(N\) is any common multiple, write \(N=ax=by\). Then \(ux=vy\). As \((u,v)=1\), we have \(v\mid x\), say \(x=vt\). Therefore \[N=ax=duvt=mt,\] so \(m\mid N\).
If \(m'\) has the same defining property, then \(m\mid m'\) and \(m'\mid m\). Hence \(m'=\pm m\), proving uniqueness up to sign.
Exercise 20
By unique factorization, the positive integer \[L=\prod_q q^{\max(\mathop{\mathrm{ord}}_q(a),\mathop{\mathrm{ord}}_q(b))}\] is a common multiple of \(a\) and \(b\), and it divides every common multiple. Thus \(L=|[a,b]|\). In particular, putting \(\alpha=\mathop{\mathrm{ord}}_p(a)\) and \(\beta=\mathop{\mathrm{ord}}_p(b)\) gives \[\mathop{\mathrm{ord}}_p[a,b]=\max(\alpha,\beta).\]
Since \(\mathop{\mathrm{ord}}_p(a,b)=\min(\alpha,\beta)\), part (a) gives \[\mathop{\mathrm{ord}}_p\bigl((a,b)[a,b]\bigr) =\min(\alpha,\beta)+\max(\alpha,\beta) =\alpha+\beta =\mathop{\mathrm{ord}}_p(ab).\] Thus the two sides agree up to sign; with the choice \([a,b]=ab/(a,b)\) from Problem 19, their signs also agree. Therefore \[(a,b)[a,b]=ab.\]
Write \(a=du\) and \(b=dv\), where \(d=(a,b)\) and \((u,v)=1\). By Problem 19, \([a,b]=duv\), so \[(a+b,[a,b])=d\,(u+v,uv).\] Suppose a prime \(p\) divides both \(u+v\) and \(uv\). Since \(p\mid uv\), Euclid’s lemma gives \(p\mid u\) or \(p\mid v\). If \(p\mid u\), then \[p\mid(u+v)-u=v;\] if \(p\mid v\), then similarly \(p\mid(u+v)-v=u\). In either case \(p\) divides both \(u\) and \(v\), contradicting \((u,v)=1\). Thus \((u+v,uv)=1\), and \[(a+b,[a,b])=d=(a,b).\]
Exercise 21
Let \[\alpha=\mathop{\mathrm{ord}}_p(a),\qquad \beta=\mathop{\mathrm{ord}}_p(b),\] and suppose first that \(\alpha\leq\beta\). Write \[a=p^\alpha u,\qquad b=p^\beta v, \qquad p\nmid u,\quad p\nmid v.\] Factoring out the smaller power of \(p\) gives \[a+b=p^\alpha\bigl(u+p^{\beta-\alpha}v\bigr),\] so \[\mathop{\mathrm{ord}}_p(a+b)\geq\alpha =\min\bigl(\mathop{\mathrm{ord}}_p(a),\mathop{\mathrm{ord}}_p(b)\bigr).\] If \(\alpha<\beta\), then \(p\mid p^{\beta-\alpha}v\) but \(p\nmid u\); hence \[p\nmid u+p^{\beta-\alpha}v.\] Therefore \(\mathop{\mathrm{ord}}_p(a+b)=\alpha\). The case \(\beta<\alpha\) is symmetric, so equality holds whenever \(\mathop{\mathrm{ord}}_p(a)\neq\mathop{\mathrm{ord}}_p(b)\).
Exercise 22
Let \(R\) be a Euclidean domain with Euclidean function \(\delta\). For \(a,b\in R\) with \(b\neq0\), division gives \[a=qb+r, \qquad r=0\ \text{or}\ \delta(r)<\delta(b).\] Moreover, \(a\) and \(b\) have exactly the same common divisors as \(b\) and \(r\). Repeating the division produces a strictly decreasing sequence of Euclidean values, so the process terminates. Its last nonzero remainder \(d\) is therefore a greatest common divisor of \(a\) and \(b\), determined up to multiplication by a unit.
The remainder equations may be substituted backwards exactly as over \(\mathbb{Z}\), giving \[d=ax+by\] for some \(x,y\in R\). These are the only ingredients used in the earlier divisibility arguments. Consequently, with equality understood up to a unit, the same proofs give, for example, \[ax+by=c\ \text{is solvable} \quad\Longleftrightarrow\quad d\mid c,\] as well as coprime cancellation, the coprime-product property, and the gcd–lcm identities.
Every Euclidean domain is a principal ideal domain and hence a unique factorization domain. Thus the arguments using prime exponents also remain valid. The only extra qualification is the unit factor: an element is an \(n\)th power precisely when every irreducible exponent is divisible by \(n\) and its unit factor is itself an \(n\)th power.
For \(k[X]\), take \(\delta(f)=\deg f\) for \(f\neq0\). Its units are the nonzero constants in \(k\); choosing gcds and lcms to be monic removes the unit ambiguity. Hence all of the preceding algebraic arguments apply to polynomials. Statements specifically involving order, sign, geometry, or irrational real roots have no literal analogue in an arbitrary Euclidean domain.
Exercise 23
Changing signs and interchanging \(a\) and \(b\) if necessary, we may assume \(c>0\), \(a\) is even, and \(b\) is odd. Indeed, \(a\) and \(b\) cannot both be odd, since squares of odd integers are \(1\) modulo \(4\); nor can they both be even, since \((a,b)=1\). Hence exactly one is even, and then \(c\) is odd.
Set \[x=\frac{c-b}{2},\qquad y=\frac{c+b}{2}.\] Since \(c^2=a^2+b^2\) and \(c>0\), we have \(c\geq |b|\), so both \(x\) and \(y\) are nonnegative. Their product is \[xy=\frac{c^2-b^2}{4}=\frac{a^2}{4} =\left(\frac a2\right)^2.\] Moreover, if \(d\mid x\) and \(d\mid y\), then \[d\mid x+y=c,\qquad d\mid y-x=b.\] Since \((b,c)=1\), this forces \(|d|=1\); hence \((x,y)=1\). Thus \(x\) and \(y\) are coprime nonnegative integers whose product is a square. By Exercise 16, each is a square, so for some integers \(u,v\), \[\frac{c-b}{2}=u^2,\qquad \frac{c+b}{2}=v^2.\] Equivalently, \[c-b=2u^2,\qquad c+b=2v^2.\] Also \((u,v)=1\), since any common divisor of \(u\) and \(v\) would have its square divide both \(u^2=x\) and \(v^2=y\).
Adding and subtracting the two equations gives \[c=u^2+v^2,\qquad b=v^2-u^2.\] Finally, \[a^2=c^2-b^2=(c-b)(c+b)=4u^2v^2.\] Choosing the sign of \(u\) if necessary, we obtain \(a=2uv\).
Conversely, for any integers \(u,v\), let \[a=2uv,\qquad b=v^2-u^2,\qquad c=v^2+u^2.\] Then \[\begin{aligned} a^2+b^2 &=4u^2v^2+(v^2-u^2)^2 \\ &=u^4+2u^2v^2+v^4 \\ &=(u^2+v^2)^2=c^2. \end{aligned}\]
Exercise 24
Multiplication makes all intermediate terms cancel: \[(x-y)\sum_{j=0}^{n-1}x^{\,n-1-j}y^j =x^n-y^n.\]
Similarly, \[(x+y)\sum_{j=0}^{n-1}(-1)^j x^{\,n-1-j}y^j =x^n+(-1)^{n-1}y^n.\] When \(n\) is odd, \(n-1\) is even, so the right-hand side is \(x^n+y^n\).
Exercise 25
For \(a>1\) and \(n>1\), Exercise 24(a) gives \[a^n-1=(a-1)(a^{n-1}+a^{n-2}+\cdots+1).\] The second factor is greater than \(1\), so primality forces \(a-1=1\); hence \(a=2\).
If \(n=rs\) with \(r,s>1\), then \[2^n-1=(2^r)^s-1\] is divisible by \(2^r-1\), where \[1<2^r-1<2^n-1.\] This contradicts primality. Therefore \(n\) is prime.
Exercise 26
If \(a\) were odd, then \(a\equiv1\pmod 2\), and therefore \[a^n+1\equiv1^n+1\equiv0\pmod 2.\] Thus \(a^n+1\) would be even. Since \(a^n+1>2\), it would be composite, a contradiction. Hence \(a\) is even.
Write \[n=2^t m,\] where \(m\) is odd. If \(m>1\), set \(x=a^{2^t}\). By Exercise 24(b), \[a^n+1=x^m+1\] is divisible by \(x+1\), and \[1<x+1<x^m+1.\] This again contradicts primality. Hence \(m=1\), so \(n=2^t\) is a power of \(2\).
Exercise 27
The second assertion retains the hypothesis that \(n\) is odd. Without it the statement is false: for \(n=2\), one has \(3\nmid n\) but \(6\nmid n^2-1\).
Let \(n=2k+1\). Then \[n^2-1=4k(k+1).\] One of the consecutive integers \(k\) and \(k+1\) is even, so \(8\mid n^2-1\).
For the same odd \(n\), suppose also that \(3\nmid n\). Then \(n\equiv\pm1\pmod 3\), so \(3\mid n^2-1\). Since \(2\mid n^2-1\) and \((2,3)=1\), it follows that \(6\mid n^2-1\).
Exercise 28
Factor \[n^5-n=n(n^2-1)(n^2+1).\] Since \(n(n^2-1)=(n-1)n(n+1)\) is a product of three consecutive integers, it is divisible by both \(2\) and \(3\). It remains to find a factor of \(5\). For every integer \(n\), \[n^2\equiv0,\ 1,\ \text{or }-1\pmod 5.\] The three possibilities correspond exactly to \[\begin{array}{c||c|c|c} n^2\bmod 5 & 0 & 1 & -1 \\ \hline 5\text{ divides} & n & n^2-1 & n^2+1 \end{array}\] Thus \(5\mid n^5-n\). Since \(2\), \(3\), and \(5\) are pairwise coprime, \[30\mid n^5-n.\]
Factor \[n^7-n=n(n^2-1)(n^4+n^2+1).\] The factor \((n-1)n(n+1)\) again supplies \(2\) and \(3\), so it remains to find a factor of \(7\). The square residues modulo \(7\) are obtained from \[\begin{array}{c||c|c|c|c} n\bmod 7 & 0 & \pm1 & \pm2 & \pm3 \\ \hline n^2\bmod 7 & 0 & 1 & 4 & 2 \end{array}\] Put \(z\equiv n^2\pmod 7\). Thus \(z\in\{0,1,2,4\}\), and \[\begin{array}{c||c|c|c|c} z & 0 & 1 & 2 & 4 \\ \hline 7\text{ divides} & n & n^2-1 & n^4+n^2+1 & n^4+n^2+1 \end{array}\] Indeed, in the last two columns, \[2^2+2+1=7,\qquad 4^2+4+1=21.\] Hence \(7\mid n^7-n\). Since \(2\), \(3\), and \(7\) are pairwise coprime, \[42\mid n^7-n.\]
Exercise 29
Let \[\frac ab+\frac cd=m\] for some \(m\in\mathbb{Z}\). Clearing denominators gives \[ad+bc=mbd.\] Reducing this equation modulo \(b\) yields \[ad\equiv0\pmod b,\] so \(b\mid ad\). Since \((a,b)=1\), coprime cancellation gives \(b\mid d\).
Similarly, reducing the same equation modulo \(d\) gives \[bc\equiv0\pmod d.\] Thus \(d\mid bc\), and \((c,d)=1\) gives \(d\mid b\). Hence \(b\mid d\) and \(d\mid b\). Since the denominators are nonzero, this implies \[|b|=|d|,\] and therefore \(b=\pm d\).
Exercise 30
Choose \(k\) so that \[2^k\leq n<2^{k+1},\] and let \(L=\operatorname{lcm}(1,2,\ldots,n)\). The largest power of \(2\) dividing \(L\) is \(2^k\). Moreover, among \(1,\ldots,n\), the only integer divisible by \(2^k\) is \(2^k\) itself, since the next multiple \(2^{k+1}\) is greater than \(n\).
Writing the sum over the common denominator \(L\) gives \[\frac12+\frac13+\cdots+\frac1n =\frac{A}{L}, \qquad A=\sum_{j=2}^n\frac Lj.\] For \(j=2^k\), the integer \(L/j\) is odd. For every other \(j\), the power of \(2\) dividing \(j\) is at most \(2^{k-1}\), so \(L/j\) is even. Thus \(A\) is the sum of one odd integer and several even integers, and is therefore odd.
Since \(L\) is even while \(A\) is odd, the factor \(2\) cannot cancel from the denominator. Hence the sum is not an integer.
Exercise 31
Since \[(1+i)^2=2i,\] we have \[2=(-i)(1+i)^2.\] Thus \((1+i)^2\mid2\) in \(\mathbb{Z}[i]\).
Exercise 32
We have \[(a+bi)(c+di)=(ac-bd)+(ad+bc)i.\] For any \(\alpha,\beta\in\mathbb{Z}[i]\), conjugation satisfies \(\overline{\alpha\beta}=\overline{\alpha}\,\overline{\beta}\). Therefore \[\begin{aligned} \lambda(\alpha\beta) &=(\alpha\beta)\overline{\alpha\beta} \\ &=(\alpha\beta) \bigl(\overline{\alpha}\,\overline{\beta}\bigr) \\ &=(\alpha\overline{\alpha}) (\beta\overline{\beta}) \\ &=\lambda(\alpha)\lambda(\beta). \end{aligned}\] Thus \(\lambda\) is multiplicative. Applying this to \(a+bi\) and \(c+di\) gives \[\begin{aligned} (a^2+b^2)(c^2+d^2) &=\lambda(a+bi)\lambda(c+di) \\ &=\lambda\bigl((a+bi)(c+di)\bigr) \\ &=(ac-bd)^2+(ad+bc)^2. \end{aligned}\]
Exercise 33
If \(\alpha\) is a unit, there is some \(\beta\in\mathbb{Z}[i]\) such that \(\alpha\beta=1\). Hence \[\lambda(\alpha)\lambda(\beta) =\lambda(\alpha\beta)=\lambda(1)=1.\] Both factors are nonnegative integers, so \(\lambda(\alpha)=1\).
Conversely, if \(\lambda(\alpha)=1\), then \[\alpha\overline{\alpha}=\lambda(\alpha)=1,\] so \(\overline{\alpha}\in\mathbb{Z}[i]\) is the inverse of \(\alpha\). Thus \(\alpha\) is a unit.
Finally, if \(\alpha=a+bi\), then \(\lambda(\alpha)=1\) means \[a^2+b^2=1.\] The only integer solutions are \((a,b)=(\pm1,0)\) and \((0,\pm1)\). Therefore the only units in \(\mathbb{Z}[i]\) are \[1,\quad -1,\quad i,\quad -i.\]
Exercise 34
Using \(\omega^2+\omega+1=0\) and \(\omega^3=1\), we obtain \[(1-\omega)^2 =1-2\omega+\omega^2 =-3\omega.\] Consequently, \[3=(-\omega^2)(1-\omega)^2,\] so \((1-\omega)^2\mid3\) in \(\mathbb{Z}[\omega]\).
Exercise 35
Since \(\overline{\omega}=\omega^2=-1-\omega\), the conjugate of \(\alpha=a+b\omega\) again lies in \(\mathbb{Z}[\omega]\), and \[\alpha\overline{\alpha} =(a+b\omega)(a+b\omega^2) =a^2-ab+b^2 =\lambda(\alpha).\] As in Exercise 32, conjugation respects products, so \(\lambda\) is multiplicative.
If \(\alpha\) is a unit with inverse \(\beta\), then \[\lambda(\alpha)\lambda(\beta) =\lambda(\alpha\beta)=\lambda(1)=1.\] Since both factors are nonnegative integers, \(\lambda(\alpha)=1\). Conversely, if \(\lambda(\alpha)=1\), then \[\alpha\overline{\alpha}=1,\] so \(\overline{\alpha}\in\mathbb{Z}[\omega]\) is the inverse of \(\alpha\).
It remains to solve \[a^2-ab+b^2=1.\] Multiplying by \(4\) and completing the square gives \[(2a-b)^2+3b^2=4.\] Hence \(|b|\leq1\). If \(b=0\), then \(a=\pm1\). If \(b=1\), then \(a(a-1)=0\), so \(a=0\) or \(1\); if \(b=-1\), then \(a(a+1)=0\), so \(a=0\) or \(-1\). These possibilities give precisely \[1,\quad -1,\quad \omega,\quad -\omega,\quad \omega^2,\quad -\omega^2.\]
Exercise 36
Write \(\tau=\sqrt{-2}\). Since \(\tau^2=-2\), we have \[\begin{aligned} (a+b\tau)+(c+d\tau)&=(a+c)+(b+d)\tau,\\ -(a+b\tau)&=-a-b\tau,\\ (a+b\tau)(c+d\tau)&=(ac-2bd)+(ad+bc)\tau. \end{aligned}\] Thus \(\mathbb{Z}[\tau]\) contains \(0\) and \(1\) and is closed under addition, additive inverses, and multiplication, so it is a ring. It is an integral domain because it is a subring of \(\mathbb{C}\).
Complex conjugation sends \(a+b\tau\) to \(a-b\tau\), and hence \[\lambda(a+b\tau) =(a+b\tau)(a-b\tau)=a^2+2b^2.\] Therefore \(\lambda(\alpha\beta)=\lambda(\alpha)\lambda(\beta)\), and \(\lambda(\alpha)\) is a nonnegative integer which vanishes only when \(\alpha=0\). Thus \(\lambda\) has the correct positive-integer values for a Euclidean function; it remains to verify the Euclidean division condition.
Now let \(\alpha,\beta\in\mathbb{Z}[\tau]\) with \(\beta\neq0\). Write \(\beta=c+d\tau\) and, in the field \(\mathbb{Q}(\tau)\), write \[\frac{\alpha}{\beta}=x+y\tau, \qquad x,y\in\mathbb{Q}.\] Choose \(m,n\in\mathbb{Z}\) nearest to \(x,y\), respectively, so that \[|x-m|\leq\frac12, \qquad |y-n|\leq\frac12.\] Set \[u=x-m,\qquad v=y-n, \qquad q=m+n\tau, \qquad r=\alpha-q\beta.\] Then \(q,r\in\mathbb{Z}[\tau]\) and \(\alpha=q\beta+r\). Direct multiplication gives \[\begin{aligned} r &=\beta\left(\frac{\alpha}{\beta}-q\right)\\ &=(c+d\tau)(u+v\tau)\\ &=(cu-2dv)+(cv+du)\tau. \end{aligned}\] Although \(u,v\) need not be integers, the two coefficients in the last line are integers because \(r\in\mathbb{Z}[\tau]\). Hence \[\begin{aligned} \lambda(r) &=(cu-2dv)^2+2(cv+du)^2\\ &=\bigl(c^2u^2-4cduv+4d^2v^2\bigr) +\bigl(2c^2v^2+4cduv+2d^2u^2\bigr)\\ &=(c^2+2d^2)u^2+2(c^2+2d^2)v^2\\ &=\lambda(\beta)(u^2+2v^2). \end{aligned}\] The cross terms \(-4cduv\) and \(4cduv\) cancel. Moreover, \[u^2+2v^2 \leq \frac14+2\cdot\frac14 =\frac34.\] Since \(\beta\neq0\), we have \(\lambda(\beta)>0\), and therefore \[\lambda(r) \leq\frac34\lambda(\beta) <\lambda(\beta).\] Thus every division has remainder \(r=0\) or \(\lambda(r)<\lambda(\beta)\), so \(\mathbb{Z}[\sqrt{-2}]\) is a Euclidean domain with Euclidean function \(\lambda\).
Exercise 37
If \(\alpha\) is a unit with inverse \(\beta\), multiplicativity gives \[\lambda(\alpha)\lambda(\beta)=\lambda(1)=1.\] Both factors are nonnegative integers, so \(\lambda(\alpha)=1\). Conversely, if \(\lambda(\alpha)=1\), then \(\alpha\overline{\alpha}=1\), so \(\alpha\) is a unit.
For \(\alpha=a+b\sqrt{-2}\), the equation \(\lambda(\alpha)=1\) is \[a^2+2b^2=1.\] It forces \(b=0\) and \(a=\pm1\). Hence the only units are \(1\) and \(-1\).
Exercise 38
Let \(R\) be any one of \[\mathbb{Z}[i],\qquad \mathbb{Z}[\omega],\qquad \mathbb{Z}[\sqrt{-2}],\] and let \(\lambda\) denote its norm. Suppose \(\lambda(\pi)=p\), where \(p\) is prime in \(\mathbb{Z}\).
First, \(\pi\) is irreducible. Indeed, if \(\pi=\gamma\delta\), then \[p=\lambda(\pi)=\lambda(\gamma)\lambda(\delta).\] The two factors on the right are positive integers, so one of them is \(1\). By Exercises 33, 35, and 37, the corresponding element is a unit.
Each of these rings is a Euclidean domain. To prove that \(\pi\) is prime, we must show that \[\pi\mid\alpha\beta \quad\Longrightarrow\quad \pi\mid\alpha\ \text{or}\ \pi\mid\beta.\] Now suppose \(\pi\mid\alpha\beta\). If \(\pi\mid\alpha\), there is nothing to prove. Otherwise, suppose \(\pi\nmid\alpha\), and let \(d\) be any common divisor of \(\pi\) and \(\alpha\). Since \(d\mid\pi\), write \[\pi=d\eta\] for some \(\eta\in R\). Because \(\pi\) is irreducible, either \(d\) or \(\eta\) is a unit. If \(d\) were not a unit, then \(\eta\) would be a unit, so \(d\) would be associated to \(\pi\). But \(d\mid\alpha\) would then imply \(\pi\mid\alpha\), contrary to our assumption. Hence every common divisor \(d\) is a unit. Thus \(\gcd(\pi,\alpha)=1\) up to a unit, and Bézout’s identity gives \[x\pi+y\alpha=1\] for some \(x,y\in R\). Multiplying by \(\beta\) yields \[\beta=x\pi\beta+y\alpha\beta.\] By hypothesis, \(\pi\mid\alpha\beta\), so \(\alpha\beta=\pi t\) for some \(t\in R\). Hence \[x\pi\beta=\pi(x\beta), \qquad y\alpha\beta=y\pi t=\pi(yt).\] Both terms on the right are therefore divisible by \(\pi\), so \(\pi\mid\beta\). Therefore \(\pi\) is prime in \(R\). This proves the assertion simultaneously for all three rings.
Exercise 39
Let \(p\) be a prime element in an integral domain, and suppose \[p=ab.\] Since \(p\mid ab\), primality gives \(p\mid a\) or \(p\mid b\). If \(p\mid a\), write \(a=pc\). Then \[p=ab=pcb.\] Because the ring is an integral domain and \(p\neq0\), cancellation gives \(1=cb\); hence \(b\) is a unit. Similarly, if \(p\mid b\), then \(a\) is a unit. Thus every factorization of \(p\) has a unit factor, so \(p\) is irreducible.