Register to reply 
Greatest common divisor  Relatively prime 
Share this thread: 
#19
Jan910, 02:42 PM

P: 361

If you have shown that dn!, 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 dn!. 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 


#20
Jan910, 02:55 PM

Sci Advisor
HW Helper
Thanks
P: 26,160

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


#21
Jan910, 04:19 PM

P: 1,270

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


#22
Jan910, 04:23 PM

Sci Advisor
HW Helper
Thanks
P: 26,160




#23
Jan910, 04:24 PM

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 dn gives a contradiction. HTH Petek 


#24
Jan910, 04:27 PM

P: 361

Petek 


#25
Jan910, 05:24 PM

P: 1,270

And also, to get a contradiction, I think we need d(n!) instead of dn 


#26
Jan910, 05:36 PM

Sci Advisor
HW Helper
Thanks
P: 26,160




#27
Jan910, 05:52 PM

P: 361

(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 dn implies dn!. Petek 


#28
Jan910, 05:58 PM

P: 361

The difficulty is deriving a contradiction from dn(n!) without using the theorem that pab implies pa or pb, 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 


#29
Jan910, 07:54 PM

P: 1,270

=> 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] => dn => d(n!) (since ab => a(bc) for any c E Z and n! = n (n1)! ) 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? 


#31
Jan1010, 01:48 PM

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 


#32
Jan1010, 02:02 PM

Emeritus
Sci Advisor
PF Gold
P: 16,099




#34
Jan1010, 04:35 PM

Emeritus
Sci Advisor
PF Gold
P: 16,099




#35
Jan1010, 05:46 PM

P: 1,270

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! 


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 