- #1

matqkks

- 285

- 5

How do computers evaluate the gcd of two integers?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- MHB
- Thread starter matqkks
- Start date

In summary, the Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides evenly into both of the given integers. It can be found by listing out all the factors of both integers or by using the Euclidean algorithm. Finding the GCD can help simplify fractions, solve problems involving ratios and proportions, and is used in algorithms and programming. The GCD is always a positive integer and there is no limit to the size of the integers when finding it, although larger numbers may take more time to calculate.

- #1

matqkks

- 285

- 5

How do computers evaluate the gcd of two integers?

Mathematics news on Phys.org

- #2

castor28

Gold Member

MHB

- 255

- 0

matqkks said:How do computers evaluate the gcd of two integers?

Hi,

They use Euclid's algorithm, described here. (Look in particular at section 2, Description).

The Greatest Common Divisor, also known as the Greatest Common Factor, is the largest positive integer that divides evenly into both of the given integers.

One method is to list out all the factors of both integers and then find the largest one that they have in common. Another method is to use the Euclidean algorithm, which involves dividing the larger integer by the smaller one and then using the remainder as the new divisor until the remainder is 0.

Finding the GCD can help in simplifying fractions and solving problems involving ratios and proportions. It is also used in algorithms and programming for tasks such as reducing fractions and finding the least common multiple.

No, the GCD is always a positive integer. However, if one or both of the integers are negative, the GCD remains the same as it would be if the integers were positive.

No, the GCD can be found for any two integers, regardless of their size. However, as the numbers get larger, it may become more time consuming to find the GCD using the list or Euclidean algorithm methods.

- Replies
- 2

- Views
- 1K

- Replies
- 5

- Views
- 1K

- Replies
- 11

- Views
- 5K

- Replies
- 1

- Views
- 2K

- Replies
- 2

- Views
- 1K

- Replies
- 6

- Views
- 990

- Replies
- 5

- Views
- 2K

- Replies
- 2

- Views
- 12K

- Replies
- 19

- Views
- 5K

- Replies
- 7

- Views
- 1K

Share: