Greatest common divisor | Relatively prime

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.

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?

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

tiny-tim

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

kingwinner

OK, I follow your arguments that IF d|n!, then we're done.

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

Thanks!

tiny-tim

If d is prime, d|(n)(n!) does imply that d|n!

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

Petek

Correct, but the OP hadn't covered prime numbers when solving this problem.

Petek

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

tiny-tim

kingwinner, why are you bothering with this? The equation you found yourself …
… is much simpler.

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

Petek

@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

kingwinner

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

Petek

Looks good, but let me review the details tomorrow.

Petek

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

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.

Petek

See my post #23 in this thread.

Petek

Hurkyl

One never has to talk about divisibility or anything -- just finish computing the GCD with Euclidean's algorithm and get 1.