Greatest common divisor | Relatively prime

Click For Summary

Discussion Overview

The discussion revolves around the claim that n! + 1 and (n+1)! + 1 are relatively prime. Participants explore various methods of proof, including mathematical induction and proof by contradiction, while addressing the challenges of modular arithmetic and the properties of prime numbers.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes using mathematical induction to prove that n! + 1 and (n+1)! + 1 are relatively prime, starting with a base case.
  • Another participant suggests reducing the problem using modular arithmetic, although some express a lack of familiarity with this concept.
  • A proof by contradiction is proposed, where participants consider a prime number that divides both expressions, leading to a discussion on the implications of such a divisor.
  • Participants discuss how to express (n+1)! + 1 in terms of n! + 1, with varying levels of success and clarity.
  • There is a focus on the implications of divisibility and the conditions under which a contradiction might arise, particularly concerning prime factors and their properties.
  • Some participants question the validity of certain steps in the proof process, particularly regarding the assumptions made about divisibility and the nature of integers involved.
  • Hints are provided to guide participants towards a valid solution, including the use of the Euclidean algorithm to derive identities related to the problem.

Areas of Agreement / Disagreement

Participants express differing views on the best approach to proving the claim, with some favoring induction and others preferring contradiction. There is no consensus on a definitive proof method, and the discussion remains unresolved regarding the most effective strategy.

Contextual Notes

Some participants indicate limitations in their understanding of modular arithmetic and prime number theory, which may affect their ability to follow certain lines of reasoning. The discussion also highlights the complexity of the problem, with multiple approaches being explored without a clear resolution.

kingwinner
Messages
1,266
Reaction score
0
Claim: n! + 1 and (n+1)! + 1 are relatively prime.

How can we prove this? Can we use mathematical induction?
Base case: (n=1)
gcd(2,3)=1
Therefore, the statement is true for n=1.

Assuming the statement is true for n=k: gcd(k! + 1,(k+1)! + 1)=1 (induction hypothesis), we need to show that it's true for n=k+1. But I am stuck here. How can we use the induction hypothesis to prove this?

Or am I even on the right track thinking of using induction?

Thanks for any help!
 
Physics news on Phys.org
kingwinner said:
How can we prove this?

Reduce mod k = n! + 1.
 
CRGreathouse said:
Reduce mod k = n! + 1.
I have no background about modular arithmetic right now. It is an exercise from the first chapter of my book about "divisibility" and "relative primes". How can we prove it without assuming knowledge about modular arithmetic?
 
Last edited:
Try a proof by contradiction: Suppose that n! + 1 and (n + 1)! +1 are not relatively prime. Let p be a prime number that divides both numbers. Then p divides the difference, and so ... (Can you do the rest?). (Or if you haven't covered prime numbers yet, let d be any integer greater than 1 that divides both numbers and then continue as above.)

HTH

Petek
 
kingwinner said:
I have no background about modular arithmetic right now. It is an exercise from the first chapter of my book about "divisibility" and "relative primes". How can we prove it without assuming knowledge about modular arithmetic?

Write (n+1)! + 1 in terms of n! + 1.
 
Petek said:
Try a proof by contradiction: Suppose that n! + 1 and (n + 1)! +1 are not relatively prime. Let p be a prime number that divides both numbers. Then p divides the difference, and so ... (Can you do the rest?). (Or if you haven't covered prime numbers yet, let d be any integer greater than 1 that divides both numbers and then continue as above.)

HTH

Petek

CRGreathouse said:
Write (n+1)! + 1 in terms of n! + 1.
I am not sure how to express (n+1)! + 1 in terms of n! + 1, the best I can think of is
(n+1)! + 1 = (n+1) n! +1

Proof by contradiction:
Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1
=> d divides (n + 1)! - n! = (n+1) n! -n! = n!(n+1-1) = (n!)n
i.e. d divides (n!)n
I am trying to reach a contradiction, but where is it??
 
Last edited:
kingwinner said:
I am not sure how to express (n+1)! + 1 in terms of n! + 1, the best I can think of is
(n+1)! + 1 = (n+1) n! +1

Good first step: you've written it in terms of n!. Now you want to write it in terms of k = n! + 1, so replace all instances of n! by (k - 1) and expand.
 
CRGreathouse said:
Good first step: you've written it in terms of n!. Now you want to write it in terms of k = n! + 1, so replace all instances of n! by (k - 1) and expand.
OK!
(n+1)! + 1 = (n+1) n! +1

Let k= n! + 1 (=> n! = k-1)
Then (n+1)! + 1 = (n+1) n! +1 = (n+1)(k-1) +1
= nk -n +k -1 +1
=n (n! +1) - n + (n! +1)

But I still don't see where the "contradiction" is...
 
Hi kingwinner! :smile:
kingwinner said:
(n+1)! + 1 = (n+1) n! +1

ok, now subtract n! + 1 from that. :wink:
 
  • #10
tiny-tim said:
Hi kingwinner! :smile:


ok, now subtract n! + 1 from that. :wink:

That's exactly what I did in post #6, but I can't find my contradiction...
 
  • #11
kingwinner said:
That's exactly what I did in post #6, but I can't find my contradiction...
kingwinner said:
… Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1
=> d divides (n + 1)! - n! = (n+1) n! -n! = n!(n+1-1) = (n!)n
i.e. d divides (n!)n
I am trying to reach a contradiction, but where is it??

oh, sorry, I missed that :redface: …

ok, if a prime d divides the difference, then d | (n!)n, so d | n!, so … :smile:
 
  • #12
tiny-tim said:
ok, if a prime d divides the difference, then d | (n!)n, so d | n!, so … :smile:

Actually Petek was right, I haven't read the chapter about "primes" yet, so I assume no results about primes, so I let d to be any integer greater than 1 that divides both numbers. How should I continue?

But by the way, why if d is a prime and d | (n!)n => d | n! ?
One theorem in the later chapters says: If p is a prime, then p|(abc) => p|a OR p|b OR p|c.

Thanks!
 
  • #13
kingwinner said:
But by the way, why if d is a prime and d | (n!)n => d | n! ?
One theorem in the later chapters says: If p is a prime, then p|(abc) => p|a OR p|b OR p|c.

Yup … d | (n!)n => d | n! or d | n …

but if d | n, then d | n! anyway. :wink:
 
  • #14
tiny-tim said:
Yup … d | (n!)n => d | n! or d | n …

but if d | n, then d | n! anyway. :wink:

But I think the converse is false.
d | (n!)n => d|n or d|(n-1) or d|(n-2) or...or d|2 or d|1 or d|n
=> d|n or d|(n-1) or d|(n-2) or...or d|2 or d|1
 
  • #15
I agree :smile: …

but all you need is d | n! :wink:​
 
  • #16
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...?
 
  • #17
kingwinner said:
… d | n!

But we don't know what "n" is, so there does not seem to be any contradiction...?

ah, but you started with …
kingwinner said:
Proof by contradiction:
Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1

so … ? :wink:
 
  • #18
The claim is n! + 1 and (n+1)! + 1 are relatively prime for ALL n E N.

So to use proof by contradiction, we assume that
there exists SOME n E N such that n! + 1 and (n+1)! + 1 are not relatively prime.

But we don't know what that "n" is. It could be 1000, or 10205.

d | n! => n! = d z for some z E Z where d is a prime. I don't see anything contradictory with this. Prime factors are allowed in the factorization, right?
 
  • #19
If you have shown that d|n!, then the contradiction arises from the assumption that d also divides n! + 1 (since consecutive integers are relatively prime). However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.

This problem is trickier than I thought when I gave the above hint.

Petek
 
  • #20
kingwinner said:
The claim is n! + 1 and (n+1)! + 1 are relatively prime for ALL n E N.

So to use proof by contradiction, we assume that
there exists SOME n E N such that n! + 1 and (n+1)! + 1 are not relatively prime.

Yes, and that means there is a prime d dividing both of them,

and you proved that that d divides n!.

So you have d | n! + 1 and (n+1)! + 1 and n!

(if you still haven't got it … if n = 4, can d divide both 24 and 25? :wink:)
 
  • #21
Petek said:
If you have shown that d|n!, then the contradiction arises from the assumption that d also divides n! + 1 (since consecutive integers are relatively prime). However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.

This problem is trickier than I thought when I gave the above hint.

Petek

OK, I follow your arguments that IF d|n!, then we're done.

But as you said "it does not follow that d|(n)(n!) implies that d|n!", then what should I do instead?

Thanks!
 
  • #22
Petek said:
… However, it does not follow that d|(n)(n!) implies that d|n!. For example 32|(6)(6!), but 32 does not divide 6!.
kingwinner said:
But as you said "it does not follow that d|(n)(n!) implies that d|n!", then what should I do instead?

If d is prime, d|(n)(n!) does imply that d|n! :rolleyes:
 
  • #23
OK, I think that I now have a valid solution. Here're some hints:

Use the Euclidean algorithm to derive the following identity:

(n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n)

(or just simplify the RHS of the equation to verify the equality).

Conclude that if d divides both (n + 1)! + 1 and n! + 1, then d divides n! +1 - n. Using the techniques discussed in this thread, show that this implies that d divides n. It's already been shown above that d|n gives a contradiction.

HTH

Petek
 
Last edited:
  • #24
tiny-tim said:
If d is prime, d|(n)(n!) does imply that d|n! :rolleyes:

Correct, but the OP hadn't covered prime numbers when solving this problem.

Petek
 
  • #25
Petek said:
OK, I think that I now have a valid solution. Here're some hints:

Use the Euclidean algorithm to derive the following identity:

(n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n)

(or just simplify the RHS of the equation to verify the equality).

Conclude that if d divides both (n + 1)! + 1 and n! + 1, then d divides n! +1 - n. Using the techniques discussed in this thread, show that this implies that d divides n. It's already been shown above that d|n gives a contradiction.

HTH

Petek
I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1.

And also, to get a contradiction, I think we need d|(n!) instead of d|n
 
Last edited:
  • #26
kingwinner said:
I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1.

kingwinner, why are you bothering with this? :confused: The equation you found yourself …
kingwinner said:
Proof by contradiction:
Suppose d is an integer greater than 1 that divides both n! + 1 and (n + 1)! +1
=> d divides (n + 1)! - n! = (n+1) n! -n! = n!(n+1-1) = (n!)n
i.e. d divides (n!)n
… is much simpler. :smile:
 
  • #27
kingwinner said:
I haven't learned Euclidean algorithm yet...and also, I fail to see why (n + 1)! + 1 = (n - 1)(n! + 1) + (n! + 1 - n). I tried simplifying the RHS but I got n! n instead of (n + 1)! + 1.

And also, to get a contradiction, I think we need d|(n!) instead of d|n

Sorry about that. The equation should be

(n + 1)! + 1 = n(n! + 1) + (n! + 1 - n)

and everything else I wrote is OK (I hope). I just mentioned the Euclidean algorithm to motivate how I derived the equation. Finally, it was already pointed out that d|n implies d|n!.

Petek
 
  • #28
tiny-tim said:
kingwinner, why are you bothering with this? :confused: The equation you found yourself …

… is much simpler. :smile:

@tiny-tim,

The difficulty is deriving a contradiction from d|n(n!) without using the theorem that p|ab implies p|a or p|b, with p prime. It's easy if you can use that theorem, but seems to require additional reasoning if you can't. Or perhaps you do have an easier argument?

Petek
 
  • #29
Petek said:
Sorry about that. The equation should be

(n + 1)! + 1 = n(n! + 1) + (n! + 1 - n)

and everything else I wrote is OK (I hope). I just mentioned the Euclidean algorithm to motivate how I derived the equation. Finally, it was already pointed out that d|n implies d|n!.

Petek

(n+1)! + 1 = n (n! +1) - n + (n! +1) = (n+1)(n! +1) - n
=> n = (n+1)[n! +1] - [(n+1)! + 1]
By assumption, d divides both (n + 1)! + 1 and n! + 1
=> d divides any integer linear combination of (n + 1)! + 1 and n! + 1
=> d divides (n+1)[n! +1] - [(n+1)! + 1]
=> d|n
=> d|(n!) (since a|b => a|(bc) for any c E Z and n! = n (n-1)! )
So d|(n!) and d|(n! +1) where d>1 <-----contradiction
Thus, no integer greater than 1 divides both n! + 1 and (n + 1)! +1.


(so I think the key point is to express "n" as a linear combiation of (n + 1)! + 1 and n! + 1)

Are my reasonings here correct?
 
Last edited:
  • #30
Looks good, but let me review the details tomorrow.

Petek
 

Similar threads

MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Equivalent definitons for primitive polynomials
  • · Replies 24 ·
Replies
24
Views
2K
Undergrad Understanding the Results of gcd(x,n)
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
  • · Replies 8 ·
Replies
8
Views
5K
Graduate Coefficients of Chebyshev polynomials
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Localising a non integral domain at a prime
  • · Replies 17 ·
Replies
17
Views
3K
Undergrad Uniqueness of reduced row echelon form (proof verification)
  • · Replies 4 ·
Replies
4
Views
3K
Can anyone please review/verify this proof of greatest common divisor?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Proving General Associativity for Group by induction
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K