Introduction to Euclidean Algorithm

Number Theory Level 1

$\begin{array}{c}&(2,3), &(3,4), &(4,5), &(5,6), &(6,7) \end{array}$

Andy wrote out a few pairs of consecutive positive integers, as shown above, and he notes that for each of these pairs, both integers do not share any positive common factor other than 1.

He then boldly asserts that no pair of consecutive positive integers share any positive common factor other than 1.

Is he correct?

No, he is wrong Yes, he is correct

3 solutions

Chung Kevin
Nov 14, 2016

Using the euclidean algorithm , we get

$\gcd(n, n+1) = \gcd (n, 1 ) = 1$

Thus, pairs of consecutive integers have a greatest common divisor of 1.

This is titled "Introduction to Euclidean Algorithm" so you should not use the algorithm itself.

William Nathanael Supriadi - 4 years, 7 months ago

Good point. Thankfully there are other solutions too :)

Chung Kevin - 4 years, 7 months ago

Shay Pecker
Nov 15, 2016

Say we have two integers (a, a+1) with a common factor d, and the integer t=a/d.
a+1/d should be an integer too.
But, (a+1)/d=a/d+1/d=t+1/d which can't be an integer, unless d=1

Nice way to work from "first principles"!

Calvin Lin Staff - 4 years, 7 months ago

Daniel Heiß
Nov 15, 2016

If x divides a and x divides b then x divides a+b, hence if x divides a and x divides a+b then x divides b. Now take divisor of n and n+1. then this divisor divides 1, hence it is 1 due to positiveness

Great explanation!

Calvin Lin Staff - 4 years, 7 months ago

Introduction to Euclidean Algorithm

3 solutions

0 pending reports