What is the GCD of a Positive and a Negative Number?

The greatest common divisor (GCD) of a positive and a negative number is the same as the GCD of the positive version of that number. This property holds because the GCD is defined based on the absolute values of the numbers involved. For example, if you want to find the GCD of 12 and -15, you would calculate it as follows:

Example: Finding the GCD of 12 and -15

Take the absolute values: 12 12 and -15 15. Find the GCD of 12 and 15.

The GCD of 12 and 15 is 3. Therefore, the GCD of 12 and -15 is also 3.

Algorithm for Calculating GCD

Regardless of the definition of the GCD, the Euclidean algorithm always provides a result with the same sign as the second number given. Here is a function in Python to compute the GCD:

def gcd(x, y): while y: x, y y, x % y return x

This is useful if x and y are being used as the numerator and denominator of a fraction. It guarantees that the denominator will always be positive and that the sign of the fraction will be carried by the numerator.

Example: Finding the GCD of 15 and -18 using the Euclidean Algorithm

Let's apply the Euclidean algorithm to find the GCD of 15 and -18:

From the Euclidean algorithm: a qb r, where b ≥ 0 and a ≥ b. Let a 15 and b -18. q is the multiplier, and r is the remainder.

The process continues in a cycle with b replacing a and r replacing b in the next stage. This cycle ends when the remainder is 0, and the GCD is the remainder obtained just before the last stage.

Let's perform the steps:

15 -1 × -18 - 3 -18 -6 × 3 - 0

Hence, the GCD is 3.

Negative Numbers as Vectors

Once you give a number a sign, you give it a direction. If a number has a direction, it is a vector. The phrase "so-called negative numbers" refers to these directed numbers. Therefore, a negative number acts as a vector in a number line, pointing in the opposite direction of its positive counterpart.

The fact that a number is negative does not change its list of positive divisors relative to its positive counterpart. Neither does either or both of the values whose greatest common divisor is being sought have any impact on which positive divisor is the greatest. Therefore, we can generalize:

GCD(a, b) GCD(a, -b) GCD(-a, b) GCD(-a, -b) for any integers a and b at least one of which is nonzero.

Example: Finding the GCD of 18 and 12

To illustrate, consider the GCD of 18 and 12:

18 2 × 12 6 12 2 × 6 0

The GCD is 6. Since 18 and 12 are both positive, their GCD is 6, which is also the GCD of 18 and -12, and the GCD of 12 and -18, and so on.

n6 divides all of 18, 12, 12, and 18, and no greater integer divides all of those values.