Register to reply

Greatest common divisor | Relatively prime

by kingwinner
Tags: common, divisor, greatest, prime
Share this thread:
Petek
#19
Jan9-10, 02:42 PM
Petek's Avatar
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
tiny-tim
#20
Jan9-10, 02:55 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,157
Quote Quote by kingwinner View Post
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
#21
Jan9-10, 04:19 PM
P: 1,270
Quote Quote by Petek View Post
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
#22
Jan9-10, 04:23 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,157
Quote Quote by Petek View Post
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 Quote by kingwinner View Post
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
#23
Jan9-10, 04:24 PM
Petek's Avatar
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
Petek
#24
Jan9-10, 04:27 PM
Petek's Avatar
P: 361
Quote Quote by tiny-tim View Post
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
#25
Jan9-10, 05:24 PM
P: 1,270
Quote Quote by Petek View Post
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
#26
Jan9-10, 05:36 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,157
Quote Quote by kingwinner View Post
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 Quote by kingwinner View Post
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
#27
Jan9-10, 05:52 PM
Petek's Avatar
P: 361
Quote Quote by kingwinner View Post
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
#28
Jan9-10, 05:58 PM
Petek's Avatar
P: 361
Quote Quote by tiny-tim View Post
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
#29
Jan9-10, 07:54 PM
P: 1,270
Quote Quote by Petek View Post
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
#30
Jan9-10, 08:38 PM
Petek's Avatar
P: 361
Looks good, but let me review the details tomorrow.

Petek
Petek
#31
Jan10-10, 01:48 PM
Petek's Avatar
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
Hurkyl
#32
Jan10-10, 02:02 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
Quote Quote by Petek View Post
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
#33
Jan10-10, 03:22 PM
Petek's Avatar
P: 361
Quote Quote by Hurkyl View Post
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
#34
Jan10-10, 04:35 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
Quote Quote by Petek View Post
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
#35
Jan10-10, 05:46 PM
P: 1,270
Quote Quote by Petek View Post
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
#36
Jan10-10, 06:20 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,092
Quote Quote by kingwinner View Post
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?


Register to reply

Related Discussions
Greatest Common Divisor General Math 1
Greatest common divisor Calculus & Beyond Homework 24
Greatest common divisor Calculus & Beyond Homework 19
Greatest common divisor of fractions and decimals General Math 2
Greatest common divisor of polynomials Linear & Abstract Algebra 0