Gaussian Integers form an Euclidean Ring
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
|
show 2 more comments
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
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
|
show 2 more comments
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
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
abstract-algebra ring-theory ideals principal-ideal-domains euclidean-domain
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
|
show 2 more comments
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
|
show 2 more comments
2 Answers
2
active
oldest
votes
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).
add a comment |
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.
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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).
add a comment |
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).
add a comment |
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).
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).
answered 1 hour ago
0x539
1,022316
1,022316
add a comment |
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
answered 20 mins ago
Robert Soupe
10.9k21950
10.9k21950
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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