Thread: [SOLVED] GCD Proof: Elem. Number Theory

Ok, so I've tried to find out how to do this, but most of the help I could find is based on two variables a and b.

However, I'm trying to show that for any integer a, gcd(2a + 1, 9a + 4) = 1.

Any help would be excellent.

Thoughts: I'm looking at using the Euclidean Algorithm, but I'm a little confused.

SOLVED.

For future reference to those who have the same problem, you used Euclid's Algorithm.

9*a + 4 = 4*(2*a + 1) + (a + 1)
2*a + 1 = 1*(a + 1) + a
a + 1 = 1*a + 1
a = a*1 + 0

Therefore, the gcd is 1.

Let d a common divisor. Then

(1)

(2)

From (1) and (2) (3)

From and (3)