# Math Help - Number Theory GCD

1. ## Number Theory GCD

Let $a \in \mathbb{Z} .$ with $a>0$. Find the greatest common divisors below.

a) $(a,a^n)$ where n is a positive integer.
b) $(3a + 5, 7a+ 12)$

2. Originally Posted by JCIR
Let $a \in \mathbb{Z} .$ with $a>0$. Find the greatest common divisors below.

a) $(a,a^n)$ where n is a positive integer.
b) $(3a + 5, 7a+ 12)$
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. $(3a+5, 7a+12) = (3a+5, 4a+7) = (3a+5, a+2) =$
$(2a+3, a+2) = (a+1, a+2) = (a+1, 1) = 1$

3. I dont really follow the algorithm

4. 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 $(2a + 3, 6a+12)$. Then we get that $(2a+3, 6a+12) = (2a+3, 4a+9) = (2a+3, 2a+6) = (2a+3, 3) = (2a, 3)$. 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.

5. Thanks alot that is really clear now.

6. 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, $x=3a+5$ and $y=7a+12$

So it divides $7x-3y$ (to eliminate a).

$7x-3y=21a+35-21a-36=-1$

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