Greatest common divisor | Relatively prime

kingwinner

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!

Hurkyl

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

Petek

Perfectly true, but the OP stated that he hadn't covered the Euclidean algorithm when working this problem.

Petek

kingwinner

No.

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

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

kingwinner

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!

tiny-tim

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.

kingwinner

Thanks, that makes sense.

kingwinner

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?

tiny-tim

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!

ramsey2879

If d > 1 how can it divide n! and n!+1 ?

Ivan,Cow'sSon

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.