Euclidean AlgorithmsDate: 3/13/96 at 8:44:27 From: John Vogler Subject: Number Theory Dear Dr. Math, What is the Euclidean algorithm? What is a "constructible" number? What can you tell me about Diophantine equations? I know that one is an equation in several variables which must be solved for integer solutions (or rational, perhaps positive numbers only). I understand that high-order Diophantine equations are pretty much solved one by one by no general procedure, but that there is a procedure for solving single-order equations. Do you know it? A "perfect" number is equal to the sum of its factors excluding itself; 6 = 1+2+3. What is the significance of a perfect number? Primes are nice for prime factorization, but I don't see any use for perfect numbers. Curious, Johnny Vogler Date: 3/24/96 at 12:17:23 From: Doctor Ken Subject: Re: Number Theory The Euclidean Algorithm is a procedure for finding the gcd of two numbers. Basically I'll give you an example because it's harder to explain than to show: Take 5033464705 and 3137640337, find their greatest common divisor. To do this we use the Euclidean Algorithm: 5033464705 = 1*3137640337 + 1895824368 3137640337 = 1*1895824368 + 1241815969 1895824368 = 1*1241815969 + 654008399 1241815969 = 1*654008399 + 58200938 654008399 = 1*58200938 + 66200829 58200938 = 8*66200829 + 58200938 66200829 = 1*58200938 + 7999891 58200938 = 7*7999891 + 2201701 7999891 = 3*2201701 + 1394788 2201701 = 1*1394788 + 806913 1394788 = 1*806913 + 587875 806913 = 1*587875 + 219038 587875 = 2*219038 + 149799 219038 = 1*149799 + 69239 149799 = 2*69239 + 11321 69239 = 6*11321 + 1313 11321 = 8*1313 + 817 1313 = 1*817 + 496 817 = 1*496 + 321 496 = 1*321 + 175 321 = 1*175 + 146 175 = 1*146 + 29 146 = 5*29 + 1 29 = 29*1 + 0 So 1 is the greatest common divisor of 5033464705 and 3137640337. We could have gotten the gcd by factoring into primes and then getting the smallest power of each prime in both of them and multiplying together - but factoring those numbers would not be fun. In fact if the numbers got real large, say if they were about a hundred digits long, Ron Rivest (at MIT) conjectured it would take 4 BILLION years to factor the numbers into primes, while finding the gcd this way would only take a couple of months (or less). So you see the Euclidian Algorithm is a pretty powerful thing. Diophantine equations are just that - equations in one or more variables which look for positive integer (or rational in some instances) solutions. For your linear problems: Let ax + by = c, where a, b are given integers and x, y are unknown integers. Suppose at least one of a, b is not zero. Then let g = gcd(a,b). If g does not divide c then there are no solutions to this problem. But say g divides c. Then by the Euclidean algorithm we can find two integers x_0, and y_0 such that a*x_0 + b*y_0 = g. (This is much trickier than just explaining the Euclidean algorithm, so if you'd take my word for it I'd be happy :) .) Multiply both sides of this equation by c/g. Since g divides c this is an integer. Multiplying we get: a*(c*x_0)/g + b*(c*y_0)/g = c. So x = c*x_0/g, and y = c*y_0/g is an integer solution to this problem. Let's see if we can get any more solutions (there might be more than one). Rename the above solution to x_1 = c*x_0/g, and y_1 = c*x_0/g. We can get more solutions by setting x = x_1 + k*b/g, and y = y_1 - k*a/g, where k is an arbitrary integer. Now are there any solutions that don't fit this form? The answer is no; to prove this say x_1, y_1, some other two integers x and y are both solutions. Then ax + by = ax_1 + by_1. So a(x - x_1) = b*(y_1 - y). Divide by g on both sides to get: (a/g)*(x-x_1) = (b/g)*(y_1-y). This means (a/g) divides what's on the right hand side. But (a/g) does not divide (b/g) since they are relatively prime (since g is the gcd of them), so (a/g) divides (y_1 - y). So k*(a/g) = y_1 - y. Solving this for y we get: y = y_1 - k*(a/g). Then substituting in we get: x = x_1 + k*(b/g). So we've proved that every solution is of that form. For higher order problems it gets a little tricky. Normally they're examined by using modular analysis, which means you reduce the coefficients modulo a prime and check to see if it's possible, and if it is, what the possibilities are. Basically this technique is not very hard, but it requires a lot of background knowledge and good logic skills, so it'll be pretty hard to explain here. (Notice how hard it was to explain the first order.) Perfect numbers are basically just that, pretty to think about, but not very useful. Although many theorems that help us factor large numbers come from the study of perfect numbers. An example of this is Euler's proof that any divisor of a number of the form 2^2^n - 1 is of the form k*2^n - 1. (Example: 2^2^5 - 1 = 2^32 = 4294967295 = 16843009 * 255). I hope this helps and that you didn't get too bored reading the procedure for finding the solution to the first order Diophantine equations. -Doctor Steven, The Math Forum |
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/