# Algebra Problems Oct 24 # Outline Sections: - 1.4: $\mathbf{Z}/m\mathbf{Z}$, rings, integral domains, fields - 2.1: Rationals - 2.3: Rationals to reals - 2.4: Complex - 3.1: Euclidean Algorithm - 3.2: Roots of polynomials - 3.3: $\mathbf{Z}[x]$. Other topics from Exam 1 - Fermat's little theorem - Induction - Extended Euclidean algorithm $$\begin{aligned} a &=q_0 b+r_1 \\ b &=q_1 r_1+r_2 \\ r_1 &=q_2 r_2+r_3 \\ \vdots\, &= \,\, \vdots\qquad \vdots \\ r_{n-2} &=q_{n-1} r_{n-1}+r_n \\ r_{n-1} &=q_n r_n . \end{aligned}$$ - Fundamental theorem of arithmetic - Solving modular congruences - Ring axioms - Units in $\mathbf{Z}/m\mathbf{Z}$. # Practice: Arithmetic - Lemma 2.1. Let $a, b$, and $d$ be integers. If $d \mid a$ and $d \mid b$, then $d\mid(m a-n b)$ for any integers $m . n$. - Proof: write $a=kd$ and $b=\ell d$, then $ma-nb = mkd -nld = d(mk-nl)$. - Proposition 2.5. Suppose $p$ is prime and $p \mid a b$. Then $p$ must divide $a$ or $b$. - Proof: suppose $p\not\mid b$, so $(p, b) = 1$ and $1=t_1p + t_2 b$, then $a = t_1 ap + t_2 ab$. Then $p\mid t_1 ap$ and $p\mid t_2ab \implies p\mid a$. - Theorem 2.8. There are infinitely many prime numbers. - Proof: $N \:= \prod_{1\leq i\leq k} p_i+1$ is composite since it is bigger than $p_k$, but if $p_i\mid N$ then $p_i \mid N - \prod p_i = 1$, so $N$ is no divisible by any $p_i$, an contradiction. - Proposition $3.3$ (Fermat). If $p$ is any prime number and $n$ is any integer, then $n^p \equiv n(\bmod p)$. - Proof: induction. Check $(n+1)^p = \sum_{k=0}^n {p\choose k} n^k \equiv_p n^p+1 \equiv n+1$ since $p\mid {n\choose k}$ for each $0\leq k\leq p-1$. To prove this fact, write ${p\choose k} = {p!\over k! (p-k)!} = p{a\over b}$ where $a=(p-1)!$ and $b=k! (p-k)!$. Rearrange to get $pa = b{p\choose k}$, and since $p$ divides the LHS it divides the RHS and $p\mid b{p\choose k}$. Conclude $p\not\mid b$ since $b$ is a product of factors smaller than $p$, and since $p$ is prime, $p\mid {p\choose k}$. - Proposition 3.4. There are infinitely many primes of the form $4 k+3, k \in \mathbf{N}$ - Proof: suppose finitely many, set $N:= 4\prod_{i\leq k} p_i - 1 \equiv_4 -1 \equiv_4 = 3$. Note $N$ is odd, suppose it is prime, then $2\not\mid N$ and only odd primes divide it. Write $N = \prod_{i\leq q} \pi_i^{\alpha_i}$, then $\pi_i^{\alpha_i} \not\equiv_4 0, 2$. If $\pi_i^{\alpha_i}\equiv_4 1$ for all $i$ then $N\equiv_4 1$ since $\prod t_i \mod m \equiv \prod(t_i\mod m)$. So not all are 1 and at least on $\pi_{i_0}^{\alpha_{i_0}}\equiv_4 -1$. The primes $p_i$ were a finite list, so $\pi_{i_0} = p_i$ for some $i$. But no $p_i$ can divide $N$, a contradiction. - Corollary 3.6. If $p$ is prime and $p$ does not divide $c$, then the congruence $c x \equiv b(\bmod p)$ always has a solution (which is unique $\bmod p)$, namely $x \equiv_p [c^{-1}]_p\cdot b$. - Since $(p,c)=1$, write $1 = t_1 p + t_2c \implies b= bt_1 p + bt_2 c \implies b \equiv_p bt_2 c := cx$ where $x:= bt_2$. - Examples: - Show $8x \equiv_{35} 11 \implies x \equiv_{35} -143 \equiv_{35} -3$. - Show $6x \equiv_{75} 9 \implies x\equiv_{75} 14, 39, 64$. Set $d = (6, 75) = 3$, reduce to solving $2x\equiv_{25} 3$, write $1= (-12)2 + (1)25 \implies 1 \equiv_{25} (-12) 2\equiv_{25}14$ so $x\equiv_{25} 14$. # Rings Review: - $(R, +)$ is a commutative group (associative, commutative, identity, inverses) and $(R, \cdot)$ is a monoid (associative, identity) with compatibility $a(b+c) = ab + ac$ (distributive). - Zero divisors: $ab=0$ with $b\neq 0$ means $a$ is a zero divisor. - Integral domains: commutative rings with no zero divisors. - Subring criterion: $H \subseteq R$ is a subring iff $H\neq 0, H\pm H\subseteq H, HH \subseteq H, -H\subseteq H$ ## Examples Exercise: p. 41, 48, 91 - Define a ring. - Soln: A ring $(R,+, \times)$ is an abelian group $(R,+)$ endowed with a multiplication $\times: R \times R \rightarrow R$ such that - $(x y) z=x(y z)$ for all $x, y, z \in R$; - $(x+y) z=x z+y z$ and $x(y+z)=x y+x z$ for all $x, y, z \in R$ - there is an element $1 \in R$, called the identity with the property that $1 . x=x .1=x$ for all $x \in R$. - The element $a+n \mathbf{Z}$ in $\mathbf{Z} / n \mathbf{Z}$ is a unit if and only if $\ldots$ - Soln: $a$ and $n$ are relatively prime, i..e, their greatest common divisor is 1 . - Write $[36]$ for the image of the integer 36 in $\mathbf{Z}_{60}$ and let $R$ denote the subset of $\mathbf{Z}_{60}$ consisting of all multiples of $[36]$. Explain why $R$ is a ring and determine the identity element of $R$. - All multiples of 36 form an ideal, the principal ideal generated by 36 , so $R$ is an additive group under $+$ and closed under $\times$ (i.e., a product of two elements in $R$ is in $R$ ), so we only need check $R$ has an identity. Since $36+36=12$ in $\mathbf{Z}_{60}$ and $36=12+12+12, R$ is also the additive group generated by 12 . Now $12 \times 36=12 \times 6 \times 6=72 \times 6=12 \times 6=72=12$, so $1_R=36$. OR For the last step you could just observe that $36 \times 36=$ $9 \times 9 \times 4 \times 4=21 \times 4 \times 4=84 \times 4=24 \times 4=96=36$ so $1_R=36$ - Write a general element of $\mathbf{Z}[2^{1\over 3}]$. - Soln: $\alpha = 2^{1\over 3} \implies x = a_0 + a_1 \alpha + a_1\alpha^2$ with $a_i\in \mathbf{Z}$. - For a general ring $R$, define the extension $R[\alpha]$ for $\alpha\in S$ where $R$ is a subring of $S$. - Soln: $$R[a]=\left\{r_0+r_1 a+r_2 a^2+\cdots+r_n a^n \mid r_0, \ldots, r_n \in R, n \geq 0\right\}$$. Alternatively, this is the smallest subring of $S$ containing $R$ and $\alpha$, i.e. the intersection of all such subrings. - Write down all of the elements in $$R=\left\{\left(\begin{array}{ll}a & b \\ 0 & a\end{array}\right) \mid a, b \in \mathbf{Z}_2\right\} \subset M_2\left(\mathbf{Z}_2\right)$$. Is $R$ commutative? What are the additive and multiplicative inverses of all elements? Is $R$ an integral domain? Is $R$ a field? - Soln: $0=\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right), \quad 1=\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right), \quad x=\left(\begin{array}{ll}0 & 1 \\ 0 & 0\end{array}\right), \quad 1+x=\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right)$. - Show $\mathbf{Z}/5\mathbf{Z}$ is a field and $\mathbf{Z}/6\mathbf{Z}$ is not an integral domain using multiplication tables. - Give an example of a zero divisor in the rings (a) $\mathbf{Z} /(12)$; (b) The matrix ring $\mathrm{Mat}_{2\times 2}(\mathbf Q)$ - Find all the zero divisors in the ring $\mathbf{Z} /(12)$. - Show that $\mathbf{Z}/m\mathbf{Z}$ is an integral domain iff $m$ is prime, in which case it is a field. - Proof: if $m$ is composite, factor as $m=qr$ to get $qr \equiv_m 0$ with $q,r \not\equiv_m 0$. Conversely if $m=p$ then try to solve $ax\equiv_p 1$: this has a solution iff $(a, p) = 1$, which is true for any $a$ since $p$ is prime. - Give an example of a noncommutative ring (prove it is a ring and prove it it not commutative). - E.g. $\mathrm{Mat}_{2\times 2}(\mathbf{Z})$ with $\mathrm{SL}_2(\mathbf{Z})$ elements $x$ and $y$. - Proposition 1.4. Given any two distinct rational numbers, there is another rational number between them. - Proof: for $r > s$ rational, take $z = {r+s\over 2}$ and show $r>z>s$. Trick: $r = {r\over 2} + {r\over 2} > {r\over 2} + {s\over 2} = z$. - Show $\sqrt{2}$ is irrational. - Show by example that if $R$ is not a domain then $R[x]$ need not be a domain. - Write a general element of $\mathbf{Q}[\sqrt 2, i]$. - Show $\mathbf{Q}[\sqrt{3} + i] = \mathbf{Q}[\sqrt 3, i]$. - Proof: $\alpha := \sqrt{3} + i$ implies $\alpha^3 = 8i$ so that $i\in \mathbf{Q}[\alpha]$. Then check $\sqrt 3 = \alpha-i = \alpha - {1\over 8} \alpha^3\in \mathbf{Q}[\alpha]$, so $\mathbf{Q}[\sqrt 3, i] \subseteq \mathbf{Q}[\alpha]$. Then clearly $\mathbf{Q}[\alpha] \subseteq \cdots$, so equal. - Show that $\mathbf{Q}[\sqrt d]$ is a field: show identities, commutativity, inverses. - Soln: $\alpha := a+b\sqrt{d}$, check $\alpha\bar\alpha := (a+b\sqrt d)(a-\sqrt d) = a^2 +b^2d := |\alpha| \in \mathbf{Q}$ so $\alpha {\bar \alpha \over |\alpha|} = 1$ and $\alpha^{-1} = \bar{\alpha}/|\alpha|$. Check $|\alpha|\neq 0$ when $\alpha\neq 0$ so this is well-defined. - - - Give an example of an irreducible polynomial $f(x) \in \mathbf{F}[x]$ having degree at least 2 where $\mathbf{F}$ is as below: (a) $\mathbf{R}$; (b) $\mathbf{Q}$; (c) $\mathbf{Z} /(2)$; (d) $\mathbf{Z} /(3)$ : - - Let $f(x)=x^2+x+1$. Is $f(x)$ irreducible when regarded as an element of (a) $\mathbf{R}[x]$; (b) $\mathrm{Q}[x]$; (c) $\mathbf{Z} /(2)[x]$; (d) $\mathbf{Z} /(3)[x]$; (e) $\mathbf{Z} /(5)[x]$. - L - Give an example of a finite field with exactly 9 elements. Solution: An example is $\mathbf{Z}_3[x] /\left\langle x^2+1\right\rangle$. - Check if these polynomials are irreducible over $\mathbf{Q}$: - $f(x)=x^3+2 x+20$ (yes, RRT or mod $p$) - $g(x)=x^{14}-6 x+75$ (yes, Eisenstein with $p=3$) - (yes, irreducible $\mod 2$, using that the only irreducible quadratic there is $x^2+x+1$). - Let $R$ be the ring $\mathbf{Z}_2 \times \mathbf{Z}_3$. Is the set $\mathbf{Z}_2 \times\{0\}$ a subring? Explain. - Is every field a domain? Explain. - Show that $\mathbf{Z}_2 \times \mathbf{Z}_3$ is the only ring with 6 elements (up to isomorphism). - - Is $\{0,1,2,3,4, \ldots\}$ a subring of $\mathbf{Z}$ ? - Is $\{1,2,3\cdots\}$ a subring of $\mathbf{Z}$? - False, does not contain an additive identity. - Is the subset of all odd integers a subring of $\mathbf{Z}$? - False: not closed under $+$. - If $R$ is a ring, is the set $Z(R) = \{ x\in R \mid xr=rx \, \forall r\in R\}$ a subring? - True. - Let $$R=\left\{\left(\begin{array}{ll} a & b \\ 0 & a \end{array}\right) \mid a, b \in \mathbb{Z}_2\right\}$$, is this a ring? Is it commutative? - True, true. - Is $\mathrm{GL}_n(k)$ a subring of $\mathrm{Mat}_{n\times n}(k)$? - False: it is not a group under $+$ because it doesn't contain 0. More generally, it is not closed under $+$ because a sum of invertible matrices need not be invertible. Think of an example. - Give an example of a ring with infinitely many elements that is not a domain. - Define a new addition and multiplication on $\mathbf{Z}$ as follows: $$ a \oplus b=a+b-3 \quad a \odot b=3 a+3 b-a b-6, $$ where the operations on the right-hand sides of these equations are the usual operations in $\mathbf{Z}$. To avoid confusion write $R$ for $\mathbf{Z}$ with this new ring structure. The operations $\oplus$ and $\odot$ make $R$ a commutative ring with identity. The zero element for this new addition is ... - The identity element for this new multiplication is ... - The negative of an element $a$ with respect to this new addition is ... - The $n$-fold sum $a \oplus a \oplus \cdots \oplus a$ is... - What is wrong with the following argument: The polynomial $x^2-10$ is irreducible in $\mathbf{F}_{13}[x]$ because its zeroes, namely $\pm \sqrt{10}$, are in $\mathbf{C}$, not $\mathbf{F}_{13}$. - An element $a$ in a commutative domain $R$ is irreducible if ... - Let $K$ be an extension field of $k$. Define the minimal polynomial of an element $a$ in $K$ and explain why it must be irreducible. - The greatest common divisor of two non-zero polynomials $a, b \in k[x]$ is $\ldots$ - In $\mathbf{F}_5$ the greatest common divisors of 2 and 4 are ... - An element $a$ in a commutative domain $R$ is irreducible if ... - Write $x^{11}-1$ as a product of irreducible polynomials in $\mathbf{F}_2[x]$. - If in a ring $R$ every $x \in R$ satisfies $x^2=x$, prove that $R$ must be commutative (A ring in which $x^2=x$ for all elements is called a Boolean ring). - Solution: Let $x, y \in R$. Then $(x+y)^2=(x+y)(x+y)=x^2+$ $x y+y x+y^2$ Since $x^2=x$ and $y^2=y$ we have $x+y=x+x y+y x+y$. Hence $x y=-y x$. But for every $x \in R$ $$(-x)=(-x)^2=(-x)(-x)=x^2=x$$ Hence $-y x=y x$ i.e. we obtain $x y=y x$. - Prove that any field is an integral domain. - Solution: Let $a \neq 0$ and $b$ be two elements in the field $F$ and $a b=0$. Since $F$ is a field and $a \neq 0$. we have $a^{-1} \in F$. Hence $a^{-1} a b=$ $a^{-1} 0=0$. So we obtain $b=0$. Hence there exists no zero divisor in $F$. - Show that the commutative ring $D$ is an integral domain if and only if for $a, b, c \in D$ with $a \neq 0$ the relation $a b=a c$ implies that $b=c$ - Solution: If $D$ is a commutative ring and $a \neq 0$, then $a b=a c$ implies $a(b-c)=0$. Since $a \neq 0$ we obtain $b=c$. Conversely assume that $a b=a c$ and $a \neq 0$ implies that $b=c$. Assume if possible that $a \neq 0$ and $a b=0$ Then $a b=a 0$ and hence $b=0$ - Let $D$ be an integral domain, $a, b \in D$. Suppose that $a^n=b^n$ and $a^m=b^m$ for two relatively prime positive integers $m$ and $n$. Prove that $a=b$. - Solution: We may embed the integral domain into a field. If $a$ is zero then $b$ must be zero. Assume that $a$ is non-zero then $a$ has inverse in the field. Since $m$ and $n$ are relatively prime there exists $x$ and $y$ in $\mathbf{Z}$ such that $m x+n y=1$. Since one of the integers may be negative we may need to use th e fact that we can embed $D$ into its field of fractions. Then $a=a^{m x+n y}=a^{m x} a^{n y}=b^{m x} b^{n y}=b^{m x+n y}=b$ as required. Remark: The above equation makes sense in the field but does not make sense in the domain as the negative power of an element does not make sense in $D$. - Let $R$ be a ring, possibly non commutative, in which $x y=0$ implies $x=0$ or $y=0$. If $a, b \in R$ and $a^n=b^n$ and $a^m=b^m$ for two relatively prime positive integers $m$ and $n$, prove that $a=b$. - Solution: $(m, n)=1$, implies that, there exists $u, k \in \mathbf{Z}$ such that $m u+n k=1$. Since $m, n \geq 0$ either $u \geq 0$ or $k \geq 0$. Assume that $u>0$. Then $m u-n k=1$ where $k>0$. Hence $m u=n k+1$. Now, let $a^{m u}=\left(a^m\right)^u=\left(b^m\right)^u=b^{m u}$ $b^{n k+1}=a^{m u}=a^{n k+1}=a a^{n k}=a\left(a^n\right)^k=a\left(b^n\right)^k=a b^{n k}$ Hence $b b^{n k}=a b^{n k}$ implies that $(b-a) b^{n k}=0$. Then either $b^{n k}=0$ or $b=a$. The first possibility $b^{n k}=0$ is impossible if $b \neq 0$. One can see this easily that, if $t$ is the smallest positive integer such that $b^{t-1} \neq 0$, but $b^t=0$, then $0=b^t=b^{t-1} . b \neq 0$. This implies that the assumption $b^t=0$ is impossible, whenever $b \neq 0$. Hence $b=a$. (In the above solution we assume $u>0$, if $k>0$, then we can continue the solution by changing the symbols $u$ and $k$, in the above solution.) - Prove that the extended Euclidean algorithm computes the gcd: $r_n=(a, b)$ where $$ \begin{aligned} b=& q_0 a+r_1 \text { where } d\left(r_1\right)