2

Given that

$R = p_1p_2\cdots p_n + 1$ where $p_1 < p_2 < \cdots < p_n$ and $p$ are 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 infinite primes proof however; Honestly, I don't know really how to even begin this problem.

Any advice on this problem would be very helpful and appreciated.

Community
  • 1
A A
  • 585
  • 6
    That's false as written; consider taking $p_1=3$ and $p_2=5$, for example, so that $R=16$ has only factors of $2$, which is less than $5$. It is important to state that $p_1<\cdots<p_n$ are the *first* $n$ prime numbers. – Zev Chonoles Feb 13 '14 at 23:19
  • 1
    @ZevChonoles : Euclid's proof didn't say they were the first $n$ prime numbers, but only that they are some finite set of prime numbers. (But it is true if they are the first $n$ prime numbers, then the prime factors of $R$ must be bigger than all of them.) – Michael Hardy Feb 13 '14 at 23:21
  • 'larger' here would be better as 'different than all the $p_i$'; this is still than enough to show that any finite list can't contain them all. – Steven Stadnicki Feb 13 '14 at 23:22
  • @Michael: Indeed, I'm only assuming that since the question asks for "larger", the source of the OP's question likely intended $p_1,\ldots,p_n$ to be the first $n$ primes, even though Euclid's proof is about any finite set of primes. – Zev Chonoles Feb 13 '14 at 23:22

1 Answers1

4

It's not true: If $p_1=5$ and $p_2 = 7$, and that's your sequence, then $p_1 p_2 + 1$ has prime factors $2$ and $3$. Those numbers are not bigger than $5$ and $7$.

What Euclid showed is that if you have any finite set of prime numbers, and you multiply them and then add $1$, then the prime factors of the number you get are not in the finite set you started with. That's not the same as saying they're bigger than any of the numbers in the set you started with. That's not true: sometimes they're actually smaller than all of them.

So you have some primes $p_1,\ldots,p_n$. The number $R=(p_1\cdots p_n)+1$ leaves a remainder of $1$ when divided by any of $p_1,\ldots,p_n$; therefore it is divisible by none of them. Its prime factors are therefore not in the set $\{p_1,\ldots,p_n\}$.

For example, consider

\begin{align} 888 & = 2\cdot3\cdot37 \\ 889 & = 7\cdot127 \\ 890 & = 2\cdot5\cdot89 \\ 891 & = 3\cdot3\cdot3\cdot3\cdot11 \\ & {}\ \vdots \end{align}

The next number after $888$ cannot be $37$ because you don't get another number divisible by $37$ until you've gone $37$ steps beyond that, up to $888 + 37$. It cannot be divisible by $3$ since you don't get another number divisible by $3$ until you get to $888+3$. It cannot be divisible by $2$ since you don't get another number divisible by $3$ until you get to $888+2$. Therefore its prime factors are not in the set $\{2,3,37\}$.

Michael Hardy
  • 1
  • Very interesting, I will certainly look into this further. Thank you for the great response Michael! – A A Feb 13 '14 at 23:47
  • 1
    Maybe I should warn you that many respectable mathematicians, Dirichlet among them, mistakenly say that what Euclid wrote was a proof by contradiction that began by assuming that only finitely many primes exist. Once you've got that assumption, it follows that those finitely many primes have to be the smallest $n$ primes (for some $n$). Even authors who don't present it as a proof by contradiction often begin by considering the smallest $n$ primes. That's relatively (but maybe not completely) harmless, but it is historically false to say that that's how Euclid did it. – Michael Hardy Feb 14 '14 at 01:22
  • 1
    In 2009 a joint paper by me and Catherine Woodgold appeared in The Mathematical Intelligencer debunking the historical error and explaining how Euclid's actual proof is better than some of those falsely reported to have been his proof. – Michael Hardy Feb 14 '14 at 01:24
  • Thank you Michael, that is a very interesting historical fact.

    It can be found through the following link, in case anyone else here wants to read it: http://link.springer.com/article/10.1007%2Fs00283-009-9064-8

     – A A Feb 14 '14 at 01:52