Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Imaginary/Complex Numbers
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/