Computing GCDs over the Gaussian Integers: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. |
I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however: |
||
''Claim'': <math>\ZZ[i]</math> is a Euclidean domain, and hence a PID, and hence a UFD.<br /> |
|||
Consider the norm function <math>\nu(a + bi) = a^2 + b^2</math>. We write the standard norm on the complex plane as <math>||a+bi||_{\mathbb{C}} = \sqrt{a^2 + b^2}</math>. We show that for all <math>x \neq 0</math> and <math>y</math> we have, <math> y = qx + r </math> where <math>\nu(r) = 0</math> or <math>\nu(r) < \nu(x)</math>. Consider <math>x</math> and <math>y</math> as points on the complex plane. Since <math>x \neq 0</math> we have that <math>y/x</math> is another point in the complex plane. Consider <math>\ZZ[i]</math> as the points with integer coordinates in <math>\mathbb{C}</math>. For any point <math>\zeta \in \mathbb{C}</math> we can find a <math>\zeta' \in \ZZ[i]</math> such that <math>||\zeta - \zeta'||_{\mathbb{C}} \leq \sqrt{2}/2</math> by taking the <math>\zeta'</math> to be the nearest lattice point to <math>\zeta</math>. Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take <math>z</math> to be the nearest lattice point to <math>y/x</math>. We then have <math>y = zx + (y - zx)</math>. We compute the norm of <math>\nu(y - zx)</math>. We have: <math> \sqrt{\nu(y - zx)} = ||y - zx||_{\mathbb{C}} = ||x||_{\mathbb{C}} \cdot ||y/x - z||_{\mathbb{C}} \leq ||x||_{\mathbb{C}} \frac{\sqrt{2}}{2} < ||x||_{\mathbb{C}} = \sqrt{\nu(x)} </math> It follows that <math>\nu(y - zy) < \nu(x)</math>. We obtain that <math>\ZZ[i]</math> is a Euclidean domain. Thus <math>\ZZ[i]</math> is a PID and hence a UFD by results given in class. |
|||
---- |
---- |
||
Revision as of 14:55, 26 November 2011
I wrote up a very simple Perl script for computing GCDs over the Gaussian integers. It comes with no guarantee or proof of correctness. One can sketchily argue something like this however:
Claim: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ZZ[i]}
is a Euclidean domain, and hence a PID, and hence a UFD.
Consider the norm function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(a + bi) = a^2 + b^2}
. We write the standard norm on the complex plane as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||a+bi||_{\mathbb{C}} = \sqrt{a^2 + b^2}}
. We show that for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \neq 0}
and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y}
we have, where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(r) = 0}
or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(r) < \nu(x)}
. Consider Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x}
and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y}
as points on the complex plane. Since Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \neq 0}
we have that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y/x}
is another point in the complex plane. Consider Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ZZ[i]}
as the points with integer coordinates in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{C}}
. For any point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta \in \mathbb{C}}
we can find a Failed to parse (unknown function "\ZZ"): {\displaystyle \zeta' \in \ZZ[i]}
such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\zeta - \zeta'||_{\mathbb{C}} \leq \sqrt{2}/2}
by taking the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \zeta'}
to be the nearest lattice point to . Since any point on the plane is contained in a square whose vertices are lattice points and whose side lengths are one, there must be a lattice point nearer than half the diagonal of the square. We then take to be the nearest lattice point to . We then have . We compute the norm of . We have: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sqrt{\nu(y - zx)} = ||y - zx||_{\mathbb{C}} = ||x||_{\mathbb{C}} \cdot ||y/x - z||_{\mathbb{C}} \leq ||x||_{\mathbb{C}} \frac{\sqrt{2}}{2} < ||x||_{\mathbb{C}} = \sqrt{\nu(x)} }
It follows that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu(y - zy) < \nu(x)}
. We obtain that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ZZ[i]}
is a Euclidean domain. Thus Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ZZ[i]}
is a PID and hence a UFD by results given in class.
#!/usr/bin/perl
use Math::Complex;
## A Quick hack for computing GCDs of Gaussian integers.
$z2 = 857 + i;
$z1 = 255;
sub gcd {
# the Euclidean algorithm
my $x = $_[0];
my $y = $_[1];
if ($x * $y == 0) {
print "Done!\n";
} else {
$q = &approx($x/$y);
$r = $x - $q*$y;
print "($x) = ($q)($y) + ($r)\n";
&gcd($y,$r);
}
}
sub approx {
# find the nearest Gaussian integer to a point on the complex plane
my $z = $_[0];
my $x = int(Re($z));
my $y = int(Im($z));
if (abs($z - (($x+1) + i*$y) ) < 1/sqrt(2)) {
return ($x+1) + i*$y;
} elsif (abs($z - (($x) + i*($y+1)) ) < 1/sqrt(2)) {
return $x + i*($y+1);
} elsif (abs($z - (($x+1) + i*($y+1)) ) < 1/sqrt(2)) {
return ($x+1) + i*($y+1);
} else {
return $x + i*$y;
}
}
&gcd($z1, $z2);
