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

Question #350951

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. 


1
Expert's answer
2022-06-16T15:04:52-0400

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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS