3
$\begingroup$

This is a modification of my previous post here which has completely different meanings/solutions

Given that

$R = p_1p_2\cdots p_n + 1$ where $p_1 < p_2 < \cdots < p_n$ and $p$ are the first n prime numbers.

Prove that if $R$ is not prime then $R$ must have a prime factor $q$ that is larger than $p_n$.

I directly understand that this question refers to Euclid's primes proof however; I don't know really how to even tackle this problem. I am looking over euclid's proof and will hopefully run into a 'eureka' moment.

Any advice or tips on how to solve this problem would be very helpful and appreciated.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ This was answered in your prior question. You know from that answer that the prime factors of $R$ are not among the first n primes, therefore they are all larger than the nth prime. $\endgroup$ – Bill Dubuque Feb 14 '14 at 0:32
  • $\begingroup$ Sorry, I may have missed it! $\endgroup$ – A A Feb 14 '14 at 0:44
3
$\begingroup$

Hint: If $R$ is not prime, then $R$ has a prime divisor. Convince yourself that this prime divisor isn't any of $p_1, ..., p_n$. Now use how $p_1, ..., p_n$ are defined.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the response Tyler. I think I have figured it out! 1. q cannot be in the given set p 2. q is a prime divisor of R 3. Since q is not in the set p, which are the first primes in order, q must be greater than the greatest number in that list. $\endgroup$ – A A Feb 14 '14 at 0:36
  • $\begingroup$ @AA Exactly right. $\endgroup$ – user61527 Feb 14 '14 at 0:36

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.