Computing GCDs over the Gaussian Integers: Difference between revisions

From Drorbn
Jump to navigationJump to search
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. One can sketchily argue something like this however:
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>\mathbb{Z}[i]</math> is a Euclidean domain, and hence a PID, and hence a UFD.<br />


⚫
''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>\mathbb{Z}[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 \mathbb{Z}[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>\mathbb{Z}[i]</math> is a Euclidean domain. Thus <math>\mathbb{Z}[i]</math> is a PID and hence a UFD by results given in class.

⚫
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.




Latest revision as of 14:56, 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 \mathbb{Z}[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 . Consider and as points on the complex plane. Since we have that is another point in the complex plane. Consider 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 (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{Z}[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 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} . 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 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 z} to be the nearest lattice point to 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} . We then 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 y = zx + (y - zx)} . 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 \mathbb{Z}[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 \mathbb{Z}[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);
Retrieved from "https://drorbn.net/index.php?title=Computing_GCDs_over_the_Gaussian_Integers&oldid=11086"