1

Prove that there are infinitely many primes congruent to 3mod4 using euclid's proof for infinitely many prime number.

I guess I don't really know where to start because I don't understand euclid's proof for infinitely many primes. I guess I am kind of confused about the part after "thus it must be divisible by at least one of our finitely many primes.." I understand that part, but I don't understand how proving the p by pn leaves a remainder of 1 shows that p is not divisible by any of the primes. enter image description here

YuiTo Cheng
  • 4,705
Math Major
  • 2,234
  • That proof you have there looks wrong. The statement 'since p1,p2...pn' consitutes all primes p can't be prime' is false. p can be prime or not prime. The proof follows if you consider those 2 cases individually. Eculid's proof seems to be horribly misunderstood. – sashang May 26 '18 at 00:33
  • 2
    @sashang: the assumption was that $p_1,p_2,\dots,p_n$ were all the primes (it was assumed that there were finitely many). – robjohn Feb 11 '19 at 15:25

1 Answers1

2

If the number $p$ were divisible by one of the $p_j$, then the remainder should be zero. However if you divide $p$ by any of the $p_j$,

$$p = \left( p_j \cdot \prod_{i\neq j} p_i \right) + 1$$

hence $p \equiv 1$ mod $p_j$

Make sense?

We know there is at least one prime $q \cong 3$ mod $4$; namely $3$ itself. Suppose now that there were only a finite number of such primes, call them $q_j$. What can you say about $q_1q_2\cdots q_n$? Or $(q_1q_2\cdots q_n)^2$

Simon S
  • 26,524
  • So then there should be a number qn+1 which is not prime because it's not contained in the finite list, so it should be divisible by qn..does the proof just basically follow as above? I'm wondering why my professor specifically chose 3mod4, is it a special case? if so, how? – Math Major Nov 11 '14 at 19:03
  • 1
    @MathMajor If there were a finite set of primes $p_i$ such that $p_i\equiv 3\pmod 4, \forall i\in[1;n], i\in\mathbb N$, then the number $(p_1p_2\cdots p_n)^2+2\equiv 3\pmod 4$ would still have to have a prime divisor $q$ such that $q\equiv 3\pmod 4$ since otherwise, if its prime divisors $m_1,m_2,\ldots,m_k$ are all equivalent to $1\pmod 4$, then $(p_1p_2\cdots p_n)^2+2=m_1m_2\cdots m_k\equiv 1\cdot 1\cdots 1\equiv 1\pmod 4$, contradiction. Thus we've proved the existence of a new prime that is not in our finite set ${q_1,q_2,\ldots,q_n}$ and is equivalent to $3\pmod 4$. – user26486 Nov 11 '14 at 19:15