Let $p_1=2, p_2=3,…,p_n$ be the first $n$ primes and suppose N=$p_1$$p_2$...$p_n$ If $N=ab$, prove that $a+b$ is divisible by a prime greater than $p_n$

Posted this question last week but I didn't know how to format the question well so I am reposting.

  • $\begingroup$ Please do not use tags like proof-writing or formal-proofs if your question is just a usual math statement. These are for more specific purposes. $\endgroup$ – 6005 Sep 24 '16 at 18:25

Partition the primes into two (possibly empty) sets, $A$ and $B$, and let $a=\prod_{p_i\in A} p_i, b = \prod_{p_j\in B} p_j$, so that $N = a \cdot b$. We can always do this for any $a$ and $b$ if we let the empty product equal $1$. We will prove the statement by contradiction.

Suppose $a + b$ were not divisible by any prime greater than $p_n$. Then some prime $p_k$ in $A$ or $B$ divides $a + b$, hence $p_k$ divides both $a$ and $b$. But that contradicts the definition of prime; since both $a$ and $b$ consist solely of primes, and $p_k$ cannot be a factor of both, therefore it cannot be the case that any $p_k$ divides $a + b$. Hence, $a + b$ is divisible by a prime greater than $p_n$.

| cite | improve this answer | |

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.