Show that if n is any integer, then 3n + 4 and 6n + 7 are relatively prime.

Question

Show that if n is any integer, then 3n + 4 and 6n + 7 are relatively prime.

Answer 1

for any n, 3n+4 and 6n+7 are relatively prime, that is, they have no common factors except the number 1

 

6n+7=3n+3n+3+4

3n+3n+3+4=3n+4+3n+3

the first expression is 3n+4 and the second expression is 3n+4+(3n+3)

let 3n+4=P and let 3n+4+(3n+3)=P+(P-1) because 3n+3 is 3n+4-1

now you are comparing P and P+(P-1)

you are comparing P and 2P-1 because P+(P-1)=2P-1

2P is a multiple of P because 2P is two times P

2P is divisible by all of the prime factors of P

2P-1 is not divisible by any of the prime factors of P because 2P is just large enough to be divisible by all of the prime factors of P as well as P itself

when you subtract 1 from 2P it becomes too small to be divisible by any of the prime factors of P

2P-1, when divided by any factor of P, call the factor F, will leave a remainder of F-1, thus 2P-1 will not be divisible by the factor F

therefore, P and 2P-1 are relatively prime and therefore 3n+4 and 6n+7 are relatively prime as well

for example, 84 and 42

84 is divisible by 42, 2, 3, and 7

but 84-1=83 and 83 isn't large enough to be divisible by 2, 3, 7, or 42

83/2=41 R1, 83/3=27 R2, 83/7=11 R6, and 83/42=1 R41