Register to reply 
Greatest common divisor  Relatively prime 
Share this thread: 
#37
Jan1010, 07:00 PM

P: 361

Petek 


#38
Jan1010, 08:48 PM

P: 1,270

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


#39
Jan1010, 10:14 PM

P: 361

Petek 


#40
Jan1110, 01:29 AM

P: 1,270

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! 


#41
Jan1110, 03:17 AM

Sci Advisor
HW Helper
Thanks
P: 26,160




#42
Jan1110, 05:02 PM

P: 1,270

Thanks, that makes sense.



#43
Jan1110, 05:04 PM

P: 1,270

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? 


#44
Jan1110, 06:01 PM

Sci Advisor
HW Helper
Thanks
P: 26,160

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! 


#45
Jan1210, 05:18 PM

P: 894




#46
Jan1410, 01:09 AM

P: 2

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(n1)! + 1, has remainder 1, hence coprime.
kingwinner, good luck with MAT315. 


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 