I'm doing a problem that states: Let $p_1,p_2,p_3...(p_n+1)$ be the first $n + 1$ primes in order.

Prove every number between $p_1 * p_2 * .... * p_n + 1$ and $p_1 * p_2 * ... * p_n + (P_n+1) - 1$ is composite (not including the two numbers).

I'm stuck on the fact that all those numbers must be a product of primes. How can I continue?

  • 2
    $\begingroup$ Well see for example that 2×3×5×7 + 2 is div. by 2, 2×3×5×7 + 3 is div. by 3, do you get the idea? $\endgroup$ – Sawarnik Mar 16 '17 at 3:15

Note how every number $N$ between $p_1\cdot p_2\ldots\cdot p_n+1$ and $p_1\cdot p_2\ldots\cdot p_n+p_{n+1}$ can be written in the form: $$N=p_1\cdot p_2\ldots\cdot p_n+k$$ with $k$ an integer and $2\le k\le p_{n+1}-1$. This means that $k$ is divisible by at least one of the primes in the product $p_1\cdot p_2\ldots\cdot p_n$ and since that prime also divides the product, that prime will divide $N$. However, it will not be equal to that prime (let's call it $q$) because $p_1\cdot p_2\ldots\cdot p_n\ge q$ (do you see why?) and $k\ge 2$.

So now we know that there is a prime $q$ such that $q$ divides $N$, but is not equal to $N$. We may conclude that $N$ is composite.


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.