Gaussian Integers form an Euclidean Ring












3














A Ring $R$ is called euclidean if a map $f:Rbackslash {0} rightarrow mathbb{N}$ exists with the following properties: For two elements $a,b in R$ with $bneq 0$ there exist $q,rin R$ with:



(i) $a=qb+r$ and



(ii) $r=0$ or $fleft(r right)<fleft(bright)$.



The Gaussian Integers are a Ring $G:= {a+bi:a,b inmathbb{Z}}$. I want to show that $G$ is an euclidean Ring. Because $G$ is obviously an Integral domain, I would be able to show that $G$ is a Principal ideal domain.



My problem is with the second part (ii). I saw that such a mapping can be defined with $a+bi mapsto a^2 + b^2$. Here is what I don't get: In our case the $b$ in (ii) is i, so I want to find a $f$ with $fleft(a right)<fleft(iright)$ for the Gaussian Integers right? How is $a+bi mapsto a^2 + b^2$ helping here? I am sorry if the notation is a bit odd. For the Gaussian integers I get (to put them into the frame like in (i)) that $a=q$, $b=i$ and $r=a$ right?



Appreciate your help, KingDingeling










share|cite|improve this question




















  • 1




    I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
    – saulspatz
    1 hour ago






  • 1




    You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
    – Bernard
    1 hour ago






  • 1




    I don't know if you want to do this as an exercise. If not I can also post a complete solution.
    – 0x539
    1 hour ago






  • 1




    You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
    – Ross Millikan
    58 mins ago












  • Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
    – KingDingeling
    58 mins ago
















3














A Ring $R$ is called euclidean if a map $f:Rbackslash {0} rightarrow mathbb{N}$ exists with the following properties: For two elements $a,b in R$ with $bneq 0$ there exist $q,rin R$ with:



(i) $a=qb+r$ and



(ii) $r=0$ or $fleft(r right)<fleft(bright)$.



The Gaussian Integers are a Ring $G:= {a+bi:a,b inmathbb{Z}}$. I want to show that $G$ is an euclidean Ring. Because $G$ is obviously an Integral domain, I would be able to show that $G$ is a Principal ideal domain.



My problem is with the second part (ii). I saw that such a mapping can be defined with $a+bi mapsto a^2 + b^2$. Here is what I don't get: In our case the $b$ in (ii) is i, so I want to find a $f$ with $fleft(a right)<fleft(iright)$ for the Gaussian Integers right? How is $a+bi mapsto a^2 + b^2$ helping here? I am sorry if the notation is a bit odd. For the Gaussian integers I get (to put them into the frame like in (i)) that $a=q$, $b=i$ and $r=a$ right?



Appreciate your help, KingDingeling










share|cite|improve this question




















  • 1




    I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
    – saulspatz
    1 hour ago






  • 1




    You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
    – Bernard
    1 hour ago






  • 1




    I don't know if you want to do this as an exercise. If not I can also post a complete solution.
    – 0x539
    1 hour ago






  • 1




    You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
    – Ross Millikan
    58 mins ago












  • Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
    – KingDingeling
    58 mins ago














3












3








3


1





A Ring $R$ is called euclidean if a map $f:Rbackslash {0} rightarrow mathbb{N}$ exists with the following properties: For two elements $a,b in R$ with $bneq 0$ there exist $q,rin R$ with:



(i) $a=qb+r$ and



(ii) $r=0$ or $fleft(r right)<fleft(bright)$.



The Gaussian Integers are a Ring $G:= {a+bi:a,b inmathbb{Z}}$. I want to show that $G$ is an euclidean Ring. Because $G$ is obviously an Integral domain, I would be able to show that $G$ is a Principal ideal domain.



My problem is with the second part (ii). I saw that such a mapping can be defined with $a+bi mapsto a^2 + b^2$. Here is what I don't get: In our case the $b$ in (ii) is i, so I want to find a $f$ with $fleft(a right)<fleft(iright)$ for the Gaussian Integers right? How is $a+bi mapsto a^2 + b^2$ helping here? I am sorry if the notation is a bit odd. For the Gaussian integers I get (to put them into the frame like in (i)) that $a=q$, $b=i$ and $r=a$ right?



Appreciate your help, KingDingeling










share|cite|improve this question















A Ring $R$ is called euclidean if a map $f:Rbackslash {0} rightarrow mathbb{N}$ exists with the following properties: For two elements $a,b in R$ with $bneq 0$ there exist $q,rin R$ with:



(i) $a=qb+r$ and



(ii) $r=0$ or $fleft(r right)<fleft(bright)$.



The Gaussian Integers are a Ring $G:= {a+bi:a,b inmathbb{Z}}$. I want to show that $G$ is an euclidean Ring. Because $G$ is obviously an Integral domain, I would be able to show that $G$ is a Principal ideal domain.



My problem is with the second part (ii). I saw that such a mapping can be defined with $a+bi mapsto a^2 + b^2$. Here is what I don't get: In our case the $b$ in (ii) is i, so I want to find a $f$ with $fleft(a right)<fleft(iright)$ for the Gaussian Integers right? How is $a+bi mapsto a^2 + b^2$ helping here? I am sorry if the notation is a bit odd. For the Gaussian integers I get (to put them into the frame like in (i)) that $a=q$, $b=i$ and $r=a$ right?



Appreciate your help, KingDingeling







abstract-algebra ring-theory ideals principal-ideal-domains euclidean-domain






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 1 hour ago

























asked 1 hour ago









KingDingeling

675




675








  • 1




    I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
    – saulspatz
    1 hour ago






  • 1




    You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
    – Bernard
    1 hour ago






  • 1




    I don't know if you want to do this as an exercise. If not I can also post a complete solution.
    – 0x539
    1 hour ago






  • 1




    You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
    – Ross Millikan
    58 mins ago












  • Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
    – KingDingeling
    58 mins ago














  • 1




    I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
    – saulspatz
    1 hour ago






  • 1




    You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
    – Bernard
    1 hour ago






  • 1




    I don't know if you want to do this as an exercise. If not I can also post a complete solution.
    – 0x539
    1 hour ago






  • 1




    You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
    – Ross Millikan
    58 mins ago












  • Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
    – KingDingeling
    58 mins ago








1




1




I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
– saulspatz
1 hour ago




I get the impression that you're confusing two different things. The $a$ and $b$ in (i) are two complex numbers, and have nothing to do with the $a$ and $b$ in $a^2+b^2$ which are two real numbers.
– saulspatz
1 hour ago




1




1




You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
– Bernard
1 hour ago




You have to find $qinmathbf Z[i]$ such that the norm of $a-qb$ is less that the norm of $b$.
– Bernard
1 hour ago




1




1




I don't know if you want to do this as an exercise. If not I can also post a complete solution.
– 0x539
1 hour ago




I don't know if you want to do this as an exercise. If not I can also post a complete solution.
– 0x539
1 hour ago




1




1




You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
– Ross Millikan
58 mins ago






You are using $b$ in two different ways. One is as an element of the ring in the first paragraph and one is as the imaginary component of an element in the second paragraph. In neither case is $b$ given to be $i$
– Ross Millikan
58 mins ago














Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
– KingDingeling
58 mins ago




Guys... thank you. I just got really confused. I will try it myself and share my ideas later. Thank you again!
– KingDingeling
58 mins ago










2 Answers
2






active

oldest

votes


















3














You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, in G$ with $b neq 0$, to find $q, r in G$ satisfying (i) and (ii).






share|cite|improve this answer





























    2














    It might help you to understand what can happen when a ring is not Euclidean. For example, consider $mathbb Z[sqrt{-5}]$, consisting of all numbers of the form $m + n sqrt{-5}$, with $m, n in mathbb Z$.



    The natural choice of Euclidean function is $$f(m + n sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n sqrt{-5})$ can never be negative, but it can be 0. Now try $gcd(2, 1 + sqrt{-5})$.



    Since $f(1 + sqrt{-5}) > f(2)$, we assign $a = 1 + sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.



    But then we see that none of the numbers $sqrt{-5}$, $1 + sqrt{-5}$, $2 + sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.



    Your task then is to prove that this can never happen in $G$, or $mathbb G$, or $mathbb Z[sqrt{-1}]$, or as it's more commonly notated, $mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.



    A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.






    share|cite|improve this answer





















      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062868%2fgaussian-integers-form-an-euclidean-ring%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      3














      You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, in G$ with $b neq 0$, to find $q, r in G$ satisfying (i) and (ii).






      share|cite|improve this answer


























        3














        You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, in G$ with $b neq 0$, to find $q, r in G$ satisfying (i) and (ii).






        share|cite|improve this answer
























          3












          3








          3






          You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, in G$ with $b neq 0$, to find $q, r in G$ satisfying (i) and (ii).






          share|cite|improve this answer












          You seem to be a bit confused. $b$ could be any element of $G$ except $0$. You have already found a good choice for $f$ so the only part left is, given arbitrary $a, b, in G$ with $b neq 0$, to find $q, r in G$ satisfying (i) and (ii).







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 1 hour ago









          0x539

          1,022316




          1,022316























              2














              It might help you to understand what can happen when a ring is not Euclidean. For example, consider $mathbb Z[sqrt{-5}]$, consisting of all numbers of the form $m + n sqrt{-5}$, with $m, n in mathbb Z$.



              The natural choice of Euclidean function is $$f(m + n sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n sqrt{-5})$ can never be negative, but it can be 0. Now try $gcd(2, 1 + sqrt{-5})$.



              Since $f(1 + sqrt{-5}) > f(2)$, we assign $a = 1 + sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.



              But then we see that none of the numbers $sqrt{-5}$, $1 + sqrt{-5}$, $2 + sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.



              Your task then is to prove that this can never happen in $G$, or $mathbb G$, or $mathbb Z[sqrt{-1}]$, or as it's more commonly notated, $mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.



              A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.






              share|cite|improve this answer


























                2














                It might help you to understand what can happen when a ring is not Euclidean. For example, consider $mathbb Z[sqrt{-5}]$, consisting of all numbers of the form $m + n sqrt{-5}$, with $m, n in mathbb Z$.



                The natural choice of Euclidean function is $$f(m + n sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n sqrt{-5})$ can never be negative, but it can be 0. Now try $gcd(2, 1 + sqrt{-5})$.



                Since $f(1 + sqrt{-5}) > f(2)$, we assign $a = 1 + sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.



                But then we see that none of the numbers $sqrt{-5}$, $1 + sqrt{-5}$, $2 + sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.



                Your task then is to prove that this can never happen in $G$, or $mathbb G$, or $mathbb Z[sqrt{-1}]$, or as it's more commonly notated, $mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.



                A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.






                share|cite|improve this answer
























                  2












                  2








                  2






                  It might help you to understand what can happen when a ring is not Euclidean. For example, consider $mathbb Z[sqrt{-5}]$, consisting of all numbers of the form $m + n sqrt{-5}$, with $m, n in mathbb Z$.



                  The natural choice of Euclidean function is $$f(m + n sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n sqrt{-5})$ can never be negative, but it can be 0. Now try $gcd(2, 1 + sqrt{-5})$.



                  Since $f(1 + sqrt{-5}) > f(2)$, we assign $a = 1 + sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.



                  But then we see that none of the numbers $sqrt{-5}$, $1 + sqrt{-5}$, $2 + sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.



                  Your task then is to prove that this can never happen in $G$, or $mathbb G$, or $mathbb Z[sqrt{-1}]$, or as it's more commonly notated, $mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.



                  A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.






                  share|cite|improve this answer












                  It might help you to understand what can happen when a ring is not Euclidean. For example, consider $mathbb Z[sqrt{-5}]$, consisting of all numbers of the form $m + n sqrt{-5}$, with $m, n in mathbb Z$.



                  The natural choice of Euclidean function is $$f(m + n sqrt{-5}) = m^2 + 5n^2.$$ Note that $f(m + n sqrt{-5})$ can never be negative, but it can be 0. Now try $gcd(2, 1 + sqrt{-5})$.



                  Since $f(1 + sqrt{-5}) > f(2)$, we assign $a = 1 + sqrt{-5}$ and $b = 2$. Now we wish to express $a = qb + r$ with $f(r) < f(b)$, meaning $f(r) < 4$. Then the only possibilities for $r$ are $-1$, 0 and 1, as all other numbers in this ring have norms of at least 4.



                  But then we see that none of the numbers $sqrt{-5}$, $1 + sqrt{-5}$, $2 + sqrt{-5}$ are divisible by 2. Therefore the Euclidean algorithm has failed in this ring, and therefore this domain is not Euclidean for the function $f$.



                  Your task then is to prove that this can never happen in $G$, or $mathbb G$, or $mathbb Z[sqrt{-1}]$, or as it's more commonly notated, $mathbb Z[i]$, to prove that a suitable choice of $r$ can always be found. The Euclidean function is $f(m + ni) = m^2 + 1n^2$.



                  A complete solution is to be found in certain number theory books, such as An Introduction to the Theory of Numbers by Ivan Niven and Herb Zuckermann.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 20 mins ago









                  Robert Soupe

                  10.9k21950




                  10.9k21950






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062868%2fgaussian-integers-form-an-euclidean-ring%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      CARDNET

                      Boot-repair Failure: Unable to locate package grub-common:i386

                      濃尾地震