3

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.

Community
  • 1
A A
  • 585
  • 1
    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. – Bill Dubuque Feb 14 '14 at 00:32
  • Sorry, I may have missed it! – A A Feb 14 '14 at 00:44

1 Answers1

3

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.

  • 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.
     – A A Feb 14 '14 at 00:36
  • @AA Exactly right. –  Feb 14 '14 at 00:36