Factoring 13 with Complex Numbers

Date: 08/11/98 at 07:44:51
From: David Scomazzon
Subject: Showing 13 is not prime using imaginary numbers

I have a question that asks me to show 13 is not a prime number and to 
use imaginary numbers to do so.

Obviously 13 = 13 x 1 but 13 = (3 + 2i)(3 - 2i), thus showing 13 is not 
prime.

How do I show mathematically how to do this?

Also, showing that 3 is still prime using the same technique is causing 
me trouble.

Date: 08/11/98 at 09:50:00
From: Doctor Rob
Subject: Re: Showing 13 is not prime using imaginary numbers

If an integer p is a prime in the ring of integers, but is composite 
in the ring of Gaussian integers (those complex numbers of the form 
a + b*i, where a and b are integers), then it must be that there exist 
integers a, b, c, and d such that:

   p = (a+b*i)*(c+d*i)

where neither a + b*i nor c + d*i is 1, -1, i, or -i. This implies 
that:

   p > |a+b*i| = sqrt(a^2+b^2) > 1 

and:
 
   p > |c+d*i| = sqrt(c^2+d^2) > 1

Multiplying this out,

   p = (a*c-b*d) + (a*d+b*c)*i

Now p is a real number, so a*d + b*c = 0, c/a = -d/b = r/s, say, in 
lowest terms. Then s*c = r*a and s*d = -r*b, so:

   p = (a+b*i)*([r*a]+[-r*b]*i)/s
     = r*(a+b*i)*(a-b*i)/s

Since r/s is in lowest terms, r and s are relatively prime, so it must 
be that s divides both a and b. Then let A = a/s, B = b/s, and 
substitute:

   p = s*r*(A^2+B^2)

Since p is prime, r <= c <= |c+d*i| < p, and s <= a <= |a+b*i| < p, it 
must be that r = s = 1, so c = a and d = -b, and:

   p = (a+b*i)*(a-b*i) = a^2 + b^2

Every prime integer expressible in this form is composite in the ring 
of Gaussian integers, and conversely every prime integer composite in 
the ring of Gaussian integers is expressible in this form.

Another proof uses the fact that if a+b*i divides p, so does a-b*i, by
taking complex conjugates. Then if a+b*i and a-b*i have greatest 
common divisor D, then the conjugate of D is also in common, so D must 
equal its conjugate, and D is real. Then D^2 will divide p, so D = 1.  
Then p = (a+b*i)*(a-b*i)*x = (a^2+b^2)*x, and either a^2 + b^2 = 1, so 
a + b*i is 1, -1, i, or -i, or else x = 1, and p = a^2 + b^2.

Now 3 is not expressible in the form a^2 + b^2, so it is not composite 
in the ring of Gaussian integers. On the other hand, 13 = 2^2 + 3^2, 
so 13 is composite in the ring of Gaussian integers.

It is also possible to prove that every prime number of the form 
4*k + 1 is expressible as the sum of two squares, and no prime number 
of the form 4*k + 3 is expressible in that way. Of course 
2 = 1^2 + 1^2. That tells us that the prime integers which are 
composite in the Gaussian integers are those not leaving remainder 3 
when divided by 4.

If p = 1 (mod 4), then finding the squares a^2 and b^2 is another
interesting problem. Clearly a and b have to be relatively prime, and 
one has to be odd and the other even. When p is small, a short search 
is all that is required. When p is large, the search becomes 
burdensome, and then a mathematical method is better.

- Doctor Rob, The Math Forum
Check out our web site! http://mathforum.org/dr.math/