Mixing
GCD computations in $mathbb{Z}[i]$
$begingroup$
Problem statement:
Find a generator of the ideal $(85, 1+13i)$ in $mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$
Can you please outline the steps, then I can practice with others.
Source: Abstract Algebra by Dummit & Foote, $S$8.1 #7
abstract-algebra
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
$endgroup$
add a comment |
$begingroup$
Problem statement:
Find a generator of the ideal $(85, 1+13i)$ in $mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$
Can you please outline the steps, then I can practice with others.
Source: Abstract Algebra by Dummit & Foote, $S$8.1 #7
abstract-algebra
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
$endgroup$
6
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
1
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44
add a comment |
$begingroup$
Problem statement:
Find a generator of the ideal $(85, 1+13i)$ in $mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$
Can you please outline the steps, then I can practice with others.
Source: Abstract Algebra by Dummit & Foote, $S$8.1 #7
abstract-algebra
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
$endgroup$
Problem statement:
Find a generator of the ideal $(85, 1+13i)$ in $mathbb{Z}[i]$, i.e., a GCD for $85$ and $1 + 13i$ by the Euclidean Algorithm. Do the same for the ideal $(47-13i, 53+56i).$
Can you please outline the steps, then I can practice with others.
Source: Abstract Algebra by Dummit & Foote, $S$8.1 #7
abstract-algebra
abstract-algebra
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
edited Nov 11 '11 at 14:35
The Chaz 2.0
8,13363675
8,13363675
asked Apr 10 '11 at 21:03
marymary
52431449
asked Apr 10 '11 at 21:03
marymary
52431449
asked Apr 10 '11 at 21:03
marymary
52431449
52431449
6
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
1
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44
add a comment |
6
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
1
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44
6
6
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
1
1
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2approx -6i, 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
$endgroup$
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
add a comment |
$begingroup$
A good way to understand the Euclidean algorithm for $mathbb{Z}[i]$ is to prove that $R:=mathbb{Z}[i]$ is a Euclidean domain with respect to the function $varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $xinmathbb{Q}$ there are $yin mathbb{Z}$ and $zinmathbb{Q}$, $|z|leq frac 1 2$ (use the Gauss floor function)
2) if $a,b in R$, then $frac a b in mathbb{Q}(i)$. Write $frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j in mathbb{Z}$ and $z_j in mathbb{Q}, ~ |z_j|leq frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r in R$.
4) The important part is: $varphi(r)<varphi(b)$ (use the fact that $varphi$ is multiplicative).
$varphi$ works just like the absolute value in $mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $frac{a}{b}=x+yi$ in $mathbb{C}$. For $x,y$ choose the closest integers $tilde x, tilde y$. Then $a=b(tilde x + tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $mathbb{Z}[i]$.
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
$endgroup$
add a comment |
$begingroup$
Compute $rm gcd(53+56 i, 47-13 i) $ by using a (Euclidean) remainder sequence, e.g.
$rm(1)quadquadquadquad 56 i +53$
$rm(2)quadquad -13 i + 47$
$rm(3)quadquadquadquad 9 i + 40quadquad$ by $rm (1) - :i (2)$
$rm(4)quadquadquadquad 7 i + 22quadquad$ by $rm i (2) - :i (3)$
$rm(5)quadquadquadquadquad 5 i + 4 quadquad$ by $rm - (3) + 2 (4):, $
Note $rm p: =: 5 i + 4 $ is prime, since it has prime norm $= 41:.:$ Hence the gcd will be either $rm:p:$ or $1:,:$ depending on if $rm:p:$ divides $rm:q = 7 i + 22:; $ it does: $rm:p:p' = 41:$ divides $rm q:p' = 123 - 82 i:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
$endgroup$
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%2f32157%2fgcd-computations-in-mathbbzi%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2approx -6i, 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
$endgroup$
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
add a comment |
$begingroup$
The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2approx -6i, 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
$endgroup$
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
add a comment |
$begingroup$
The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2approx -6i, 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
$endgroup$
The Euclidean algorithm gives:
$$
85/(1+13i)=1/2-13i/2approx -6i, 85=(-6i)(1+13i)+(7+6i),
$$
$$
(1+13i)/(7+6i)=1+i, 1+13i=(1+i)(7+6i),
$$
Hence the gcd is $7+6i$.
When going through the Euclidean algorithm, you divide and take a nearest (Gaussian) integer, as you would over the (rational) integers.
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
edited Feb 1 at 17:52
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
answered Apr 11 '11 at 0:22
yoyoyoyo
6,6311726
6,6311726
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
add a comment |
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
+1, albeit with a slight nitpick: in this context, a "nearest gaussian integer" need not be unique. For any $m,nin mathbb{Z}$, $frac{2m+1}{2} + frac{2n+1}{2}iin mathbb{Q}[i]$ is equidistant to each of $n+mi$, $n+1+mi$, $n+(m+1)i$, and $(n+1)+(m+1)i$.
$endgroup$
– user5137
Nov 11 '11 at 15:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
$begingroup$
Shouldn't it be $ 7+6i$ in first line ?
$endgroup$
– mathemather
Jan 30 at 7:40
add a comment |
$begingroup$
A good way to understand the Euclidean algorithm for $mathbb{Z}[i]$ is to prove that $R:=mathbb{Z}[i]$ is a Euclidean domain with respect to the function $varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $xinmathbb{Q}$ there are $yin mathbb{Z}$ and $zinmathbb{Q}$, $|z|leq frac 1 2$ (use the Gauss floor function)
2) if $a,b in R$, then $frac a b in mathbb{Q}(i)$. Write $frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j in mathbb{Z}$ and $z_j in mathbb{Q}, ~ |z_j|leq frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r in R$.
4) The important part is: $varphi(r)<varphi(b)$ (use the fact that $varphi$ is multiplicative).
$varphi$ works just like the absolute value in $mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $frac{a}{b}=x+yi$ in $mathbb{C}$. For $x,y$ choose the closest integers $tilde x, tilde y$. Then $a=b(tilde x + tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $mathbb{Z}[i]$.
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
$endgroup$
add a comment |
$begingroup$
A good way to understand the Euclidean algorithm for $mathbb{Z}[i]$ is to prove that $R:=mathbb{Z}[i]$ is a Euclidean domain with respect to the function $varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $xinmathbb{Q}$ there are $yin mathbb{Z}$ and $zinmathbb{Q}$, $|z|leq frac 1 2$ (use the Gauss floor function)
2) if $a,b in R$, then $frac a b in mathbb{Q}(i)$. Write $frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j in mathbb{Z}$ and $z_j in mathbb{Q}, ~ |z_j|leq frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r in R$.
4) The important part is: $varphi(r)<varphi(b)$ (use the fact that $varphi$ is multiplicative).
$varphi$ works just like the absolute value in $mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $frac{a}{b}=x+yi$ in $mathbb{C}$. For $x,y$ choose the closest integers $tilde x, tilde y$. Then $a=b(tilde x + tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $mathbb{Z}[i]$.
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
$endgroup$
add a comment |
$begingroup$
A good way to understand the Euclidean algorithm for $mathbb{Z}[i]$ is to prove that $R:=mathbb{Z}[i]$ is a Euclidean domain with respect to the function $varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $xinmathbb{Q}$ there are $yin mathbb{Z}$ and $zinmathbb{Q}$, $|z|leq frac 1 2$ (use the Gauss floor function)
2) if $a,b in R$, then $frac a b in mathbb{Q}(i)$. Write $frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j in mathbb{Z}$ and $z_j in mathbb{Q}, ~ |z_j|leq frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r in R$.
4) The important part is: $varphi(r)<varphi(b)$ (use the fact that $varphi$ is multiplicative).
$varphi$ works just like the absolute value in $mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $frac{a}{b}=x+yi$ in $mathbb{C}$. For $x,y$ choose the closest integers $tilde x, tilde y$. Then $a=b(tilde x + tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $mathbb{Z}[i]$.
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
$endgroup$
A good way to understand the Euclidean algorithm for $mathbb{Z}[i]$ is to prove that $R:=mathbb{Z}[i]$ is a Euclidean domain with respect to the function $varphi(a+bi)=a^2+b^2$.
This can be done in the following way:
1) for $xinmathbb{Q}$ there are $yin mathbb{Z}$ and $zinmathbb{Q}$, $|z|leq frac 1 2$ (use the Gauss floor function)
2) if $a,b in R$, then $frac a b in mathbb{Q}(i)$. Write $frac a b = y_1+z_1 + (y_2+z_2)i$, according to (1), with $y_j in mathbb{Z}$ and $z_j in mathbb{Q}, ~ |z_j|leq frac 1 2$.
3) Now we can write $a=qb+r$, $q:=y_1+y_2i$, $r:=b(z_1+z_2i)$. $q,r in R$.
4) The important part is: $varphi(r)<varphi(b)$ (use the fact that $varphi$ is multiplicative).
$varphi$ works just like the absolute value in $mathbb{Z}$. It will become smaller in every step, so the algorithm will terminate.
From this proof we gather the following algorithm: Compute the fraction $frac{a}{b}=x+yi$ in $mathbb{C}$. For $x,y$ choose the closest integers $tilde x, tilde y$. Then $a=b(tilde x + tilde y i) - r$ with a suitable $r$. In this way you can do a division with remainder in $mathbb{Z}[i]$.
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
answered Nov 11 '11 at 15:24
Oliver BraunOliver Braun
1,57911122
1,57911122
add a comment |
add a comment |
$begingroup$
Compute $rm gcd(53+56 i, 47-13 i) $ by using a (Euclidean) remainder sequence, e.g.
$rm(1)quadquadquadquad 56 i +53$
$rm(2)quadquad -13 i + 47$
$rm(3)quadquadquadquad 9 i + 40quadquad$ by $rm (1) - :i (2)$
$rm(4)quadquadquadquad 7 i + 22quadquad$ by $rm i (2) - :i (3)$
$rm(5)quadquadquadquadquad 5 i + 4 quadquad$ by $rm - (3) + 2 (4):, $
Note $rm p: =: 5 i + 4 $ is prime, since it has prime norm $= 41:.:$ Hence the gcd will be either $rm:p:$ or $1:,:$ depending on if $rm:p:$ divides $rm:q = 7 i + 22:; $ it does: $rm:p:p' = 41:$ divides $rm q:p' = 123 - 82 i:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
$endgroup$
add a comment |
$begingroup$
Compute $rm gcd(53+56 i, 47-13 i) $ by using a (Euclidean) remainder sequence, e.g.
$rm(1)quadquadquadquad 56 i +53$
$rm(2)quadquad -13 i + 47$
$rm(3)quadquadquadquad 9 i + 40quadquad$ by $rm (1) - :i (2)$
$rm(4)quadquadquadquad 7 i + 22quadquad$ by $rm i (2) - :i (3)$
$rm(5)quadquadquadquadquad 5 i + 4 quadquad$ by $rm - (3) + 2 (4):, $
Note $rm p: =: 5 i + 4 $ is prime, since it has prime norm $= 41:.:$ Hence the gcd will be either $rm:p:$ or $1:,:$ depending on if $rm:p:$ divides $rm:q = 7 i + 22:; $ it does: $rm:p:p' = 41:$ divides $rm q:p' = 123 - 82 i:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
$endgroup$
add a comment |
$begingroup$
Compute $rm gcd(53+56 i, 47-13 i) $ by using a (Euclidean) remainder sequence, e.g.
$rm(1)quadquadquadquad 56 i +53$
$rm(2)quadquad -13 i + 47$
$rm(3)quadquadquadquad 9 i + 40quadquad$ by $rm (1) - :i (2)$
$rm(4)quadquadquadquad 7 i + 22quadquad$ by $rm i (2) - :i (3)$
$rm(5)quadquadquadquadquad 5 i + 4 quadquad$ by $rm - (3) + 2 (4):, $
Note $rm p: =: 5 i + 4 $ is prime, since it has prime norm $= 41:.:$ Hence the gcd will be either $rm:p:$ or $1:,:$ depending on if $rm:p:$ divides $rm:q = 7 i + 22:; $ it does: $rm:p:p' = 41:$ divides $rm q:p' = 123 - 82 i:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
$endgroup$
Compute $rm gcd(53+56 i, 47-13 i) $ by using a (Euclidean) remainder sequence, e.g.
$rm(1)quadquadquadquad 56 i +53$
$rm(2)quadquad -13 i + 47$
$rm(3)quadquadquadquad 9 i + 40quadquad$ by $rm (1) - :i (2)$
$rm(4)quadquadquadquad 7 i + 22quadquad$ by $rm i (2) - :i (3)$
$rm(5)quadquadquadquadquad 5 i + 4 quadquad$ by $rm - (3) + 2 (4):, $
Note $rm p: =: 5 i + 4 $ is prime, since it has prime norm $= 41:.:$ Hence the gcd will be either $rm:p:$ or $1:,:$ depending on if $rm:p:$ divides $rm:q = 7 i + 22:; $ it does: $rm:p:p' = 41:$ divides $rm q:p' = 123 - 82 i:.$
The first problem is much simpler, involving only two divisions - see yoyo's answer.
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
edited Apr 16 '11 at 23:31
user242
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
answered Apr 11 '11 at 2:09
Bill DubuqueBill Dubuque
214k29197656
214k29197656
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.
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%2f32157%2fgcd-computations-in-mathbbzi%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
6
$begingroup$
Euclid algorithm en.wikipedia.org/wiki/Euclidean_algorithm - your remainders should have the minimal absolute value
$endgroup$
– user8268
Apr 10 '11 at 21:06
$begingroup$
Since $85 = 5times 17 = (1+2i)(1-2i)(1+4i)(1-4i)$ and $(1+13i)(1-13i) = 170 = 2times 5times 17 = (1+i)(1-i)(1+2i)(1-2i)(1+4i)(1-4i)$, it is now easy to check that $1+13i = -i(1+i)(1+2i)(1+4i)$, so that $gcd(85,1+13i)=(1+2i)(1+4i) = -7+6i$.
$endgroup$
– Arturo Magidin
Apr 10 '11 at 21:42
$begingroup$
I resurrected this question (by editing it), since I came across the problem in an algebra book.
$endgroup$
– The Chaz 2.0
Nov 11 '11 at 14:36
1
$begingroup$
It's also worth pointing out (although not worth posting as an official answer) that since $mathbb{Z}[i]$ is a UFD, you can compute the $gcd$ of any two nonzero nonunit elements by looking at the prime factorizations in $mathbb{Z}[i]$ (by, eg, using the norm). Of course, this is computationally much more difficult than simply applying the Euclidean algorithm.
$endgroup$
– user5137
Nov 11 '11 at 15:44