Greatest common divisor | Relatively prime

[kingwinner]

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 statement 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!

 

[CRGreathouse]

How can we prove this?

Reduce mod k = n! + 1.

 

[kingwinner]

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?

 

[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

 

[CRGreathouse]

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.

 

[kingwinner]

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

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

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
I am trying to reach a contradiction, but where is it??

 

[CRGreathouse]

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.

 

[kingwinner]

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

 

[tiny-tim]

Hi kingwinner!

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

ok, now subtract n! + 1 from that.

 

[kingwinner]

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

 

[tiny-tim]

That's exactly what I did in post #6, but I can't find my 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
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 …

 

[kingwinner]

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!

 

[tiny-tim]

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.

 

[kingwinner]

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

 

[tiny-tim]

I agree …

but all you need is d | n! ​

 

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

 

[tiny-tim]

… d | n!

But we don't know what "n" is, so there does not seem to be any contradiction...?

ah, but you started with …

Proof by contradiction:
Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1

so … ?

 

[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]

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

 

[kingwinner]

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

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]

… However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.

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!

 

[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]

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

 

[kingwinner]

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

 

[tiny-tim]

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 …

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.

 

[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

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]

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

 

[kingwinner]

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?

 

[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]

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.

 

[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.

See my post #23 in this thread.

Petek

 

[Hurkyl]

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.

 

[kingwinner]

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!

 

[Hurkyl]

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?

 

[Petek]

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

 

[kingwinner]

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?

 

[Petek]

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

 

[kingwinner]

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!

 

[tiny-tim]

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.

 

[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]

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! ​

 

[ramsey2879]

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 ?

 

[IvanCow]

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.