## Greatest common divisor | Relatively prime

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!
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor

Recognitions:
Homework Help
 Quote by kingwinner How can we prove this?
Reduce mod k = n! + 1.

 Quote by CRGreathouse Reduce mod k = n! + 1.
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?

Recognitions:
Gold Member

## Greatest common divisor | Relatively prime

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

Recognitions:
Homework Help
 Quote by kingwinner 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?
Write (n+1)! + 1 in terms of n! + 1.

 Quote by Petek 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
 Quote by CRGreathouse Write (n+1)! + 1 in terms of n! + 1.
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

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

Recognitions:
Homework Help
 Quote by kingwinner 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
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.

 Quote by CRGreathouse 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.
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...

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
Hi kingwinner!
 Quote by kingwinner (n+1)! + 1 = (n+1) n! +1
ok, now subtract n! + 1 from that.

 Quote by tiny-tim Hi kingwinner! ok, now subtract n! + 1 from that.
That's exactly what I did in post #6, but I can't find my contradiction...

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
 Quote by kingwinner That's exactly what I did in post #6, but I can't find my contradiction...
 Quote by kingwinner … 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??
oh, sorry, I missed that

ok, if a prime d divides the difference, then d | (n!)n, so d | n!, so …

 Quote by tiny-tim ok, if a prime d divides the difference, then d | (n!)n, so d | n!, so …
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!

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
 Quote by kingwinner 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.
Yup … d | (n!)n => d | n! or d | n …

but if d | n, then d | n! anyway.

 Quote by tiny-tim Yup … d | (n!)n => d | n! or d | n … but if d | n, then d | n! anyway.
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
 Blog Entries: 27 Recognitions: Gold Member Homework Help Science Advisor I agree … but all you need is d | n!
 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...?

Blog Entries: 27
Recognitions:
Gold Member
Homework Help