3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$$ $\endgroup$ – learner Apr 18 '16 at 18:52
  • 1
    $\begingroup$ 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$... $\endgroup$ – Sil Apr 18 '16 at 18:53
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.