Euclid's Algorithm for Finding a GCD
Date: 10/12/2002 at 15:36:06 From: Matt Subject: Factoring a large number We were given the numbers 163231, 152057, and 135749, and were asked to find the only number besides one that is a common factor. What is the best way to do this since these are large numbers? Thanks.
Date: 10/12/2002 at 16:47:49 From: Doctor Ian Subject: Re: Factoring a large number Hi Matt, You could use Euclid's algorithm for finding the greatest common divisor of any two of the numbers. 163231 = 135749*1 + 27482 | | | +-----------+ +---------------+ | | | gcd(16321,135749) = gcd(135749,27482) 135749 = 4*27482 + 25821 gcd(135749,27842) = gcd(27482,25821) 27482 = 25821*1 + 1661 gcd(27482,25821) = gcd(25821,1661) 25821 = 1661*15 + 906 gcd(25821,1661) = gcd(1661,906) 1661 = 906*1 + 755 gcd(1661,906) = gcd(906,755) 906 = 755*1 + 151 gcd(906,755) = gcd(755,151) 755 = 151*5 gcd(755,151) = 151 And lo and behold, 135749 = 151 * 899 163231 = 151 * 1081 And this should put you well on your way to dealing with the third number. Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 10/12/2002 at 22:24:39 From: Matt Subject: Factoring a large number Thanks a lot! I used the formula and I got 151 for all three numbers. How could you find three numbers, small or pretty large like those, that only have one common divisor? Thanks, Matt
Date: 10/12/2002 at 23:06:10 From: Doctor Ian Subject: Re: Factoring a large number Hi Matt, Do you mean, how would you set up a problem like this? You obviously need three numbers like a = 151 * this b = 151 * that c = 151 * the_other and as long as this, that, and the_other have no factors in common, a, b, and c will have only the one factor in common. Does that make sense? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Date: 10/14/2002 at 10:05:34 From: Matt Subject: Factoring a large number Yes, I want three numbers that have only one divisor, but is there a formula or a pattern I should look for that would clue me that these numbers would only have one divisor? Thanks, Matt
Date: 10/14/2002 at 10:35:34 From: Doctor Ian Subject: Re: Factoring a large number Hi Matt, There are divisibility rules that you can use to check for divisibility by small numbers, which you can read about in our FAQ: http://mathforum.org/dr.math/faq/faq.divisibility.html And of course, you should always check those first. But if someone goes to the trouble of setting up a problem like this, it's unlikely that he'll choose such small numbers as the common divisor. One of the things that makes prime numbers so interesting is that they look just like composite numbers, and there appear to be no patterns that can be used to identify them without doing a lot of divisions. It's exactly what makes them useful for encryption. - Doctor Ian, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.