- #1

- 59

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter smithg86
- Start date

In summary, the question is whether the greatest common divisor of two successive integers (n, n+1) is always equal to 1, or if they are always coprime. Euclid's Algorithm may be used to prove this, as it is pretty obvious that if m divides n, then n+1 is not divisible by m unless m=1. This property can also be used to prove that there are infinitely many primes. There can be multiple replies to this question due to its trivial nature and the fact that more people may know the answer. If constructing a formal proof, it may take around 50 lines using Peano's axioms and "existential introduction/elimination."

- #1

- 59

- 0

Physics news on Phys.org

- #2

Homework Helper

- 726

- 3

yes, i think so.

- #3

- 59

- 0

but how would you prove it to be true?

- #4

Homework Helper

- 726

- 3

try Euclid's Algorithm...

- #5

Staff Emeritus

Science Advisor

- 8,146

- 74

- #6

Homework Helper

Gold Member

- 2,386

- 4

I saw a proof using this property to show that there are infinitely many primes.

- #7

Science Advisor

Homework Helper

- 11,597

- 1,878

how can there be 5 replies to this question?

the more trivial the inquiry the more replies.

the more trivial the inquiry the more replies.

- #8

- 1,030

- 4

- #9

- 366

- 1

mathwonk said:the more trivial the inquiry the more replies.

Duh! Because more people know the answer.

The GCD of (n, n+1) is 1.

There are several methods to prove the GCD of (n, n+1) is 1. One method is to use the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is 0. The last non-zero remainder will be the GCD. In the case of (n, n+1), the remainder will always be 1, proving that the GCD is 1.

Proving the GCD of (n, n+1) is 1 is significant because it shows that n and n+1 are relatively prime, meaning they have no common factors other than 1. This has applications in number theory and cryptography.

No, the GCD of (n, n+1) can only be 1. This is because n and n+1 are consecutive integers, and the only common factor they can have is 1.

Proving the GCD of (n, n+1) is 1 is related to the concept of coprime numbers, which are numbers that have a GCD of 1. It is also related to the fundamental theorem of arithmetic, which states that every positive integer can be uniquely expressed as a product of prime numbers. In the case of (n, n+1), n and n+1 cannot share any prime factors other than 1, further supporting the fact that their GCD is 1.

Share:

- Replies
- 8

- Views
- 814

- Replies
- 7

- Views
- 959

- Replies
- 13

- Views
- 1K

- Replies
- 25

- Views
- 1K

- Replies
- 6

- Views
- 972

- Replies
- 4

- Views
- 863

- Replies
- 2

- Views
- 611

- Replies
- 4

- Views
- 1K

- Replies
- 2

- Views
- 725

- Replies
- 3

- Views
- 1K