## Greatest common divisor | Relatively prime

 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!

Recognitions:
Gold Member
Staff Emeritus
 Quote by kingwinner Why is it sufficient to check only for the case where d is prime?)
Because the general case can be reduced to this particular case. Do you see how?

Recognitions:
Gold Member
 Quote by Hurkyl One never has to talk about divisibility or anything -- just finish computing the GCD with Euclidean's algorithm and get 1.
Perfectly true, but the OP stated that he hadn't covered the Euclidean algorithm when working this problem.

Petek

 Quote by Hurkyl Because the general case can be reduced to this particular case. Do you see how?
No.

Why can we assume that d is a "prime" without any loss of generality?

Recognitions:
Gold Member
 Quote by kingwinner No. Why can we assume that d is a "prime" without any loss of generality?
If d is a prime, we're done. If d is not prime, then ... . (Do you know the "fundamental theorem of arithmetic"? If not, look it up on Wikipedia,)

Petek

 Quote by Petek If d is a prime, we're done. If d is not prime, then ... . (Do you know the "fundamental theorem of arithmetic"? If not, look it up on Wikipedia,) Petek
OK, I looked it up on Wikipedia and that theorem says that every integer greater than 1 can be uniquely factored into primes.

If we assumed that d is prime that divides both n! + 1 and (n + 1)! +1 and reached a contradiction, this means that no prime divides both n! + 1 and (n + 1)! +1.

But still, why does it follow that
"No prime divides both n! + 1 and (n + 1)! +1 => no integer greater than 1 divides both n! + 1 and (n + 1)! +1" ?

(sorry, I am very new to number theory and many things do not seem so obvious to me...)

Thanks for explaining!

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
 Quote by kingwinner But still, why does it follow that "No prime divides both n! + 1 and (n + 1)! +1 => no integer greater than 1 divides both n! + 1 and (n + 1)! +1" ?
Because if an integer does divide both, then either that integer is a prime, or it isn't, whcih means it's divisible by a prime, and so that prime divides both.
 Thanks, that makes sense.
 The claim is a statement of the form "... for all natural numbers n". In this case, can we prove that n! + 1 and (n+1)! + 1 are relatively prime by mathematical induction? When I see statements like this(about some claim is true for all natural numbers n), my first thought is to prove by mathematical induction, but maybe in this case it doesn't work?

Blog Entries: 27
Recognitions:
Gold Member
Homework Help
 Quote by kingwinner When I see statements like this(about some claim is true for all natural numbers n), my first thought is to prove by mathematical induction …
erm … it shouldn't be!

Always try to prove something simply and directly, first.

If you can't se a simple proof, then try induction.
In this case, I'd be surprised if there was a proof by induction, and I'd be amazed if it was simpler!

Blog Entries: 2
 Quote by kingwinner 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...?
If d > 1 how can it divide n! and n!+1 ?
 Only using properties of gcd, in two steps you get (n!+1,(n+1)!+1) = (n!+1,n), and by the Euclidean algorithm, n!+1 = n(n-1)! + 1, has remainder 1, hence coprime. kingwinner, good luck with MAT315.