Greatest common divisor | Relatively prime

[Petek]

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]

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]

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]

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]

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]

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?

 

[Petek]

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]

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]

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]

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]

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]

Thanks, that makes sense.

 

[kingwinner]

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]

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]

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 ?

 

[IvanCow]

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.