Does gcd(n, n+1)=1?

  • Thread starter smithg86
  • Start date
  • #1
59
0

Main Question or Discussion Point

is the gcd of two successive integers (n, n+1) always equal to 1? i.e., are two successive integers always coprime? it seems like this is the case, but how would you prove this? (this came up in my logic/proof class, but the professor wouldn't or couldn't prove it - this isn't a HW question.)
 

Answers and Replies

  • #2
mjsd
Homework Helper
726
3
yes, i think so.
 
  • #3
59
0
but how would you prove it to be true?
 
  • #4
mjsd
Homework Helper
726
3
try Euclid's Algorithm...
 
  • #5
cristo
Staff Emeritus
Science Advisor
8,107
73
Isn't it pretty obvious? suppose m divides n, then n=jm for some j. But then n+1=jm+1 which is not divisible by m (unless m=1). Thus n and n+1 are coprime.
 
  • #6
JasonRox
Homework Helper
Gold Member
2,314
3
It's neat that you brought that up.

I saw a proof using this property to show that there are infinitely many primes.
 
  • #7
mathwonk
Science Advisor
Homework Helper
10,819
983
how can there be 5 replies to this question?

the more trivial the inquiry the more replies.
 
  • #8
1,030
4
If this comes from a logic class, then I'm assuming you need to construct a formal proof starting from Peano's axioms, with the "existential introduction/elimination", etc. This proposition should take about 50 lines to prove, if you're lucky.
 
  • #9
367
1
the more trivial the inquiry the more replies.
Duh! Because more people know the answer.
 

Related Threads on Does gcd(n, n+1)=1?

Replies
1
Views
4K
  • Last Post
Replies
12
Views
9K
  • Last Post
Replies
2
Views
4K
Replies
2
Views
2K
Replies
21
Views
5K
  • Last Post
Replies
5
Views
3K
  • Last Post
3
Replies
59
Views
11K
  • Last Post
Replies
11
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
2K
Top