Chapter 1. Unique Factorization

back to chapters


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)\).

back to top

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}.\]

back to top

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}\]

back to top

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\).

back to top

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}\]

back to top

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.

back to top

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\).

back to top

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}.\]

back to top

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\).

back to top

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\).

back to top

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\).

back to top

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.

back to top

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\).

back to top

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\).

back to top

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.

back to top

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.

back to top

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.

back to top

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.

back to top

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.

back to top

Exercise 20

  1. 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).\]

  2. 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.\]

  3. 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).\]

back to top

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)\).

back to top

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.

back to top

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}\]

back to top

Exercise 24

  1. Multiplication makes all intermediate terms cancel: \[(x-y)\sum_{j=0}^{n-1}x^{\,n-1-j}y^j =x^n-y^n.\]

  2. 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\).

back to top

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.

back to top

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\).

back to top

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\).

back to top

Exercise 28

  1. 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.\]

  2. 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.\]

back to top

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\).

back to top

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.

back to top

Exercise 31

Since \[(1+i)^2=2i,\] we have \[2=(-i)(1+i)^2.\] Thus \((1+i)^2\mid2\) in \(\mathbb{Z}[i]\).

back to top

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}\]

back to top

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.\]

back to top

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]\).

back to top

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.\]

back to top

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\).

back to top

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\).

back to top

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.

back to top

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.

back to top