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/