Thread: Number Theory GCD

Let with . Find the greatest common divisors below.

a) where n is a positive integer.
b)

Originally Posted by JCIR

Let with . Find the greatest common divisors below.

a) where n is a positive integer.
b)

The answer to both is relatively straightforward. For the first, we immediately notice that the GCD is a. The second requires use of an algorithm.

I dont really follow the algorithm

The GCD of a and b, if b>a, is the same as the GCD of a and b-a. You just keep repeating that process in order to get your answer. Suppose instead I want to know . Then we get that . You couldn't simplify that any further, without knowing a. In some cases the gcd would be 1 and in other cases it would be 3.

Thanks alot that is really clear now.

The GCD of a and b, if b>a, is the same as the GCD of a and b-a.

More generally, the gcd of x and y divides any linear combination of x and y.

Here, and

So it divides (to eliminate a).



Since the gcd is an integer (and said to be positive),