1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving two number are relatively prime

  1. Sep 3, 2010 #1
    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. jcsd
  3. Sep 3, 2010 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Isn't the usual way via computing a GCD?
     
  4. Sep 3, 2010 #3
    i have to prove for all n. this is a proof's class. what do u mean?
     
  5. Sep 3, 2010 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  6. Sep 3, 2010 #5
    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
     
  7. Sep 3, 2010 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  8. Sep 3, 2010 #7
    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)
     
  9. Sep 3, 2010 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  10. Sep 3, 2010 #9
    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.
     
  11. Sep 3, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  12. Sep 3, 2010 #11
    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.
     
  13. Sep 3, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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


    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.
     
  14. Sep 3, 2010 #13

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook