{"id":411,"date":"2023-06-20T16:42:59","date_gmt":"2023-06-20T08:42:59","guid":{"rendered":"https:\/\/qwq.cafe\/?p=411"},"modified":"2023-06-20T16:42:59","modified_gmt":"2023-06-20T08:42:59","slug":"abstract-algebra-1-8-euclidean-rings-and-principal-ideal-domains","status":"publish","type":"post","link":"https:\/\/qwq.cafe\/?p=411","title":{"rendered":"Abstract Algebra \u2013 1.8 Euclidean Rings and Principal Ideal Domains"},"content":{"rendered":"

Definition 1.8.1<\/strong> If $a,b$ lie in a commutative ring $R$, then a greatest common divisor<\/strong> (gcd) of $a,b$ is a common divisor $d\\in R$ which is divisible by every common divisor; that is if $c\\mid a$ and $c\\mid b$, then $c\\mid d$.<\/p>\n

Definition 1.8.2<\/strong> A principal ideal domain<\/strong> is a domain $R$ in which every ideal is a principal ideal. This term is usually abbreviated to PID.<\/p>\n

Theorem 1.8.1<\/strong> Let $R$ be a PID.<\/p>\n

    \n
  1. \n

    Every $a,b\\in R$ has a gcd, say $d$, that is a linear combination of $a$ and $b$:
    \n$$
    \nd=sa+tb,
    \n$$
    \nwhere $s,t\\in R$.<\/p>\n<\/li>\n

  2. \n

    Euclid’s Lemma<\/strong>: If an irreducible element $p\\in R$ divides a product $ab$, then either $p\\mid a$ or $p\\mid b$.<\/p>\n<\/li>\n

  3. \n

    Unique Factorization<\/strong>: If $a\\in R$ and $a=p_1\\cdots p_m$, where $p_i$ are irreducible elements, then this factorization is unique in the following sense: if $a=q_1\\cdots q_k$, where the $q_j$ is are irreducible elements, then $k=m$ and the $q$’s can be reindexed so that $p_i$ and $q_i$ are associates for all $i$.<\/p>\n<\/li>\n<\/ol>\n

    Proof.<\/p>\n

      \n
    1. \n

      If $a,b$ are both $0$, then their gcd is $0$.<\/p>\n

      Otherwise, since $R$ is a PID, $(a,b)$ is a principal ideal; that is $\\exists d\\in R,(a,b)=(d)$.<\/p>\n

      Let’s prove that $d=\\gcd(a,b)$.<\/p>\n

      Because $a,b\\in (d)$, $(d\\mid a\\land d\\mid b)\\Rightarrow d$ is a common divisor of $a$ and $b$.<\/p>\n

      And $\\exists s,t\\in R$ with $d=sa+tb$ for $d\\in(a,b)$.<\/p>\n

      Then $\\forall u\\in R$ with $u$ is a common divisor of $a$ and $b$, then $\\exists v,w\\in R$ with $a=vu,b=wu$.<\/p>\n

      So $d=sa+tb=svu+swu=(sv+sw)u\\Rightarrow u\\mid d$.<\/p>\n

      Therefore $d$ is gcd of $a$ and $b$, which is a linear combination of $a,b$.<\/p>\n<\/li>\n

    2. \n

      If $p\\nmid a$, then $1$ is the gcd of $p$ and $a$.<\/p>\n

      Then we have $s,t\\in R$ with $1=sp+ta$ for (1).<\/p>\n

      So $b=apb+tab$. Since $p\\mid ab$, it follows that $p\\mid b$.<\/p>\n<\/li>\n

    3. \n

      By induction on $M=\\max\\{m,k\\}$.<\/p>\n

      If $M=1$, we have $p_1=a=q_1$.<\/p>\n

      For inductive step, the given equation shows that $p_m\\mid q_1\\cdots q_k$. By (2), Euclid’s Lemma, there is some $i$ with $p_m\\mid q_i$.<\/p>\n

      Since $q_i$ is irreducible, $q_i=up_m$ for some unit $u$; that is $q_i$ and $p_m$ are associates.<\/p>\n

      Reindexing, we may assume that $q_k=up_m$; canceling, we have $p_1\\cdots p_{m-1}=q_1\\cdots (q_{k-1}u)$.<\/p>\n

      Since $q_{k-1}u$ is irreducible, the inductive hypothesis gives $m-1=k-1$ (hence, $m=k$) and, after reindexing, $p_i$ and $q_i$ are associates for all $i$. $\\square$<\/p>\n<\/li>\n<\/ol>\n

      Definition 1.8.3<\/strong> A euclidean ring<\/strong> is a domain $R$ that is equipped with a function
      \n$$\\partial:R\\textbackslash\\{0\\}\\to \\mathbb N,
      \n$$
      \ncalled a degree function<\/strong>, such that<\/p>\n

        \n
      1. \n

        $\\partial(f)\\le \\partial(fg)$ for all $f,g\\in R$ with $f,g\\ne 0$;<\/p>\n<\/li>\n

      2. \n

        Division Algorithm:<\/strong> for all $f,g\\in R$ with $f\\ne 0$, there exist $q,r\\in R$ with
        \n$$
        \ng=qf+r,
        \n$$
        \nwhere either $r=0$ or $\\partial(r)<\\partial(f)$.<\/p>\n<\/li>\n<\/ol>\n

        Example 1.8.1<\/strong><\/p>\n

          \n
        1. \n

          Let $R$ have a degree function $\\partial$ that is identically $0$. If $f\\in R$ and $f\\ne 0$, the division algorithm gives an equation $1=qf+r$ with $r=0$ or $\\partial(r)<\\partial(f)$. This forces $r=0$, for $\\partial(r)<\\partial(f)=0$ is not possible. Therefore, $q=f^{-1}$ and $R$ is a field.<\/p>\n<\/li>\n

        2. \n

          The set of integers $\\mathbb Z$ is a euclidean ring with degree function $\\partial(m)=|m|$. Note that $\\partial$ is multiplicative:
          \n$$
          \n\\partial(mn)=|mn|=|m||n|=\\partial(m)\\partial(n).
          \n$$<\/p>\n<\/li>\n

        3. \n

          When $k$ is a field, the domain $k[x]$ is a euclidean ring with degree function $\\partial(f)=\\deg(f)$, the usual degree of a nonzero polynomial $f$. Note that $\\deg$ is additive:
          \n$$
          \n\\partial(fg)=\\deg(fg)=\\deg(f)+\\deg(g)=\\partial(f)+\\partial(g).
          \n$$<\/p>\n<\/li>\n<\/ol>\n

          Theorem 1.8.2<\/strong> A euclidean ring is a PID.<\/p>\n

          Proof.<\/p>\n

          Let $R$ be a euclidean ring with a degree function $\\partial$.<\/p>\n

          Let $I$ be an ideal in $R$. If $I\\ne (0)$, and then we have the $d\\in I\\textbackslash\\{0\\}$ with its degree is minimal in $I\\textbackslash\\{0\\}$.<\/p>\n

          $\\forall a\\in I$, by division algorithm, $a=qd+r$ with $\\partial(r)<\\partial(d)$ or $r=0$.<\/p>\n

          Since $r\\in I$, it follows that $r=0$; so $a\\in (d)$.<\/p>\n

          Therefore $I\\subset(d)\\subset I\\Rightarrow (d)=I$. $\\square$<\/p>\n

          Definition 1.8.4<\/strong> If a degree function $\\partial$ is multiplicative, that is, if $\\partial(fg)=\\partial(f)\\partial(g)$, then $\\partial$ is called a norm<\/strong>.<\/p>\n

          Example 1.8.2<\/strong> The Gaussian integers $\\mathbb Z[i]$ form a euclidean ring whose degree function
          \n$$\\partial(a+bi)=a^2+b^2
          \n$$
          \nis a norm.<\/p>\n

          We now show that $\\partial$ satisfies the first property of a degree function.<\/p>\n

          If $\\beta=c+id\\in \\mathbb Z[i]$ and $\\beta\\ne 0$, then
          \n$$1\\le \\partial(\\beta),
          \n$$
          \nfor $\\partial(\\beta)=a^2+b^2$ is a positive integer; it follows that if $\\alpha,\\beta\\in \\mathbb Z[i]$ with $\\beta\\ne 0$, then
          \n$$\\partial(\\alpha)\\le \\partial(\\alpha)\\partial(\\beta)=\\partial(\\alpha\\beta).
          \n$$
          \nLet us show that $\\partial$ also satisfies the Division Algorithm.<\/p>\n

          Given $\\alpha,\\beta\\in \\mathbb Z[i]$ and $\\beta\\ne 0$, regard $\\alpha\/\\beta$ as an element of $\\mathbb C$. Rationalizing the denominator gives $\\alpha\/\\beta=\\alpha\\overline\\beta\/(\\beta\\overline\\beta)=\\alpha\\overline\\beta\/\\partial(\\beta)$, so that
          \n$$\\alpha\/\\beta=x+yi,
          \n$$
          \nwhere $x,y\\in \\mathbb Q$.<\/p>\n

          Write $x=a+u$ and $y=b+v$, where $a,b\\in \\mathbb Z$ are integers closest to $x$ and $y$, respectively; thus $|u|,|v|\\le \\frac 1 2$. (If $x$ or $y$ has the form $m-\\frac 1 2$, where $m$ is an integer, then we chose the integer $m$ as the closest integer.) It follows that
          \n$$\\alpha=\\beta(a+bi)+\\beta(u+vi).
          \n$$
          \nNotice that $\\beta(u+vi)\\in \\mathbb Z$, for it is equal to $\\alpha-\\beta(a+bi)$. Finally, we have
          \n$$\\partial(\\beta(u+vi))=(u^2+v^2)\\partial(\\beta)\\le (\\frac 1 4+\\frac 1 4)\\partial(\\beta)=\\frac 1 2\\partial(\\beta)<\\partial (\\beta).
          \n$$
          \nIt’s easy to find that quotients and remainders in $\\mathbb Z[i]$ may not be unique. For example, let $\\alpha=3+5i$ and $\\beta=2$. Then $\\alpha\/\\beta=\\frac 3 2 +\\frac 5 2 i$; the possible choice are
          \n$$\\begin{align}
          \na=1 \\text{ and } u=\\frac 1 2 \\ \\ &\\text{ or }\\ \\ a=2 \\text{ and } u=-\\frac 1 2,\\\\
          \nb=2 \\text{ and } v=\\frac 1 2 \\ \\ &\\text{ or }\\ \\ b=3 \\text{ and } v=-\\frac 1 2.
          \n\\end{align}
          \n$$
          \nHence, there are four quotients and remainders after dividing $3+5i$ by $2$ in $\\mathbb Z[i]$.<\/p>\n

          Theorem 1.8.3<\/strong> The ring $\\mathbb Z[i]$ of Gaussian integers is a PID.<\/p>\n

          Definition 1.8.5<\/strong> An element $u$ in a domain $R$ is a universal side divisor<\/strong> if $u$ is not a unit and, for every $x\\in R$, either $u\\mid x$ or there is a unit $z\\in R$ with $u\\mid (x+z)$.<\/p>\n

          Proposition 1.8.1<\/strong> If $R$ is a euclidean ring but not a field, then $R$ has a universal side divisor.<\/p>\n

          Proof.<\/p>\n

          Let $\\partial$ be the degree function on $R$, and define
          \n$$S=\\{\\partial(v);v\\ne 0\\text{ and } v \\text{ is not a unit}\\}.
          \n$$
          \nSince $R$ is not a field, then $S$ is a nonempty subset of the natural numbers and, hence, $S$ has a smallest element, say, $\\partial(u)$.<\/p>\n

          Then we claim that $u$ is a universal side divisor.<\/p>\n

          If $x\\in R$, there are elements $q$ and $r$ with $x=qu+r$. If $r=0$, then $u\\mid x$; otherwise, $\\partial(r)<\\partial(u)$ shows that $r\\notin S\\Rightarrow r$ is a unit.<\/p>\n

          Therefore, $u$ is a universal side divisor. $\\square$<\/p>\n

          The converse of Theorem 1.8.2 is false: there are PIDs that are not euclidean rings.<\/p>\n

          Example 1.8.3<\/strong> If $\\alpha=\\frac 1 2(1+\\sqrt{-19})$, then it is shown in algebraic number theory that the ring
          \n$$\\mathbb Z(\\alpha)=\\{a+b\\alpha;a,b\\in \\mathbb Z\\}
          \n$$
          \nis a PID ($\\mathbb Z(\\alpha)$ is the ring of algebraic integers in the quadratic number field $\\mathbb Q(\\sqrt{-19})$). In 1949, Motzkin proved that $\\mathbb Z(\\alpha)$ doesn’t have a universal side divisor, so it isn’t a euclidean ring.<\/p>\n

          Proposition 1.8.2<\/strong> Let $R$ be a euclidean ring, not a field, whose degree function $\\partial$ is a norm.<\/p>\n

            \n
          1. An element $\\alpha\\in R$ is a unit if and only if $\\partial(\\alpha)=1$.<\/li>\n
          2. If $\\alpha\\in R$ and $\\partial(\\alpha)=p$, where $p$ is a prime number, then $\\alpha$ is irreducible.<\/li>\n
          3. The only units in the ring $\\mathbb Z[i]$ of Gaussian integers are $\\pm 1$ and $\\pm i$.<\/li>\n<\/ol>\n

            Proof.<\/p>\n

              \n
            1. \n

              $\\partial(1)=\\partial(1\\cdot 1)=\\partial(1)\\partial(1)\\Rightarrow$ $\\partial(1)=1$ or $\\partial(1)=0$.<\/p>\n

              If $\\partial(1)=0$, then $\\forall a\\in R\\textbackslash\\{0\\},\\partial(a)=\\partial(1a)=\\partial(1)\\partial(a)=0$; hence, by the Division Algorithm, $1=qa+r$ with $r=0$.<\/p>\n

              Every element is a unit, contradicting $R$ is not a field.<\/p>\n

              Therefore $\\partial(1)=1$.<\/p>\n

                \n
              • \n

                ($\\Rightarrow$).<\/p>\n

                $1=\\partial(1)=\\partial(\\alpha\\alpha^{-1})=\\partial(\\alpha)\\partial(\\alpha^{-1})$.<\/p>\n

                For $\\partial(\\alpha)$ and $\\partial(\\alpha^{-1})$ are positive integers, $\\partial(\\alpha)=1$.<\/p>\n<\/li>\n

              • \n

                ($\\Leftarrow$).<\/p>\n

                $1=q\\alpha+r$ with $r=0$ or $\\partial(r)<\\partial(\\alpha)=1$.<\/p>\n

                If $r\\ne 0$, that is $\\partial(r)=0$, then $1 = q'r+r'$ with $r'=0$, by the Division Algorithm.<\/p>\n

                Thus, $r$ is a unit and, hence, $\\partial(r)=1$, which contradicts $\\partial(r)=0$.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n

              • \n

                If $\\alpha=uv$, then $p=\\partial(\\alpha)=\\partial(u)\\partial(v)$.<\/p>\n

                For $p$ is prime, $\\partial(u)=1$ or $\\partial(v)=1$ and, hence, $u$ is a unit or $v$ is a unit.<\/p>\n<\/li>\n

              • \n

                If $a+bi\\in \\mathbb Z[i]$ is a unit, then $a^2+b^2=\\partial(a+bi)=1$.<\/p>\n

                Since $a,b\\in \\mathbb Z$, $a=\\pm 1\\land b=0$ or $a=0\\land b=\\pm 1$. $\\square$<\/p>\n<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

                Definition 1.8.1 If $a,b$ lie in a commutative ring $R$ […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,6],"tags":[11,8],"class_list":["post-411","post","type-post","status-publish","format-standard","hentry","category-abstract-algebra","category-6","tag-11","tag-8"],"_links":{"self":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/411","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=411"}],"version-history":[{"count":1,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/411\/revisions"}],"predecessor-version":[{"id":412,"href":"https:\/\/qwq.cafe\/index.php?rest_route=\/wp\/v2\/posts\/411\/revisions\/412"}],"wp:attachment":[{"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=411"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=411"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/qwq.cafe\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=411"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}