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
Math Forum Home || Math Library || Quick Reference || Math Forum Search