Greatest common divisor | Relatively prime


by kingwinner
Tags: common, divisor, greatest, prime
Petek
Petek is offline
#37
Jan10-10, 07:00 PM
Petek's Avatar
P: 361
Quote Quote by Hurkyl View Post
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
kingwinner is offline
#38
Jan10-10, 08:48 PM
P: 1,270
Quote Quote by Hurkyl View Post
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
Petek is offline
#39
Jan10-10, 10:14 PM
Petek's Avatar
P: 361
Quote Quote by kingwinner View Post
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
kingwinner is offline
#40
Jan11-10, 01:29 AM
P: 1,270
Quote Quote by Petek View Post
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
tiny-tim is offline
#41
Jan11-10, 03:17 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by kingwinner View Post
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
kingwinner is offline
#42
Jan11-10, 05:02 PM
P: 1,270
Thanks, that makes sense.
kingwinner
kingwinner is offline
#43
Jan11-10, 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?
tiny-tim
tiny-tim is offline
#44
Jan11-10, 06:01 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by kingwinner View Post
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
ramsey2879 is offline
#45
Jan12-10, 05:18 PM
P: 891
Quote Quote by kingwinner View Post
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 ?
Ivan,Cow'sSon
Ivan,Cow'sSon is offline
#46
Jan14-10, 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(n-1)! + 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