Factoring 13 with Complex NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/