How do I prove that two consecutive integers are relatively prime? In other words, how do I show if two integers have no common factors other than 1? Thanks

Printable View

- Dec 1st 2008, 12:15 PMTitaniumXrelatively prime
How do I prove that two consecutive integers are relatively prime? In other words, how do I show if two integers have no common factors other than 1? Thanks

- Dec 1st 2008, 12:22 PMMoo
Let n and n+1 be the 2 consecutive integers.

Let $\displaystyle d$ be a common divisor of n and n+1.

Hence $\displaystyle n=dk'$ and $\displaystyle n+1=dk''$ where k' and k'' are integers.

So $\displaystyle (n+1)-n=1=d(k'-k'')$

------> d must divide 1. which is not possible unless d=1 - Dec 1st 2008, 12:28 PMvincisonfire
Suppose you have some integer $\displaystyle N_0$ whose factorization is

$\displaystyle p_0^{a_0}p_1^{a_1}...p_t^{a_t} $. The consecutive integer is

$\displaystyle N_1 = p_0^{a_0}p_1^{a_1}...p_t^{a_t} + 1 $. Let $\displaystyle P $ be a prime dividing $\displaystyle N_1 $. Then $\displaystyle P $ doesn't divide $\displaystyle N_0$ otherwise it would divide the difference $\displaystyle N_1-N_0 = 1 $. This is impossible.

Therefore, there is no prime integer that divide both $\displaystyle N_0 $ and $\displaystyle N_1 $. In other words they have no common factors or are relatively prime.