ch21.md

title	author	header-includes	abstract
Abstract Algebra by Pinter, Chapter 21	Amir Taaki	- \usepackage{mathrsfs} - \usepackage{mathtools} - \usepackage{extpfeil} - \DeclareMathOperator\ker{ker} - \DeclareMathOperator\ord{ord} - \DeclareMathOperator\gcd{gcd} - \DeclareMathOperator\lcm{lcm} - \DeclareMathOperator\mod{mod} - \DeclareMathOperator\char{char}	Chapter 21 on Integers

A. Properties of Order Relations in Integral Domains

Q1

$$a \leq b, b \leq c \implies a \leq c$$

4 cases: $$a < b, b = c \implies a < c$$ $$a < b, b < c \implies a < c$$ $$a = b, b = c \implies a = c$$ $$a = b, b < c \implies a < c$$

Q2

$$a \leq b \implies a + c \leq b + c$$

$$a < b \implies a + c < b + c$$ $$a = b \implies a + c = b + c$$

Q3

$$a \leq b, c \geq 0 \implies ac \leq bc$$

$$a < b, c > 0 \implies ac < bc$$ $$a < b, c = 0 \implies ac = 0 = bc$$ $$a = b, c \geq 0 \implies ac = bc$$

Q4

$$c < 0 \implies -c > 0$$ $$a < b \implies -ac < -bc$$ $$-ac + bc < 0$$ $$bc < ac$$

Q5

$$a < b$$ $$a - b < 0$$ $$\implies -b < -a$$

Q6

$$a + c < b + c \implies a + c - c < b \implies a < b$$

Q7

$$ac < bc, c > 0 \implies a < b$$

$$ac < bc$$ $$\implies 0 < bc - ac$$ $$\implies 0 < c(b -a)$$ but $c &gt; 0 \implies b -a &gt; 0$ $$ b > a$$

Q8

$$a < b, c < d$$ $$a - b < 0, 0 < d - c$$ $$\implies a - b < d - c$$ $$\implies a + c < b + d$$

B. Further Properties of Ordered Integral Domains

Q1

$$c^2 \geq 0 \implies (a - b)^2 \geq 0$$ $$a^2 + b^2 \geq 2ab$$

Q2

$$ab \leq 2ab$$ $$\implies a^2 + b^2 \geq ab$$ $$(-a)^2 + b^2 = a^2 + b^2 \geq -ab$$

Q3

$$(a - b)^2 + (b - c)^2 + (c - a)^2 \geq 0$$

Q4

$$a^2 + b^2 \neq 0 \implies a \neq 0, b \neq 0$$ $$(a + b)^2 > 0 \implies a^2 + b^2 > ab$$

Q5

$$a, b > 1 \implies (a - 1) > 0, (b - 1) > 0$$ $$(a - 1)(b - 1) = ab + 1 - a - b > 0$$

Q6

$$(a - 1)(b - 1)(c - 1) > 0$$ $$abc + a + b + c - ab - ac - bc - 1 > 0$$ $$ab + ac + bc + 1 < a + b + c + abc$$

C. Uses of Induction

Q1

Assume $S_k$ is correct.

$$k^2 + 2(k + 1) - 1 = (k + 1)^2$$

Thus is correct.

Q2

$$S_1: 1^3 = 1^2$$

Assume $S_k$ is true.

$S_{k + 1}$:

$$(1 + 2 + \cdots + k)^2 + (k + 1)^3 = (1 + 2 + \cdots + k + 1)^2$$ $$(\frac{k(k + 1)}{2})^2 + (k + 1)^3 = (\frac{(k + 1)(k + 2)}{2})^2$$

sage: bool(((k*(k + 1)) / 2)**2 + (k + 1)**3 == ((k + 1)*(k + 2)/2)**2)
True

Q3

$S_1: 0^2 &lt; \frac{1^3}{3} &lt; 1^2$

$S_2: 1^2 &lt; \frac{8}{3} = 2\frac{2}{3} &lt; 1^2 + 2^2 = 5$

Assume $S_k$ is true, then:

$$1^2 + \cdots + (k - 1)^2 < \frac{k^3}{3}$$ $$\frac{k^3}{3} < 1^2 + \cdots + k^2$$

$S_{k + 1}$:

$$1^2 + \cdots + k^2 < \frac{(k + 1)^3}{3}$$ $$1^2 + 2^2 + \cdots + (k - 1)^2 + k^2 < \frac{(k + 1)^3}{3}$$

but

$$1^2 + 2^2 + \cdots + (k - 1)^2 + k^2 < \frac{k^3}{3} + k^2$$ $$\frac{k^3 + 3k^2}{3} < \frac{k^3 + 3k^2 + 3k + 1}{3}$$ $$\frac{k^3}{3} < 1^2 + 2^2 + \cdots + k^2$$ $$\frac{(k + 1)^3}{3} < 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2$$ $$\frac{k^3}{3} + (k + 1)^2 < 1^2 + 2^2 + \cdots + k^2 + (k + 1)^2$$ $$\frac{k^3 + 3k^2 + 3k + 1}{3} < \frac{k^3 + 3k^2 + 6k + 3}{3}$$

Q4

$S_1$:

$$0 < \frac{1}{4} < 1^3$$

$S_k$:

$$1^3 + 2^3 + \cdots + (k - 1)^3 < \frac{k^4}{4} < 1^3 + 2^3 + \cdots + k^3$$

$S_{k + 1}$:

$$1^3 + 2^3 + \cdots + (k - 1)^3 < \frac{k^4}{4}$$ $$1^3 + 2^3 + \cdots + (k - 1)^3 + k^3 < \frac{(k + 1)^4}{4}$$ $$1^3 + 2^3 + \cdots + (k - 1)^3 + k^3 < \frac{k^4}{4} + k^3$$

But $\frac{k^4}{4} + k^3 = \frac{k^4 + 4k^3}{4}$ and $\frac{(k + 1)^4}{4} = \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4}$, therefore $\frac{k^4}{4} + k^3 &lt; \frac{(k + 1)^4}{4}$.

$$\implies 1^3 + 2^3 + \cdots + k^3 < \frac{(k + 1)^4}{4}$$

Likewise

$$\frac{k^4}{4} < 1^3 + \cdots + k^3$$ $$\frac{(k + 1)^4}{4} < 1^3 + \cdots + k^3 + (k + 1)^3$$

but

$$\frac{k^4}{4} + (k + 1)^3 < 1^3 + \cdots + k^3 + (k + 1)^3$$

and

$$\frac{(k + 1)^4}{4} = \frac{k^4 + 4k^3 + 6k^2 + 4k + 1}{4} < \frac{k^4}{4} + (k + 1)^3 = \frac{k^4 + 4k^3 + 12k^2 + 12k + 4}{4}$$ $$\implies \frac{(k + 1)^4}{4} < 1^3 + \cdots + (k + 1)^3$$

Q5

sage: bool((1/6)*k*(k + 1)*(2*k + 1) + (k + 1)**2 == (1/6)*(k + 1)*(k + 1 + 1)*(2*(k + 1) + 1))
True

Q6

sage: bool((k**2/4)*(k + 1)**2 + (k + 1)**3 == (1/4)*(k + 1)**2*(k + 1 + 1)**2)
True

Q7

\begin{align*} \frac{(n + 1)! - 1}{(n + 1)!} + \frac{n + 1}{(n + 2)!} &= \frac{(n + 2)! - 1}{(n + 2)!} \ &= \frac{(n + 2)! - (n + 2) + n + 1}{(n + 2)!} \ &= \frac{(n + 2)! - 1}{(n + 2)!} \end{align*}

Q8

$$n = 1$$ \begin{align*} F_2 F_3 - F_1 F_4 &= 1 \times 2 - 1 \times 3 \ &= -1 = (-1)^1 \end{align*}

Assume $S_k$ is true.

$S_{k + 1}$:

\begin{align*} F_{k + 2} F_{k + 3} - F_{k + 1} F_{k + 4} &= (F_{k + 1} + F_k) F_{k + 3} - F_{k + 1}(F_{k + 3} + F_{k + 2}) \ &= F_{k + 1} F_{k + 3} + F_k F_{k + 3} - F_{k + 1} F_{k + 3} - F_{k + 1} F_{k + 2} \ &= F_k F_{k + 3} - F_{k + 1} F_{k + 2} \ &= (-1) \cdot (F_{k + 1} F_{k + 2} - F_k F_{k + 3}) \ &= (-1) \cdot (-1)^k = (-1)^{k + 1} \end{align*}

D. Every Integral System Is Isomorphic to $\mathbb{Z}$

Q1

Ordered integral domain:

If $a &lt; b$ then $a + c &lt; b + c$ $$0 &lt; 1 \implies (n - 1) \cdot &lt; n \cdot 1$$ If $a &lt; b, b &lt; c$, then $a &lt; c$ $$0 &lt; n \cdot 1$$ Since $A$ is an integral system, every positive subset has a least element, so for $m &lt; n, m \cdot 1 &lt; n \cdot 1$

Q2

Injective: $h(m) = m \cdot 1 = h(n) = n \cdot 1$ $\implies m = n$ since in an integral system if $x \neq y$ then either $x &lt; y$ or $x &gt; y$, and each element of the mapping $h(n) = n \cdot 1$ is distinct.

Surjective: every element of an integral system is a multiple of 1 (page 210).

Q3

\begin{align*} h(m + n) = (m + n) \cdot 1 &= 1 + \cdots + 1 \ &= m \cdot 1 + n \cdot 1 \ &= h(m) + h(n) \ h(mn) &= mn \cdot 1 \ &= mn \cdot 1^2 \ &= (m \cdot 1)(n \cdot 1) \ &= h(m) h(n) \end{align*}

E. Absolute Values

Q1

$a \geq 0$ then $|a| = a$ and $|-a| = -(-a) = a$ $$\implies |-a| = |a|$$ $a &lt; 0$ then $|a| = -a$ and $|-a| = -a$ $$\implies |-a| = |a|$$

Q2

$$a \leq |a|$$

$a \geq 0$ then $|a| = a \implies a = |a|$

$a &lt; 0$ then $|a| = -a \implies a &lt; |a|$

Q3

$$a \geq -|a|$$

$a \geq 0$ then $-|a| = -a \implies a &gt; -|a|$

$a &lt; 0$ then $-|a| = a \implies a = -|a|$

Q4

$$b &gt; 0$$ $$|a| \leq b \iff -b \leq a \leq b$$ $a \geq 0$ then $|a| = a \implies a \leq b$ and $b &gt; 0$, then $-b &lt; 0$ but $a \geq 0$ so $a &gt; -b$

$a &lt; 0$ then $|a| = -a \implies -a \leq b$, but $a &lt; 0$ so $a &lt; -a$ and $a &lt; b$. Also $-a \leq b \implies a \geq -b$

For the opposite statement that $-b \leq a \leq b \implies |a| \leq b$

$a \geq 0$ then $|a| = a$ and $a \leq b \implies |a| \leq b$

$a &lt; 0$ then $|a| = -a$ and $-b \leq a \implies -a \leq b \implies |a| \leq b$

Q5

$$|a + b| \leq |a| + |b|$$

Let $\bar{a} = a + b$ and $\bar{b} = |a| + |b|$

$$\bar{a} = \bar{b} \implies |\bar{a}| \leq \bar{b}$$ $$|a + b| \leq |a| + |b|$$

Q6

$$|a - b| \leq |a| + |b|$$

$a \geq 0, b \geq 0$ then $|a - b| &lt; |a| + |b|$

$a \geq 0, b &lt; 0$ then $|a - b| = |a| + |b|$

$a &lt; 0, b \geq 0$ then $|a - b| = |a| + |b|$

$a &lt; 0, b &lt; 0$ then $|a - b| &lt; |a| + |b|$

Q7

$$|ab| = |a| \cdot |b|$$

$a \geq 0, b \geq 0$ then $|ab| = |a| \cdot |b|$

$a \geq 0, b &lt; 0$ then $ab &lt; 0, |ab| = -ab &gt; 0$ and $|ab| = |a| \cdot |b|$

$a &lt; 0, b \geq 0$: see above

$a &lt; 0, b &lt; 0$ then $ab &gt; 0, |ab| = |a| \cdot |b|$

Q8

$$|a| - |b| \leq |a - b|$$

From part 5:

$$|a + b| \leq |a| + |b|$$

Substitute into $a$, the expression $a - b$

$$|(a - b) + b| \leq |a - b| + |b|$$

$$|a| - |b| \leq |a - b|$$

Q9

From 4, $a \leq b \implies |a| \leq b$

$$|a - b| > 0$$

From 8, $||a| - |b|| \leq |a - b|$

F. Problems on the Division Algorithm

Q1

$$m = qn + r \qquad 0 \leq r < n $$

$$km = k(qn + r) \qquad 0 \leq kr < kn $$

So $q$ is quotient and $kr$ is remainder.

Q2

$$m = qn + r \qquad 0 \leq r < n$$ $$q = kq_1 + r_1 \qquad 0 \leq r_1 < k$$

$$m = n(kq_1 + r_1) + r = (nk)q_1 + (nr_1 + r)$$

We must show $nr_1 + r &lt; nk$, since this is the rule of the remainder.

Now $r_1 &lt; k \implies k - r_1 &gt; 0$ so $k - r_1 \geq 1$, $$ \implies n(k - r_1) \geq n $$ $$ \implies n + nr_1 \leq nk$$

But $r &lt; n$ so $nr_1 + r &lt; nk$

Q3

$$n \neq 0, m = nq + r, 0 \leq r < |n|$$

$$m \geq 0 \implies m \geq (0)n$$

$$m \geq nq$$

$$m < 0, n < 0 \implies -n \geq 1$$ $$\implies (-m)(-n) \geq -m$$

Add $-mn + m$ to both sides $$ m \geq (-m)n$$

$$m < 0, n > 0 \implies mn \leq m$$

In every case $m \geq nq$ where $n \neq 0$ and $q$ is an integer.

$$m \geq nq \implies m - nq = r \geq 0$$

$|n| &gt; 0$ so if $n \leq r$ then $r - |n| \geq 0$, but $r - |n| = m - |n|(q + 1)$.

But $m - |n|(q + 1) &lt; r$ which is impossible. So $r &lt; |n|$

Q4

\begin{align*} (nq_1 + r_1) - (nq_2 + r_2) &= n(q_1 - q_2) + (r_1 - r_2) \ &= 0 \end{align*}

Assume $r_2 \geq r_1$, otherwise switch the symbols. Then $r_2 - r_1 \geq 0$ $$\implies r_2 - r_1 = n(q_1 - q_2)$$

but $r_1 - r_1 &lt; n$ and $n &gt; 0$, so $r_1 - r_1 = 0$

Q5

$$n(q_1 - q_2) = 0, n > 0 \implies q_1 - q_2 = 0$$

$$q_1 = q_2$$ $$r_1 = r_2$$

Q6

$$m = nq + r \implies m = r (\mod n)$$

G. Law of Multiples

Q1

\begin{align*} 1 \cdot (a + b) &= a + b = 1 \cdot a + 1 \cdot b \ (n + 1) \cdot (a + b) &= n \cdot (a + b) + a + b \ &= n \cdot a + a + n \cdot b + b \ &= (n + 1) \cdot a + (n + 1) \cdot b \end{align*}

Q2

\begin{align*} (1 + m) \cdot a &= a + m \cdot a \ (n + 1 + m) \cdot a &= (n + m + 1) \cdot a = (n + m) \cdot a + a &= n \cdot a + m \cdot a + a \ &= (n + 1) \cdot a + m \cdot a \end{align*}

and vice versa

Q3

\begin{align*} (1 \cdot a)b &= ab = (1 \cdot b)a \ [(n + 1) \cdot a]b &= (n \cdot a + a) b\ &= n \cdot ab + ab \ &= (n + 1) \cdot ab \ &= [(n + 1) \cdot b] a \end{align*}

Q4

\begin{align*} m \cdot (1 \cdot a) &= m \cdot a \ m \cdot [(n + 1) \cdot a] &= m \cdot (n \cdot a + a) \ &= mn \cdot a + m \cdot a \ &= (mn + m) \cdot a \ &= [m(n + 1)] \cdot a \end{align*}

Q5

\begin{align*} k \cdot a &= (k \cdot 1)a \ (k + 1) \cdot a &= [(k + 1) \cdot 1] \cdot a \end{align*}

because $(k + 1) \cdot 1 = k \cdot 1 + 1$ and $1 \cdot a = a$

Q6

\begin{align*} (1 \cdot a)(m \cdot b) &= a(m\cdot b) = m \cdot ab \ [(k + 1) \cdot a](m \cdot b) &= (k \cdot a + a)(m \cdot b) \ &= (k \cdot a)(m \cdot b) + a(m \cdot b) \ &= km \cdot ab + m \cdot ab \ &= [(k + 1)m] \cdot ab \end{align*}

H. Principle of Strong Induction

Q1

$$k \in K \implies k + 1 \in K$$

Q2

by the statement above $S_k$ is true, implies all of $S_i$ is true for $i &lt; k$ and so $S_{k + 1}$ is true.

$k$ the integers for which $S_k$ is true so implies with the statement above and $S_n$ is true for every $n$.

By the well ordering principle $b \notin K$ is the least element. By i. $b \neq 1$ so $b &gt; 1$ but $b - 1 &gt; 0$ and $b - 1 \in K$.

Then by ii. $b \in K$ (contradiction).