1. ## Number Theory GCD

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

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

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

a) $\displaystyle (a,a^n)$ where n is a positive integer.
b) $\displaystyle (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. $\displaystyle (3a+5, 7a+12) = (3a+5, 4a+7) = (3a+5, a+2) =$
$\displaystyle (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 $\displaystyle (2a + 3, 6a+12)$. Then we get that $\displaystyle (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, $\displaystyle x=3a+5$ and $\displaystyle y=7a+12$

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

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

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