# Greatest common divisor | Relatively prime

by kingwinner
Tags: common, divisor, greatest, prime
P: 361
 Quote by Hurkyl 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
P: 1,270
 Quote by Hurkyl 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?
P: 361
 Quote by kingwinner 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
P: 1,270
 Quote by 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
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!
HW Helper
Thanks
P: 26,148
 Quote by kingwinner 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.
 P: 1,270 Thanks, that makes sense.
 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?
HW Helper
Thanks
P: 26,148
 Quote by kingwinner 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!
P: 894
 Quote by 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...?
If d > 1 how can it divide n! and n!+1 ?
 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(n-1)! + 1, has remainder 1, hence coprime. kingwinner, good luck with MAT315.

 Related Discussions General Math 1 Calculus & Beyond Homework 24 Calculus & Beyond Homework 19 General Math 2 Linear & Abstract Algebra 0