# [SOLVED] GCD Proof: Elem. Number Theory

• February 8th 2009, 10:10 PM
iMito
[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.
• February 9th 2009, 01:50 AM
red_dog
Let d a common divisor. Then

$d|(2a+1)\Rightarrow d|(8a+4)$ (1)

$d|(9a+4)$ (2)

From (1) and (2) $d|(9a+4)-(8a+4)\Rightarrow d|a\Rightarrow d|2a$ (3)

From $d|(2a+1)$ and (3) $\Rightarrow d|(2a+1)-2a\Rightarrow d|1$