# relatively prime

• Dec 1st 2008, 12:15 PM
TitaniumX
relatively 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 PM
Moo
Quote:

Originally Posted by TitaniumX
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

Let n and n+1 be the 2 consecutive integers.

Let $d$ be a common divisor of n and n+1.
Hence $n=dk'$ and $n+1=dk''$ where k' and k'' are integers.

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

------> d must divide 1. which is not possible unless d=1
• Dec 1st 2008, 12:28 PM
vincisonfire
Suppose you have some integer $N_0$ whose factorization is
$p_0^{a_0}p_1^{a_1}...p_t^{a_t}$. The consecutive integer is
$N_1 = p_0^{a_0}p_1^{a_1}...p_t^{a_t} + 1$. Let $P$ be a prime dividing $N_1$. Then $P$ doesn't divide $N_0$ otherwise it would divide the difference $N_1-N_0 = 1$. This is impossible.
Therefore, there is no prime integer that divide both $N_0$ and $N_1$. In other words they have no common factors or are relatively prime.