# Proof of (n) and (n+1) Sharing No Prime Factors

A number $(n)$ has a set of prime factors $\{\alpha_1, \alpha_2,...\alpha_\epsilon\}$ and a number $(n+1)$ has a set of prime factors $\{\beta_1,\beta_2,...\beta_\psi\}$. The conjunction, $\{\alpha_1,\alpha_2,...\alpha_\epsilon\}\cap\{\beta_1,\beta_2,...\beta_\psi\}$ = $\emptyset$. What is the proof?

• Hint: This is equivalent to showing that $\gcd(n,n+1)=1$. To show this, use Euclidean Algorithm.$$n+1=1\times n + \boxed{1}\\ n=n\times 1 + 0$$ – learner Apr 18 '16 at 18:52
• You can see this easily from when you have $p\mid n$ and $p\mid (n+1)$, then $p \mid (n+1) - n = 1$, so $p=1$... – Sil Apr 18 '16 at 18:53

## 2 Answers

Suppose $\alpha_{i}=\beta_{j}=p$ for some $i,j$. Then, $p$ divides $n$ and $n+1$. Consequently, $p$ divides the difference $(n+1)-n=1$. But this is impossible since $p\geq 2$.

Suppose $p|n$ and $p|n+1$. Then $n = kp$ for some $k$ and $n+1 = jp$ for some $j$. That means $(n+ 1) - n = jp - kp = p(j-k)$.

Can you take it from there?