Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
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? –  Gerry Myerson Apr 16 '11 at 0:10
    
@Gerry, you're right, it's not quite clear how to proceed. Here's one possibility: jimloy.com/algebra/gprimes.htm –  lhf Apr 16 '11 at 2:14
    
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. –  Gerry Myerson Apr 16 '11 at 6:26
    
@Gerry, yes, I think that the lattice approach you describe is the closest in spirit to Eratosthenes. –  lhf Apr 16 '11 at 9:30
    
Thank you all for interesting thoughts! –  user9636 Apr 21 '11 at 20:04

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)$.

share|improve this answer
    
Thanks! –  user9636 Apr 21 '11 at 20:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.