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

Homework Help: Prove gcd(nn!, n!+1)=1

  1. Apr 10, 2012 #1
    1. The problem statement, all variables and given/known data
    For any [itex]n \in \mathbb{N}[/itex], find [itex]\mathrm{gcd}(n!+1,(n+1)!+1)[/itex]. First come up with a conjecture, then prove it.

    2. The attempt at a solution
    By testing some values, it seems like [itex]\mathrm{gcd}(n!+1,(n+1)!+1) = 1[/itex]

    I'm trying to prove this by induction. I'll leave out the inductive assumption and base case verification because I can do those.

    I have [itex]\mathrm{gcd}(n!+1,(n+1)!+1) = 1[/itex] and I'm trying to show that [itex]\mathrm{gcd}((n+1)!+1,(n+2)!+1) = 1[/itex].

    I can simplify what's given to me to [itex]\mathrm{gcd}(nn!, n!+1)=1[/itex] but I can't find out how to get it into the form I want it. Can anybody look at what I'm doing and give me any guidance?

    [itex]\mathrm{gcd}(n!+1,(n+1)!+1) = 1 \implies \mathrm{gcd}(n!+1,(n+1)n!+1) = 1 \implies \mathrm{gcd}(n!+1,nn!+n!+1) = 1 \implies \mathrm{gcd}((n)n!, n!+1) = 1[/itex]
     
  2. jcsd
  3. Apr 11, 2012 #2

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    I wouldn't bother with induction here.

    Try to argue as follows. If a prime divides both n!+1 and (n+1)!+1, it will divide their difference. What does this imply?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook