greatest common divisor of large numbers

[logistic_guy]

here is the question

How to find the common greatest divisor of two large numbers, the first consists of 17 digits and the second consists of 16 digits?

it's easy when the numbers small like 50 and 90

$\displaystyle 50 = 2 \times 5 \times 5 = 2 \times 5^2$
$\displaystyle 90 = 2 \times 3 \times 3 \times 5 = 2 \times 3^2 \times 5$

$\displaystyle \text{gcd}(50,90) = 2 \times 5 = 10$

 

[fresh_42]

Factorization is inefficient for large numbers. The extended Euclidean algorithm is faster and easier to code.

Extended Euclidean algorithm - Wikipedia

en.wikipedia.org

 

[Dr.Peterson]

here is the question

How to find the common greatest divisor of two large numbers, the first consists of 17 digits and the second consists of 16 digits?

it's easy when the numbers small like 50 and 90

$\displaystyle 50 = 2 \times 5 \times 5 = 2 \times 5^2$
$\displaystyle 90 = 2 \times 3 \times 3 \times 5 = 2 \times 3^2 \times 5$

$\displaystyle \text{gcd}(50,90) = 2 \times 5 = 10$

To find just the GCD, all you need is the Euclidean Algorithm proper:

Euclidean algorithm - Wikipedia

en.wikipedia.org

In your example, divide 90 by 50 to get 1 with remainder 40; then divide 50 by 40 to get 1 with remainder 10; then divide 40 by 10 to get no remainder, and the GCD is the last divisor used, 10.

For large numbers, this is far easier than any other method.

 

[logistic_guy]

Factorization is inefficient for large numbers. The extended Euclidean algorithm is faster and easier to code.

Extended Euclidean algorithm - Wikipedia

en.wikipedia.org

thank

To find just the GCD, all you need is the Euclidean Algorithm proper:

Euclidean algorithm - Wikipedia

en.wikipedia.org

In your example, divide 90 by 50 to get 1 with remainder 40; then divide 50 by 40 to get 1 with remainder 10; then divide 40 by 10 to get no remainder, and the GCD is the last divisor used, 10.

For large numbers, this is far easier than any other method.

thank

this Euclidean Algorithm for large numbers i can't do it with hand without error. this mean software is necessary?

$\displaystyle \text{gcd}(42849217045022222,5485880443662222) = 2$

software say i need 30 divisions. so it's impossible i do it with hand without mistake

 

[Dr.Peterson]

i can't do it with hand without error. this mean software is necessary?

Of course you can. You just won't, because software makes it unnecessary. Before computers, people would make no such claim.

so it's impossible i do it with hand without mistake

You are using the wrong definition of impossible. This is a math site!

In any case, these statements here have nothing to do with your question. Surely you didn't expect any method to be easy, did you?

 

[fresh_42]

this mean software is necessary?

It means that an easy-to-code algorithm will do. It is a modern tool that is used by many people, e.g. Python. You can always do it by hand, it just takes a little bit longer. The question then is as with every such task: will I write a program or shall I do it by hand? That depends in my opinion on how often you will use such an algorithm and on whether you want to practice programming. The latter will be useful on many occasions in case you follow a path in STEM fields or IT.

And there are finally websites like Wolfram Alpha that will do it for you:

gcd(42849217045022222,5485880443662222)= - Wolfram|Alpha

Wolfram|Alpha brings expert-level knowledge and capabilities to the broadest possible range of people—spanning all professions and education levels.

www.wolframalpha.com

Interesting large prime factors, by the way, and an interesting Bézout expression
$$\begin{array}{lll} 2 &= (2742940221831111 n + 1928420076297505)\cdot 42849217045022222\\ \phantom{=}&+ (-21424608522511111 n - 15062539414017514) \cdot 5485880443662222\, , \, n \in \mathbb{Z} \end{array}$$

 

[logistic_guy]

thank Dr.Peterson
thank fresh_42

i think i'll use software