2
$\begingroup$

I am studying the proof of the statement

there are infinitely many primes congruent to $1 \bmod 4$

Here is a snippet of the proof:

we first define $a$: $$a = (p_1p_2\cdots p_\ell)+1,\qquad p_i \in \mathbb P$$ but by unique prime factorization theorem, a can also be written as: $$a = q_1q_2\cdots q_n, \qquad q_i \in \mathbb P$$ we know $\{q_1,q_2,\ldots,q_n\}\cap\{p_1,p_2,\ldots,p_\ell\} = \emptyset$

How do I prove the last sentence? I was thinking using contradiction...assume that $p_i$ is in both set $$p_ix+1 = a = p_iy: x,y \in \Bbb Z$$ $$p_i(y-x) = 1$$ so that $p_i$ is not a prime, the only integer solution is $p_i = 1$ (it seems to me that if $a = (p_1p_2\cdots p_\ell)+2, p_i \in \mathbb P$, this proof will fail)

I didn't use any knowledge in math to prove it...is there a better proof?

$\endgroup$
  • 1
    $\begingroup$ Yes, that method does not work with $\ldots +2$. In fact it can happen then that $2\in\{q_1,\ldots,q_n\}\cap\{p_1,\ldots,p_l\}$. $\endgroup$ – Hagen von Eitzen Nov 2 '15 at 19:42
  • 1
    $\begingroup$ This may be helpful. I'm not sure I see the link between the proof that there are infinitely many primes of the form $4k+1$, and the rest of your question (for $4k+3$, it's easier). Here you are merely dealing with Euclid's proof that there are infinitely many primes (of any kind). $\endgroup$ – Jean-Claude Arbaut Nov 2 '15 at 19:51
  • $\begingroup$ @Jean-ClaudeArbaut The actual proof of infinitely many primes congruent to 1 mod 4 is by first assuming that there are finitely many such primes: $p_1,p_2...p_l$, then we construct an integer $a = (p_1p_2...p_l)^2+1$, and we have prime factorization of a : $a=q_1q_2...q_n$ we know that $a \equiv 0 \pmod {q_i}$ in other words $(p_1p_2...p_l)^2 \equiv -1 \pmod {q_i}$, but since $q_i$ can not be a prime congruent to 1 mod 4 (this is the snippet), $q_i$ must be a prime congruent to 3 mod 4, but by the law of reciprocity, -1 is not a quadratic residue of $q_i$ (contradiction) $\endgroup$ – watashiSHUN Nov 2 '15 at 21:36
  • $\begingroup$ That's what the first link in my comment refers to. However, your $a$ is $p_1p_2...p_n+1$, not $(p_1p_2...p_n)^2+1$. That's why I say it resembles most Euclide's proof. And since quadratic reciprocity is significantly more elaborate, I feel strange that you are stuck on a simpler question (these are basic properties of divisibility). I was just curious about that. $\endgroup$ – Jean-Claude Arbaut Nov 3 '15 at 11:13
2
$\begingroup$

$$ (p_1\cdots p_\ell) + 1 \overset{\large\text{?}} = q_1 \cdots q_n $$ $$ (p_1\cdots p_\ell) - (q_1 \cdots q_n) \overset{\large\text{?}} = 1 \tag 1 $$ What would happen if $p_1 = q_1$? Then $(1)$ would become $$ p_1 \Big( (p_2 \cdots p_\ell) - (q_2\cdots q_n) \Big) = 1. $$ That would mean $1$ is divisible by the prime number $p_1$. And we get the same conclusion if $p_1 = q_6$ or $p_8 = q_5$, etc. The number $1$ cannot be divisible by a primes, so we have to conclude $p_1$ is not in the intersection of those two sets. Nor is $p_2$, for the same reason, etc.

$\endgroup$
1
$\begingroup$

Let's say $p_j$ divides $a$. Then: $a = kp_j = \prod p_i + 1 \Rightarrow p_j\cdot(k- \underset{{i \neq j}}\prod p_i) = 1$. This means that $p_j$ divides $1$, therefore $p_j = 1$, which is a contradiction because $p_j$ is prime.

Therefore the two sets have to be disjoint.

$\endgroup$

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.