Proving two number are relatively prime

[188818881888]

Homework Statement

show that 5n +3 and 7n+4 are relatively prime for all n.

Homework Equations

The Attempt at a Solution

tried to use induction but didnt work. Trying to find another way.

 

[Hurkyl]

Isn't the usual way via computing a GCD?

 

[188818881888]

i have to prove for all n. this is a proof's class. what do u mean?

 

[Hurkyl]

One of the standard ways to check if two numbers are relatively prime is compute that their GCD is 1, right? So have you tried it?

 

[188818881888]

yes when n=1 the two numbers are relatively prime. but i have to prove it for all n and i can't calculate for all n because n is infinite

 

[Hurkyl]

n isn't infinite. You mean there are infinitely many possibilities for n.

You can calculate for all n: that's one of the reasons you learned how to do arithmetic with variables!

I'm not asking you to compute the GCD of 5*0+3 and 7*0+4 then 5*1+3 and 7*1+4 and then 5*2+3 and 7*2+4, et cetera. I'm simply asking you to make an attempt to compute the GCD of 5n+3 and 7n+4. Even if the usual GCD algorithm or some clever tweak to it doesn't solve the problem for you, at least you can say you tried it, and maybe it still reduces things to a simpler problem that is easier to solve.

 

[188818881888]

rite well like i said i tried to use induction to compute it for all n. the base case n=1 works and after you assume 5n+3 and 7n+4 are relatively prime, ie (5n+3)s + (7n+4)t =1 = gcd, then i tried to use that to prove for n+1, ie {5(n+1)+3}s + {7(n+1) +4}t =1. after expanding and using the assumption i still got stuck. btw (s and t are intergers)

 

[Hurkyl]

rite well like i said i tried to use induction to compute it for all n. the base case n=1 works and after you assume 5n+3 and 7n+4 are relatively prime, ie (5n+3)s + (7n+4)t =1 = gcd, then i tried to use that to prove for n+1, ie {5(n+1)+3}s + {7(n+1) +4}t =1. after expanding and using the assumption i still got stuck. btw (s and t are intergers)

Well, if you want to do it that way, then you shouldn't use the same letters for multiple purposes. The s in (5n+3)s + (7n+4)t=1 has, a priori, nothing to do with the s in the hypothetical (5(n+1)+3)s + (7(n+1)+4)t=1, and similarly for t. In the latter equation, it's surely better to use different letters; say u and v. How far did you get?

 

[188818881888]

ok using u and v i have (5n + 5+ 3)u + (7n +7 +4)v =1
we already know that (5n +3)u + (7n +4)v =1 by assumption. wats left over is 5u +7v. since 5 and 7 are relatively prime (5u + 7v) =1 also so the first equation equal two and it should equal one.

 

[Hurkyl]

Ack, you made the same mistake! You used u for two different purposes in exactly the the same way you used s for two different purposes last time.

The two coefficients on

___ (5n+3) + ___ (7n+4) = 1​

have no prior reason to be the same thing as the two coefficients on

___ (5(n+1)+3) + ___ (7(n+1)+4) = 1.​

There are four distinct blanks there, and you are confusing yourself by using the same pair of letters for both pairs of blanks. The four coefficients should be four different variables, not two.

 

[188818881888]

ok i see. i still am stuck though. i think that I am thinking about it too much. if i put c and d in the 2nd equation i have c(5n+8) +d(7n+11). is it enough to say that 5n+8 and 7n+11 are relatively prime because they have no other common factors other than 1.

 

[Hurkyl]

It is if you can prove it, but if you could prove it, you would be using that argument to prove the original problem.


The tricky part here is that, with the approach you're taking, the only real useful thing you know about, say, 5n+3 involves it being multiplied by the s from your inductive hypothesis. (Or are you using a now?) I think to continue, I would have to take a guess at equating c with some expression involving s.

(Note that you don't have to get it "exactly" right -- the expression for c could involve s and some additional variables, and hopefully you could simplify the problem so that you could guess what the other variables need to be)

Or maybe you could start with the equation involving s and t, and try to fiddle with it to make a 5n+8 appear -- maybe that would give you a good idea about what c needs to be?

Or, I suppose you could try a few specific values of n and n+1, and try to guess how c and s relate?

I guess I can come up with a few ways to proceed after all. There are probably more too.

 

[Gokul43201]

...the base case n=1 works and after you assume 5n+3 and 7n+4 are relatively prime, ie (5n+3)s + (7n+4)t =1...

Apologies for the intrusion, but is it not a lot easier to actually just prove that bolded statement outright (i.e., find s and t)? You can guess them by inspection, and there would be no need to proceed with induction.