Answer to Question #350951 in Combinatorics | Number Theory for Fred

Question

41. Prove that for every integer k the numbers 2k+1 and 9k+4 are rel-

atively prime, and for numbers 2k-1 and 9k+4 find their greatest common 

divisor as a function of k. 

Answer 1

An alternative method of proof:

This problem can essentially be burned to ashes using the Euclidean Algorithm. For the first part, we have:

$(2k+1,9k+4) = (2k+1,7k+3)$

$=(2k+1,5k+2)$

$=(2k+1,3k+1)$

$=(2k+1,k)$

$=(k+1,k)$

$=(1,k)$

The greatest common divisor of any integer and $1$ is $1$, so our original numbers have a greatest common divisor of $1$. Also, if the greatest common divisor of two numbers is $1$, then they are relatively prime by definition. Therefore, $2k+1$ and $9k+4$ are relatively prime.

For the second part, we do a similar thing:

$(2k-1,9k+4) =(2k-1,7k+5)$

$=(2k-1,5k+6)$

$=(2k-1,3k+7)$

$=(2k-1,k+8)$

$=(k-9,k+8)$

$=(17,k+8)$

$=(17,k-9)$

Thus, $k\equiv9\mod 17$, then the GCD is $17$. If $k\not\equiv9\mod 17$, the the GCD is $1$.