Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Greatest common divisor | Relatively prime

  1. Jan 7, 2010 #1
    Claim: n! + 1 and (n+1)! + 1 are relatively prime.

    How can we prove this? Can we use mathematical induction?
    Base case: (n=1)
    gcd(2,3)=1
    Therefore, the statement is true for n=1.

    Assuming the statment is true for n=k: gcd(k! + 1,(k+1)! + 1)=1 (induction hypothesis), we need to show that it's true for n=k+1. But I am stuck here. How can we use the induction hypothesis to prove this?

    Or am I even on the right track thinking of using induction?

    Thanks for any help!
     
  2. jcsd
  3. Jan 7, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Reduce mod k = n! + 1.
     
  4. Jan 7, 2010 #3
    I have no background about modular arithmetic right now. It is an exercise from the first chapter of my book about "divisibility" and "relative primes". How can we prove it without assuming knowledge about modular arithmetic?
     
    Last edited: Jan 7, 2010
  5. Jan 7, 2010 #4
    Try a proof by contradiction: Suppose that n! + 1 and (n + 1)! +1 are not relatively prime. Let p be a prime number that divides both numbers. Then p divides the difference, and so ... (Can you do the rest?). (Or if you haven't covered prime numbers yet, let d be any integer greater than 1 that divides both numbers and then continue as above.)

    HTH

    Petek
     
  6. Jan 7, 2010 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Write (n+1)! + 1 in terms of n! + 1.
     
  7. Jan 7, 2010 #6
    I am not sure how to express (n+1)! + 1 in terms of n! + 1, the best I can think of is
    (n+1)! + 1 = (n+1) n! +1

    Proof by contradiction:
    Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1
    => d divides (n + 1)! - n! = (n+1) n! -n! = n!(n+1-1) = (n!)n
    i.e. d divides (n!)n
    I am trying to reach a contradiction, but where is it??
     
    Last edited: Jan 8, 2010
  8. Jan 8, 2010 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Good first step: you've written it in terms of n!. Now you want to write it in terms of k = n! + 1, so replace all instances of n! by (k - 1) and expand.
     
  9. Jan 9, 2010 #8
    OK!
    (n+1)! + 1 = (n+1) n! +1

    Let k= n! + 1 (=> n! = k-1)
    Then (n+1)! + 1 = (n+1) n! +1 = (n+1)(k-1) +1
    = nk -n +k -1 +1
    =n (n! +1) - n + (n! +1)

    But I still don't see where the "contradiction" is...
     
  10. Jan 9, 2010 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi kingwinner! :smile:
    ok, now subtract n! + 1 from that. :wink:
     
  11. Jan 9, 2010 #10
    That's exactly what I did in post #6, but I can't find my contradiction...
     
  12. Jan 9, 2010 #11

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    oh, sorry, I missed that :redface:

    ok, if a prime d divides the difference, then d | (n!)n, so d | n!, so … :smile:
     
  13. Jan 9, 2010 #12
    Actually Petek was right, I haven't read the chapter about "primes" yet, so I assume no results about primes, so I let d to be any integer greater than 1 that divides both numbers. How should I continue?

    But by the way, why if d is a prime and d | (n!)n => d | n! ???
    One theorem in the later chapters says: If p is a prime, then p|(abc) => p|a OR p|b OR p|c.

    Thanks!
     
  14. Jan 9, 2010 #13

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yup … d | (n!)n => d | n! or d | n …

    but if d | n, then d | n! anyway. :wink:
     
  15. Jan 9, 2010 #14
    But I think the converse is false.
    d | (n!)n => d|n or d|(n-1) or d|(n-2) or...or d|2 or d|1 or d|n
    => d|n or d|(n-1) or d|(n-2) or...or d|2 or d|1
     
  16. Jan 9, 2010 #15

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    I agree :smile:

    but all you need is d | n! :wink:
     
  17. Jan 9, 2010 #16
    Actually you are right. I don't know what I was thinking before.

    d | (n!)n => d | n! or d | n
    If d | n!, then d | n!
    If d | n, then d | n!
    So d | (n!)n => d | n! or d | n => d | n!

    But we don't know what "n" is, so there does not seem to be any contradiction...?
     
  18. Jan 9, 2010 #17

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    ah, but you started with …
    so … ? :wink:
     
  19. Jan 9, 2010 #18
    The claim is n! + 1 and (n+1)! + 1 are relatively prime for ALL n E N.

    So to use proof by contradiction, we assume that
    there exists SOME n E N such that n! + 1 and (n+1)! + 1 are not relatively prime.

    But we don't know what that "n" is. It could be 1000, or 10205.

    d | n! => n! = d z for some z E Z where d is a prime. I don't see anything contradictory with this. Prime factors are allowed in the factorization, right?
     
  20. Jan 9, 2010 #19
    If you have shown that d|n!, then the contradiction arises from the assumption that d also divides n! + 1 (since consecutive integers are relatively prime). However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.

    This problem is trickier than I thought when I gave the above hint.

    Petek
     
  21. Jan 9, 2010 #20

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes, and that means there is a prime d dividing both of them,

    and you proved that that d divides n!.

    So you have d | n! + 1 and (n+1)! + 1 and n!

    (if you still haven't got it … if n = 4, can d divide both 24 and 25? :wink:)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest common divisor | Relatively prime
  1. Common Divisor Proof (Replies: 6)

Loading...