# DRP Notes $$ \newcommand{\ZZ}[0]{\mathbb{Z}} \newcommand{\QQ}[0]{\mathbb{Q}} \newcommand{\CC}[0]{\mathbb{C}} \newcommand{\ideal}[0]{\trianglelefteq} $$ ## Definitions - **Monoids**: a monoid is a set $S$ with some binary operation $\star$, thought of as a function $\star: S\times S\to S$ which takes ordered pairs of elements $(x, y)$ with $x\in S, y\in S$, and pairs them to produce a new element in $S$ that we call $x\star y$. We do not necessarily require inverses, but we do require - Closure, so that $x\star y$ is always another element of $S$ (and not some larger universe), - Associativity, so $(x\star y)\star z = x\star(y\star z)$ - An identity element $\mathbf{e}$, satisfying $x\star \mathbf{e} = x$ and $\mathbf{e} \star x = x$ for all $x\in S$. - E.g. $\mathbb{N}$ is a monoid but not a ring, since we don't have additive inverses in the universe $\mathbb{N}$. Explicitly, $5\in \mathbb{N}$ but $-5\not\in \mathbb{N}$. - **Rings**: a **ring** $R$ is a set with two monoid operations which we call $+$ and $\cdot$. We require - $(R, +)$ is a commutative monoid, so $x+y=y+x$ always, with identity called $0$, inverses which we call $-x$ for $x\in R$, so that $x + (-x) = 0$ and $(-x)+x = 0$. - $(R, \cdot)$ is just a monoid, which may or may not have inverses, and may not be commutative, so $xy\neq yx$ in general. We call the identity $1$, which satisfies $x\cdot 1 = x$ and $1\cdot x = x$ for all $x\in R$. - Compatibility of the two monoid operations in the form of the distributive law: $$ x\cdot(y+z) = x\cdot y + x\cdot z \quad \forall x,y,z\in R $$ - E.g. $\mathbb{Z}, \mathbb{R}, \mathbb{C}, \cdots$, $n\times n$ matrices over $\mathbb{R}$, the sets $\ZZ/n$ under modular arithmetic. - E.g. the Gaussian integers $\ZZ[i] = \{a+bi \mid a, b\in \ZZ, i^2=-1\}$ - **Divisibility**: if $r$ admits a decomposition of the form $r=st$, we say $r$ is **divisible** by $t$ (and also divisible by $s$). Mnemonic: $r=st \implies s = "{r\over t}"$. - Notation: if $a=bc$ we write $b\mid a$ ($b$ divides $a$) and $c\mid a$ ($c$ divides $a$). Conversely, if $b\mid a$, we can always write $a=bt$ for some $t$. - Example: $10 = 5\cdot 2$ in $\ZZ$, so both $5$ and $2$ divide 10. Conversely, since we know $2\mid 10$, we know there is some $t\in \ZZ$ so that $10=2t$. - **Units**: an element $u\in R$ is a **unit**, notated $r\in R^\times$, if $u$ has a well-defined two-sided multiplicative inverse $u^{-1}$ satisfying $u\cdot u^{-1} = 1$ and $u^{-1} u = 1$. - Example: $u = 3$ is a unit in $\ZZ/10$, since setting $u^{-1} = 7$ provides an inverse: $3\cdot 7 \equiv 21 \equiv 1 \mod 10$, and $7 \cdot 3 \equiv 21 \equiv 1 \mod 10$. - $u=2$ is *not* a unit in $\ZZ/10$ -- one can exhaustively check the products $2x$ for all 10 elements $x$ in $\ZZ/10$. Alternatively, just observe that $2x$ remains even $\mod 10$ while we would need $2x \equiv 1 \mod 10$ which is odd for there to be an inverse. - Example: $\ZZ^\times = \{1, -1\}$. - **Associates**: two elements $r,s\in R$ are **associates** if $r=us$ for $u\in R^\times$ a unit. - Example: $3$ and $-3$ are associates in $\ZZ$, since we can write $3 = -1\cdot (-3)$, i.e. we set $r=3, s=-3, u=-1$ in the definition. - Example: in $\ZZ[i]$, $r=-1+i$ and $s=1+i$ are associates since we can take $u=i$ to write $$ r = -1+i = i^2 + i = i(1 + i) = u s $$ - This says that $r$ is divisible by $s$, and moreover the "quotient" is a unit. - **Reducible**: an element $r\in R$ is **reducible** if it admits *some* decomposition $r=st$ where neither $s$ nor $t$ are units. If $r$ admits no such decomposition, we say $r$ is **irreducible**. - This says that $r$ is divisible by some pair of non-units. - Example: $6\in \ZZ$ is reducible since $6=2\cdot 3$, neither of which are units in $\ZZ$. - **Prime**: an element $p\in R$ is **prime** if whenever $p\mid ab$ for some elements $a, b\in R$, we must have $p\mid a$ or $p\mid b$ (or both). - Eg. $2\in \ZZ$ is prime. For example, we know $2\mid 20$ and we can factor $20 = 4\cdot 5$, and $2$ must divide one of the factors. - E.g. $r = 1+\sqrt{-3}\in \ZZ[\sqrt{-3}]$ is not prime: one just needs to find a case where $r\mid ab$ but $r$ doesn't divide either of $a$ or $b$. Check that $r\bar{r} = |r|^2 = 4$ (taking the complex conjugate) so that $r\mid 4=2\cdot 2$, but $r\not\mid 2$. Why? Write $rs = 2$, so $(1+\sqrt{-3})(a+b\sqrt{-3}) = 2$ and FOIL to get $$ 2 = (1+\sqrt{-3})(a+b\sqrt{-3}) = (a - 3b) + (a+b)\sqrt{-3} \\ \implies a-3b = 2,\quad a+b=0 \\ \implies (-b)- 3b = 2 \implies -4b=2 ,$$ which has no solutions $a, b\in \ZZ$. - **Ideals**: we say that a subset $I \subseteq R$ is an **ideal** of $R$ and write $I\ideal R$, if $I$ is closed under addition (so $a, b\in I\implies a+b\in I$) and absorbing under multiplication (so $a\in I, r\in R \implies ra\in I$). - E.g. the even integers $2\ZZ = \{\cdots, -4, -2, 0, 2, 4, 6,\cdots\}$ are an ideal in $\ZZ$. - **Generating elements** given (say) two elements $r, s\in R$, the **ideal generated by $r$ and $s$**, is defined as $$ \left< r, s \right> = \{ rx + sy \mid x,y\in R\} .$$ I.e., this is the set of all "$R$-linear combinations" of the elements $r$ and $s$. Mnemonic: the $r, s$ are like vectors in a vector space, and the $x,y$ are like scalars, so we're taking the "subspace" spanned by $r$ and $s$. - An ideal generated by 3 or more elements is defined similarly. - E.g. the ideal $\left< 1\right> = \{1\cdot x \mid x\in R\} = R$, the entire ring. More generally, an ideal whose generator is any unit will just give you back the entire ring. - E.g. the ideal $\left< 2\right> \ideal \ZZ$ is exactly what we've been calling $2\ZZ$, the even numbers. - E.g. $\left<2, 3\right> = \{2x + 3y \mid x, y\in \ZZ\}$. It in fact turns out that $\left< 2, 3\right> = \left< 1 \right> = \ZZ$, all of the integers, because we can solve the Diophantine equation $2x+3y=1$ and scale up to get any $n\in \ZZ$. Pick your favorite $n$, then to show $n\in \left<2, 3\right>$, we need to find $x,y$ such that $n=2x+3y$. First solve $2x+3y=1$, then $$ \begin{align*} 2x + 3y = 1 &\implies n\cdot (2x+3y) = n\cdot 1\\ &\implies 2(nx) + 3(ny) = n \\ &\implies 2x' +3y' = n \quad x'= nx, y'=ny \\ &\implies n\in \left<2, 3\right> \end{align*} $$ - Warning: not every ideal $I$ is generated by *finitely* many elements, so it's not always the case that we can write $I = \left$. This motivates the next definition: - **Principal ideals**: we say an ideal $I \ideal R$ is **principal** if it is generated by a single element, and can thus be written $I = \left$ for some $r\in R$. We say a ring $R$ is a **principal ideal domain** if every ideal is principal. This is often abbreviated by saying $R$ is a **PID**. (These are very nice rings indeed!) - **Norms**: given a number ring $\ZZ[\sqrt{-d}]$ (where $d$ is assumed squarefree, otherwise we could factor out the square), thought of as a lattice inside of $\CC$, we define the **norm** of an element as $$ \begin{align*} N(a+b\sqrt{-d}) &= (a+b\sqrt{-d})\overline{(a+b\sqrt{-d})}\\ &= (a+b\sqrt{-d})(a-b\sqrt{-d}) \\ &= a^2 + db^2 \end{align*} $$ - **Unique factorization**: a ring $R$ is a **unique factorization domain** (abbreviated **UFD**)) if every element $r\in R$ admits a decomposition into irreducibles times a unit: $$ r = u p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n} $$ Moreover, this factorization is unique in the sense that if $r$ admits any other such factorization $r=u' \prod_{i=1}^m q_i^{k_i}$, then - $m=n$, so there are the same number of irreducible factors. - The $q_i$ can be reordered so that each pair $(p_i, q_i)$ are associates. - Note that in $\ZZ$, we technical have two factorizations of numbers into irreducibles, e.g. $6 = 2\cdot 3 = (-2)\cdot(-3)$, but the pair $(2, -2)$ are associates. - Note: not every ring is a UFD. The easy example is $\ZZ[\sqrt{-5}]$, whence $$ 6= 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) ,$$ which are two distinct factoriations into irreducibles. (To check that these factors are *really* irreducible, use the norm!) - **Euclidean domains**: a ring $R$ is a **Euclidean domain** if it admits a "size" function $\sigma:R\to \ZZ$ such that whenever $x,y\in R$ are nonzero, there exist a quotient $q$ and a remainder $r$ such that one can write $$ x = yq + r \quad \text{ where } r=0\text{ or }\sigma(r) < \sigma(y) $$ - E.g. $\ZZ$ with the usual absolute value $|n|$. - Polynomials $\ZZ[x] = \{a_0 + a_1x + a_2x^2 + \cdots +a_nx^n\mid a_i\in \ZZ, n\in \NN \}$ in $x$ with the degree function $\deg(a_nx^n+\cdots) = n$. ## Irreducible doesn't always imply prime The main warning: in *most* rings, prime $\implies$ irreducible, but only in very nice rings does irreducible $\implies$ prime. In $\ZZ$, we have prime $\iff$ irreducible. In $\ZZ[\sqrt{-5}]$ for example, there are irreducible elements which are not prime! Take $r = 2$, this is irreducible because if $2$ has a factor of the form $a + b\sqrt{-5}$, we can use the property of norms: $$ r\mid s \in \ZZ[\sqrt{-5}] \implies N(r) \mid N(s) \in \ZZ .$$ However, $N(a+b\sqrt{-5}) = a^2 + 5b^2$ would have to divide $N(2) = 2\bar{2} = 4$ (nontrivially), so we'd need an integer solution to the following Diophantine equation: $$ 2 = a^2 + 5b^2 .$$ But this has no integer solutions, by just plugging in small integer values of $a$ and $b$ and noting when they get too large. So $2$ is irreducible. However, $2$ is *not* prime, since we can write $$ 2\mid 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5}) ,$$ so $2$ divides a certain product, but I claim it doesn't divide either factor. This is again clear by using the norm: if $2\mid 1\pm \sqrt{-5}$ in $\ZZ[\sqrt{-5}]$, $$ 2\mid 1\pm \sqrt{-5} \hspace{9em} \in \ZZ[\sqrt{-5}]\\ \implies N(2) \mid N(1\pm \sqrt{-5}) \hspace{0.5em} \in \ZZ \\ \implies 4 \mid 1^2 + 5^2 = 6 \hspace{3em} \in \ZZ ,$$ which is a contradiction. ## Irreducible implies prime in PIDs **Theorem**: if $R$ is a PID and $r\in R$ is irreducible in $R$, then in fact $r$ is prime in $R$. **Proof**: First we set up the definition of prime: suppose $r\mid ab$, we then need to show that $r\mid a$ or $r\mid b$. Define $I = \left = \{rx+ay \mid x,y\in R\}$. Since $R$ is principal, every ideal can be generated by a single element, so write $I = \left = \{dt\mid t\in R\}$ for some $d$. Note that $r\in I = \left$ in particular, so we can write $r = dt_0$ for some $t_0\in R$. Since $r$ was irreducible, it can not admit a nontrivial decomposition, so one of $d$ or $t_0$ must be a unit. **Case 1**: if $d$ is a unit, then $\left = \left = R$ is the entire ring. Since in particular $1\in R$, we can write $$ 1 = rx + ay \text{ for some }x,y\in R .$$ Now scale this up by the parameter we haven't used: $$ b = brx + bay .$$ Now clearly $r\mid brx$, since $r$ occurs as a factor, and $r\mid bay$ since $r\mid ab$ was one of our assumptions. So $r$ divides the RHS of the above equation, and thus must divide the LHS, we get $r\mid b$, and we're done. **Case 2**: if $d$ is not a unit, then $t_0$ must be a unit. If two elements differ by a unit, they generate the same ideal, and since $r=dt_0$ we have $\left = \left = I = \left$. In particular, $a\in I = \left$, so we can write $a=rt_1$, which by definition means that $r$ divides $a$ (since it appears as a factor of $a$). $\Box$ ## Bezout's Identity Recall that $d=\gcd(a, b)$ means that $d\mid a$, $d\mid b$, and $d$ is the *greatest* such divisor in the sense that if $d'\mid a$ and $d'\mid b$ for some other $d'$, then $d'\mid d$ (and in particular $d'\leq d$). **Theorem** (Bezout's Identity): Let $a, b\in \ZZ$ and $d=\gcd(a, b)$. Then there exist $x, y\in \ZZ$ solving the linear Diophantine equation $$ ax + by = d .$$ Equivalently, the following line has at least one integer lattice point $(x, y)$ in $\ZZ^2 \subseteq \mathbb{R}^2$: $$ L: ax + by - d = 0 $$ **Theorem** (Solvability of the linear Diophantine equation): Fix $a, b, c\in \ZZ$, and consider the equation $$ ax+by=c .$$ This admits solutions $(x, y)\in \ZZ^2$ if and only if $c\mid \gcd{a, b}$. Moreover, if there is a single solution $(x_0, y_0)\in \ZZ^2$, there are infinitely many, parameterized in the following form: $$ \left\{ [x_0, y_0] + t\left[{b\over d}, - {a\over d} \right]\mid t\in \ZZ \right\} $$ *Proof*: We want to produce solutions to $ax+by=c$. $\implies$: We want to show $A\implies B$ where $A$ is "$ax+by=c$ admits solutions" and $B$ is "$c\mid d = \gcd(a, b)$". Equivalently, we can show $\not B\implies \not A$. Now just note that if $d\not\mid c$, there can be no solutions: since $d\mid a$ and $d\mid b$, so $d$ divides the LHS and would have to divide the RHS. $\impliedby$: Now suppose $c\mid d = \gcd(a, b)$. Take the equation $$ \begin{equation} ax+by=c \qquad (1) \end{equation} $$ and divide through by $d$ to obtain $$ \begin{equation} {a\over d}x + {b\over d}y = {c\over d} \qquad (2) \end{equation} $$ Any solution to (2) will yield a solution to (1), so we've reduced to finding solutions to (2). Note that $\gcd\left({a\over d}, {b\over d}\right) = 1$, since we've divided out by their gcd, so we can consider equations of the form $$ ax + by = c \qquad \gcd(a, b) = 1 ,$$ where we've replaced $a$ with ${a\over d}$, etc. To find solutions, we first attempt to solve the equation $$ ax+by=\gcd(a, b) = 1 .$$ Bezout's identity tells us that such solutions exist. However, we can always explicitly find solutions by using the extended Euclidean algorithm. Given such an $x,y$, we then scale up by $c$: $$ ax+by = 1 \implies cax + cby = c ,$$ so we can take $(x_0, y_0) = (cx, cy)$ as a particular solution. To get the general solution, note that if $(x_1, y_1)$ and $(x_2, y_2)$ are any two solutions, we have $$ ax_1 + by_1 = c \\ ax_2 + by_2 = c \\ \implies a(x_1 - x_2) + b(y_1 - y_2) = c-c = 0 \\ \implies a(x_1 - x_2) = -b(y_1 - y_2) \\ \implies {a\over b} = - {y_1 - y_2\over x_1 - x_2} .$$ Now we have an equivalence of two rational numbers in $\QQ$, and in general if $p_1/q_1 = p_2/q_2\in \QQ$ then we have $p_1 = tp_2$ and $q_1 = tq_2$, i.e. two presentations of a rational number as a fraction can only differ if one them is not a reduced fraction. This lets us write $$ y_1 - y_2 = -at \implies y_1 = -at + y_2 \\ x_1 - x_2 = bt \implies x_1 = bt+x_2 ,$$ so $y_1$ is obtained from $y_2$ by adding multiples of $-a$, and $x_1$ from $x_2$ by adding multiples of $b$. This says that if we start with a given solution (x_2, y_2)$, we can obtain all solutions as $$ [x_1, y_1] = [x_2 + bt, y_2 - at ] ,$$ which can be rewritten as a vector equation $$ [x_1, y_1] = [x_2, y_2] + t[b, -a] .$$ Unwindering everything, for the original equation (1), undoing the scaling by $d$, if we have an initial solution $(x_1, y_1)$, we get all solutions as $$ [x_1, y_1] = [x_2, y_2] + t\left[{b\over d}, -{a\over d}\right] .$$ $\Box$ ## Theorem: Prime $\iff$ irreducible in $\ZZ[i]$ *Proof* To prove this, use the fact that "prime $\iff$ irreducible" holds in PIDs, every ED is a PID, and $\ZZ[i]$ is an ED. We need to introduce a division algorithm and a remainder function. Fix $\alpha, \beta \in \ZZ[i]$, we then seek to write $$ \alpha = \beta q + r \qquad |r| = 0 \text{ or }|r| < |\beta| $$ The key idea: we may not be able to for $\alpha/\beta = \alpha\beta^{-1}$, since $\beta$ may not be a unit (so not invertible) in our universe, although they may become invertible once we pass to $\CC$. So $q$ is supposed to be a good approximation of $\alpha/\beta$ in our smaller ring $\ZZ[i]$. The trick is to go up to $\CC$, consider the exact quotient there, and choose a lattice point in $\ZZ[i] \subseteq \CC$ closest to $\alpha/\beta \in \CC$. Write $\alpha = a+bi$ and $\beta = c+di$, then check that $$ \begin{align*} {\alpha\over \beta} &= {\alpha\bar\beta \over \beta\bar\beta} \\ &= {\alpha\bar\beta \over |{\beta}|^2} \\ &= {(a+bi)(c-di) \over c^2 + d^2} \\ &= {ac+bd\over c^2+d^2} + i\,{bc-ad \over c^2 + d^2} \\ &= Q + iP \end{align*} ,$$ where now $Q, P\in \QQ$. Now round $Q$ to $x$, the nearest integer, and $P$ to $y$, its nearest integer. If either $P$ or $Q$ is $1/2$, pick arbitrarily which way to round -- we don't require uniqueness for the division algorithm/function in an ED, only existence! Now set $q=x+iy$ $$ \alpha = \beta q + r \implies \alpha - \beta q = r ,$$ so $r = \alpha-\beta q$ is forced upon us by this choice. We now just need to check the size of the remainder: $$ \begin{align*} |r| &= |\alpha - \beta q| \\ &= \left|\beta \left( {\alpha\over \beta} - {\beta q\over \beta}\right) \right| \\ &= |\beta| \cdot \left| {\alpha\over \beta} - q \right| \\ &\leq |\beta| \cdot 2^{-{1\over 2}} \\ &< |\beta| \end{align*} ,$$ which is exactly what's needed to $|\cdots|$ to be a Euclidean function. The only remaining question: where did ${1\over 4}$ come from? Recall that $q=x+iy$ where $x$ was rounded from $P$ and $y$ from $Q$, where $\alpha =P+iQ$. So $|x-P| \leq {1\over 2}$ and $|y-Q| \leq {1\over 2}$, and we have $$ \begin{align*} \left|{\alpha\over \beta} - q\right|^2 &= \left| (P+iQ) - (x+iy)\right|^2 \\ &= | (P-x) - i(Q-y)|^2 \\ &= (P-x)^2 + (Q-y)^2 \\ &\leq \left(1\over 2\right)^2 + \left(1\over 2\right)^2 \\ &= 2^{-1} \end{align*} ,$$ so taking square roots yields $$ \left|{\alpha\over \beta} - q\right| \leq 2^{-{1\over 2}} < 1 .$$