# Greatest common divisor | Relatively prime

by kingwinner
Tags: common, divisor, greatest, prime
 P: 361 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
HW Helper
Thanks
P: 26,167
 Quote by kingwinner 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.
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? )
P: 1,270
 Quote by Petek 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

But as you said "it does not follow that d|(n)(n!) implies that d|n!", then what should I do instead?

Thanks!
HW Helper
Thanks
P: 26,167
 Quote by Petek … However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.
 Quote by kingwinner But as you said "it does not follow that d|(n)(n!) implies that d|n!", then what should I do instead?
If d is prime, d|(n)(n!) does imply that d|n!
 P: 361 OK, I think that I now have a valid solution. Here're some hints: Use the Euclidean algorithm to derive the following identity: (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n) (or just simplify the RHS of the equation to verify the equality). Conclude that if d divides both (n + 1)! + 1 and n! + 1, then d divides n! +1 - n. Using the techniques discussed in this thread, show that this implies that d divides n. It's already been shown above that d|n gives a contradiction. HTH Petek
P: 361
 Quote by tiny-tim If d is prime, d|(n)(n!) does imply that d|n!
Correct, but the OP hadn't covered prime numbers when solving this problem.

Petek
P: 1,270
 Quote by Petek OK, I think that I now have a valid solution. Here're some hints: Use the Euclidean algorithm to derive the following identity: (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n) (or just simplify the RHS of the equation to verify the equality). Conclude that if d divides both (n + 1)! + 1 and n! + 1, then d divides n! +1 - n. Using the techniques discussed in this thread, show that this implies that d divides n. It's already been shown above that d|n gives a contradiction. HTH Petek
I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1.

And also, to get a contradiction, I think we need d|(n!) instead of d|n
HW Helper
Thanks
P: 26,167
 Quote by kingwinner I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1.
kingwinner, why are you bothering with this? The equation you found yourself …
 Quote by kingwinner 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
… is much simpler.
P: 361
 Quote by kingwinner I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1. And also, to get a contradiction, I think we need d|(n!) instead of d|n
Sorry about that. The equation should be

(n + 1)! + 1 = n(n! + 1) + (n! + 1 - n)

and everything else I wrote is OK (I hope). I just mentioned the Euclidean algorithm to motivate how I derived the equation. Finally, it was already pointed out that d|n implies d|n!.

Petek
P: 361
 Quote by tiny-tim kingwinner, why are you bothering with this? The equation you found yourself … … is much simpler.
@tiny-tim,

The difficulty is deriving a contradiction from d|n(n!) without using the theorem that p|ab implies p|a or p|b, with p prime. It's easy if you can use that theorem, but seems to require additional reasoning if you can't. Or perhaps you do have an easier argument?

Petek
P: 1,270
 Quote by Petek Sorry about that. The equation should be (n + 1)! + 1 = n(n! + 1) + (n! + 1 - n) and everything else I wrote is OK (I hope). I just mentioned the Euclidean algorithm to motivate how I derived the equation. Finally, it was already pointed out that d|n implies d|n!. Petek
(n+1)! + 1 = n (n! +1) - n + (n! +1) = (n+1)(n! +1) - n
=> n = (n+1)[n! +1] - [(n+1)! + 1]
By assumption, d divides both (n + 1)! + 1 and n! + 1
=> d divides any integer linear combination of (n + 1)! + 1 and n! + 1
=> d divides (n+1)[n! +1] - [(n+1)! + 1]
=> d|n
=> d|(n!) (since a|b => a|(bc) for any c E Z and n! = n (n-1)! )
So d|(n!) and d|(n! +1) where d>1 <-----contradiction
Thus, no integer greater than 1 divides both n! + 1 and (n + 1)! +1.

(so I think the key point is to express "n" as a linear combiation of (n + 1)! + 1 and n! + 1)

Are my reasonings here correct?
 P: 361 Looks good, but let me review the details tomorrow. Petek
 P: 361 kingwinner, "Upon further review", your solution is correct and yes, the key was to express n as a linear combination of (n + 1)! + 1 and n! + 1. Petek
Emeritus
PF Gold
P: 16,101
 Quote by Petek kingwinner, "Upon further review", your solution is correct and yes, the key was to express n as a linear combination of (n + 1)! + 1 and n! + 1. Petek
Hrm. I think simply using the Euclidean algorithm (or a very slight adjustment) to compute the GCD works out to doing the same thing.
P: 361
 Quote by Hurkyl Hrm. I think simply using the Euclidean algorithm (or a very slight adjustment) to compute the GCD works out to doing the same thing.
See my post #23 in this thread.

Petek
Emeritus
PF Gold
P: 16,101
 Quote by Petek See my post #23 in this thread. Petek
One never has to talk about divisibility or anything -- just finish computing the GCD with Euclidean's algorithm and get 1.
P: 1,270
 Quote by Petek kingwinner, "Upon further review", your solution is correct and yes, the key was to express n as a linear combination of (n + 1)! + 1 and n! + 1. Petek
Thanks for the confirmation. :)

Now I'm interested in the method of proof by contradiction about assuming d to be a PRIME (as you said originally).

The claim is n! + 1 and (n+1)! + 1 are relatively prime for ALL n E N.
So to use proof by contradiction, we should assume that
there exists SOME n E N such that n! + 1 and (n+1)! + 1 are not relatively prime.
i.e. Suppose that for SOME n E N, d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1
As shown above, this leads to a correct proof and I'm perfectly fine with it.

But why instead we can assume that d is a "prime" without any loss of generality? (i.e. why don't we have to check the case where d is NOT prime and show that it also leads to contradiction? Why is it sufficient to check only for the case where d is prime?)

Thanks!
Emeritus