[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.
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.