11
$\begingroup$

I need to adapt the Sieve of Eratosthenes for the usual integers to find all Gaussian primes with norm less than a specific limit. How to apply it to finding all Gaussian primes with norm less than 100? Thank you very much!

2 Answers 2

11

In the Sieve of Eratosthenes for rational integers, you select the positive ones and list those in increasing size. You do the same for the Gaussian integers: list them by increasing norm. But you need to select only one representative from each associate class, that is, modulo multiplication by units. In the rational integers, the units are $\pm 1$. In the Gaussian integers they are $\pm 1$ and $\pm i$. So to normalize the Gaussian integers, you may assume that $|a| \le |b|$ in $a+bi$ because you can always multiply by $i$ to make it so, and you may also assume that $a \ge 0$ because you can always multiply by $-1$ to make it so.

  • 2
    that doesn't quite mimic the sieve of Eratosthenes, does it? In the integers, every third one is divisible by 3, every 5th one by 5, etc. If you list the Gaussians as you describe, will the multiples of, say, $2+i$ form such a simple pattern?2011-04-16
  • 0
    @Gerry, you're right, it's not quite clear how to proceed. Here's one possibility: http://www.jimloy.com/algebra/gprimes.htm2011-04-16
  • 0
    yes, that page goes systematically through the Gaussians and picks out the primes. I don't see it as Eratosthenian, if you'll allow that as a word. For one thing, you have to know which ordinary integers are prime, else what do you do when you get to, say, $100+i$, with norm 10,001? You can't say, unless you know whether 10,001 is a prime.2011-04-16
  • 0
    @Gerry, yes, I think that the lattice approach you describe is the closest in spirit to Eratosthenes.2011-04-16
  • 0
    Thank you all for interesting thoughts!2011-04-21
9

EDIT1: what's below is quite wrong, or, to be more positive about it, woefully incomplete. Please see EDIT2.

Represent the Gaussians with norm less than 100 as the lattice points on or in the circle of radius 10 centered at the origin (I take it the norm of $a+bi$ is $a^2+b^2$). Concentrate on the 45 degree sector between the real axis and the line $x=y$. Ignore the points $(0,0)$ and $(1,0)$. Take the closest point to the origin (which is $(1,1)$, corresponding to the number $1+i$), circle it (that's your first prime), and cross out everything else on the line connecting it to the origin. Among the points remaining, take the one closest to the origin, and iterate the procedure until termination.

EDIT2: Crossing out everything on the line through $(0,0)$ and $(a,b)$ will only cross out the multiples of $a+bi$ by ordinary integers, and that's not good enough - one must also cross out the multiples by other Gaussian integers. These form a $\it lattice$ generated by $a+bi$ and $b-ai$. Anyone unfamiliar with this concept is encouraged to plot (for example) the points ${\bf u}=(2,1)$ and ${\bf v}=(1,-2)$, think of them as vectors, then start plotting linear combinations of the two vectors with integer coefficients, $c{\bf u}+d{\bf v}$ with $c$ and $d$ integers. You'll see a simple pattern - that's a lattice, and you have to cross out all the points in it when you circle $(2,1)$.