# Proving two number are relatively prime

1. Sep 3, 2010

### 188818881888

1. The problem statement, all variables and given/known data
show that 5n +3 and 7n+4 are relatively prime for all n.

2. Relevant equations

3. The attempt at a solution
tried to use induction but didnt work. Trying to find another way.

2. Sep 3, 2010

### Hurkyl

Staff Emeritus
Isn't the usual way via computing a GCD?

3. Sep 3, 2010

### 188818881888

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

4. Sep 3, 2010

### Hurkyl

Staff Emeritus
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?

5. Sep 3, 2010

### 188818881888

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

6. Sep 3, 2010

### Hurkyl

Staff Emeritus
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.

7. Sep 3, 2010

### 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)

8. Sep 3, 2010

### Hurkyl

Staff Emeritus
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?

9. Sep 3, 2010

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

10. Sep 3, 2010

### Hurkyl

Staff Emeritus
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.

11. Sep 3, 2010

### 188818881888

ok i see. i still am stuck though. i think that im 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.

12. Sep 3, 2010

### Hurkyl

Staff Emeritus
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.

13. Sep 3, 2010

### Gokul43201

Staff Emeritus
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.