Greatest common divisor | Relatively prime

In summary, the claim is that n! + 1 and (n+1)! + 1 are relatively prime. Proving this using mathematical induction is a possible method, as demonstrated by the base case (n=1) and the induction hypothesis (assuming the statement is true for n=k). However, further steps are required to prove the statement for n=k+1. Another approach suggested is to use proof by contradiction, assuming that n! + 1 and (n+1)! + 1 are not relatively prime and showing that this leads to a contradiction. This can be done by considering a prime number or any integer greater than 1 that divides both numbers.
  • #36
kingwinner said:
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?
 
Physics news on Phys.org
  • #37
Hurkyl said:
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
 
  • #38
Hurkyl said:
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?
 
  • #39
kingwinner said:
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
 
  • #40
Petek said:
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!
 
  • #41
kingwinner said:
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. :wink:
 
  • #42
Thanks, that makes sense.
 
  • #43
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
kingwinner said:
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 :redface: … 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! :biggrin:
 
  • #45
kingwinner said:
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 ?
 
  • #46
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.
 

Similar threads

Replies
3
Views
2K
Replies
8
Views
1K
Replies
2
Views
2K
Replies
5
Views
2K
Replies
4
Views
2K
Replies
1
Views
2K
Replies
17
Views
2K
Back
Top