1
$\begingroup$

I have read in a book proof regarding the infinitude of primes of the form $4n+3$. The issue is there are missing steps (as per the understanding level of mine), and want to get the 'filled missing steps' vetted (highlighted by $\color {blue}{\textrm{blue color}}$).
Will ask doubts, when am unable to understand text.
For comparison, an image of the book's proof is given.
It starts with the statement that:
Any odd prime is either of the form $4n+1$ or $4n+3$ for suitable $n \in \mathbb{ Z}$.
For later requirement, it is shown 'earlier' that product for two odd integers, of the form $4n+1$ is also of the same form, as repeated below:
> Let two primes be $4n_1+1, 4n_2+1$ with the product being : $(4n_1+1)(4n_2+1) = 4(4n_1n_2 + n_1+n_2) + 1$, i.e. of the same form.

Next, it shows infinitude of primes for the $4n+3$ form by contradiction approach, by assuming a finite number ($N$) of such primes $p_1,p_2, p_3, ..., p_N$ being of the form $4n+3$ in ascending order, with $p_1=3, p_2=7,$ $p_3=11, p_4=15$, etc.
Hence, the product of such primes (let, $M$) would also be of the same form. Let $$M = 4(p_2p_3...p_N)+3$$

Doubt 1: Why $p_1$ is removed just for the sake of it being divisible by $3$? Will it not affect the value of $M$?

Next, it states that by Theorem 9, $M$ is not divisible by any of $p_2, p_3, ..., p_N$.

Doubt 2: That proof considers all factors $p_1p_2p_3....p_N$ (i.e. not ignores $p_1$),

takes $M =p_1p_2p_3....p_N+1$, and relies on division of $M$ and $p_1p_2p_3...p_N$ by a (among the N possible) factor, let $p_1$. Then shows by contradiction that the left side ($\frac{M}{p_1} - p_2p_3...p_N$ is an integer, while the r.h.s. ($\frac{1}{p_1}$) is not an integer.

Further, $3\nmid M$, as $3\nmid 4$, $\color {blue}{\textrm{as in the equality $M - 4(p_2p_3...p_N) =3$, both terms on the l.h.s.}}$ $\color {blue}{\textrm{need be divisible by $3$.}}$

Hence, $M$ has the form $4n+3$, but no prime factor among $p_2, p_2, p_N$. The alternate form left for prime factors of $M$ is $4n+1$.

But, the product of such prime factors has already been shown to be of the form $4n+1$, rather than the form of $M$, i.e. $4n+3$.

Hence, by contradiction, there are an infinite number of primes of the form $4n+3$.

Doubt 3: Does the author take that all numbers of the form 4n+3 are odd primes? If so, then should have indicated that. Does he expect the reader to provide a proof of the same? I mean that for me saying that there are infinitely many primes of the form 4n+3, is different from saying that: 'all' numbers of the given form are prime. Also, what about the numbers of the form 4n+1. Are those also same for the primality criteria as 4n+3?

Have found very good links on MSE, here, here, here, here, & also here.

enter image description here

$\endgroup$
7
  • 1
    $\begingroup$ See math.stackexchange.com/questions/21333/… $\endgroup$ – daniel Jan 27 '18 at 7:12
  • 1
    $\begingroup$ Doubt 1: We want a number that is not divisible by $p_1$ through $p_n$. We want it in the form of $4K + 3$. So we do NOT want $3|K$ because then $3$ would divide $4K+3$. As all the other primes do not divide $3$ we can assure $p_k$ does not divide $4K + 3$ by assuring that $p_k$ DOES divide $K$. Sk $M = 4p_2p_3... p_n + 3$ is a number of the form that is not divisible by any of the primes. It may not be the only such number but it was a simple and easy one to derive. $\endgroup$ – fleablood Jan 29 '18 at 22:59
  • 1
    $\begingroup$ Doubt 2: $p_1 = 3$ and $3\not \mid M = 4K +3$ because $3$ does NOT divide $K$ or $4$ but $3$ DOES divide $3$ so $p_1 \not \mid M =4K +3$. All the other primes work in the exact opposite manner. $p_k$ does divide $K$ but NOT $3$ so $p_k \not \mid 4K + 3$. so $p_1, p_2,....p_n$ do NOT divide $4K +3$ but the reasons the pries that aren't $3$ don't, is a different reason than why $3$ doesn't. But the important bit is that none of them do divide it. $\endgroup$ – fleablood Jan 29 '18 at 23:04
  • 1
    $\begingroup$ Doubt 3: "Does the author take that all numbers of the form $4n+3$ are odd primes?" Not at all! Not even remotely! As we are assuming there are finite prime 4n+3, and there are infinite $4n+3$ there MUST be infinitely many composite $4n+3$. No-where does he assume that $4n+3$ are prime. But he has proven that all number of the form must has a prime factor that is of the form $4n + 3$. So if $4n+3$ is not prime then $4n+3 = N*p_j$ where $p_j = 4m + 3$. $\endgroup$ – fleablood Jan 29 '18 at 23:13
  • 1
    $\begingroup$ "Also, what about the numbers of the form 4n+1. Are those also same for the primality criteria as 4n+3?" No. As $(4n + 3)(4m + 3) = 4(4mn+3m+3n + 2) + 1$ it does not folllow that a number of the form $4n + 1$ must have prime factors of the form $4n+1$. So we can not prove it this way. $\endgroup$ – fleablood Jan 29 '18 at 23:34
2
$\begingroup$

Doubt 1: We are defining $M$ by this expression. There is no reason we can't choose to omit $3$ from the product in the definition.

Doubt 2: Not quite sure I understand what you're saying here. Yes, it is true that $M$ must not be divisible by any of the $3, p_2,\ldots p_N$ since its first term is divsible by $p_2\ldots p_N$ but not by $3$ and its second term is divisble by $3$ but not any of the $p_2\ldots p_N$.

Doubt 3: No the author does not assume all numbers of the form $4n+3$ are prime. Why do yo think they do? They prove there are infinitely many primes of that form by assuming there are finitely many and deriving a contradiction. I don't get what you're asking regarding $4n+1,$ but there are an infinite number of primes of that form as well.

I think you are missing some essential part of the logic here, but I can't tell what it is. Feel free to ask follow-up questions.

$\endgroup$
18
  • 1
    $\begingroup$ @jiten The logic of the proof is 1) Assume for the sake of contradiction that there are a finite number of primes of the form $4n+3.$ Call them $p_1=3,$ $p_2=7,$ $p_3=11,$ and so on till the last one $p_n.$ 2) Define the number $M=4p_2p_3\ldots p_n+3.$ (We can make any definition we want... we make this one cause leads to the contradiction.) 3) By its construction, this number is not divisible by any of the $p_i,$ is odd and moreover, is of the form $4n+3.$ But this is impossible. Hence our assumption that there are a finite number of primes of the form $4n+3$ was wrong. $\endgroup$ – spaceisdarkgreen Jan 27 '18 at 19:31
  • 1
    $\begingroup$ @jiten Have you understood the Euclid proof that there are an infinite number of primes? This is very similar (at least to the version that is a proof by contradiction). $\endgroup$ – spaceisdarkgreen Jan 27 '18 at 19:45
  • 1
    $\begingroup$ @jiten Huh? Again, you can construct any number you want.... whether or not it produces the desired contradiction is another story. (And no, not all instances of Dirichlet's theorem can be proved in an elementary way like this.) $\endgroup$ – spaceisdarkgreen Jan 27 '18 at 20:01
  • 1
    $\begingroup$ For $8k+7,$ you could attempt a similar proof as follows: 1) Assume for the sake of contradiction that $p_1=7,p_2=23,p_3=31,\ldots p_n$ are all of the primes of the form $8k+7.$ 2) Consider $M=8p_2p_3\ldots p_n + 7.$ By its construction and our assumptions it is not divisible by any primes of the form $8k+7.$ Thus (since it is odd) it must be a product of primes of the form $8k+1,$ $8k+3,$ $8k+5.$ Does this produce a contradiction like before? That depends on whether you can write a number of the form $8k+7$ as a product of numbers of the form $8k+1,$ $8k+3,$ and $8k+5.$ $\endgroup$ – spaceisdarkgreen Jan 27 '18 at 20:06
  • 2
    $\begingroup$ Re: We can get $8n+1$ by $(8k+3)(8j+3)$ or by $(8k+7)(8j+7)$ so we can't prove there are inf primes of form $8n+1$. We can get $8n + 5$ by $(8k+3)(8j+7)$ so we can't prove for form $8n+5$ and we can get $8n+7$ by $(8k+3)(8j+5)$ so we cant prove for form $8n+7$. But the only way to get $8n+3$ is but $(8k+1)(8j+3)$. So any number of the form $8n+3$ must have a factor of the form $8n+3$. $\endgroup$ – fleablood Jan 29 '18 at 23:49
1
$\begingroup$

Doubt 1: The number M is simply defined to be the product of all of the primes of the form 4n+3 except for 3. M doesn't need to be the product of all primes of that form: we simply need an impossible thing to prove by contradiction. M should exist as defined, yet it has impossible properties.

Doubt 2: $p_2,..,p_N$ are not devisors by the earlier theorem. 3 is not a divisor since the definition of M that spawned doubt 1 makes it so (i.e 3 is not a factor of $4(p_1...p_n)$, it will not be a factor of the number three larger than this)

I think the doubts come from the assumption that M must include all primes of the form 4n+3 when in fact it is just a number suitable for he proof

$\endgroup$
3
  • $\begingroup$ It is the subset of possible values that $M$ can take which is the issue (i.e., doubt #1). If $M$ can take a subset of values, then should it take only consecutive values, or can it take any values - say: product of 2nd, 4th, 7th, 11th, and so on randomly? $\endgroup$ – jiten Jan 27 '18 at 7:27
  • 1
    $\begingroup$ M can be any number you want so long as it has the following conditions: 1) M is of the form $4n+3$. 2) M is not divisible by $3, p_2, p_3,..... p_n$. $4p_2p_3...p_n + 3$ is one such number. $13*4*p_2..p_n + 3$ is another. If $n$ is even then $3p_2... p_n + 2$ is a third. If $n$ is odd then $p_2....p_n+ 6$ is also one. However for sake of simplicity the number $M = 4p_2p_3....p_n + 3$ is the easiest and clearest to work with. $\endgroup$ – fleablood Jan 29 '18 at 23:58
  • 1
    $\begingroup$ The thing is you have to come up with a number $M$ and then justify is satisfies those two conditions. The heart of this proof is proving that such an $M$ actually exists. The easiest such number to derive and prove satisfies the two conditions is $M = 4p_2...p_n + 3$. It's obviously of the form $4M + 3$ and obviously $3$ does not divide it. And obviously none of the $p_k$ divide it. It's not the only such number but ... well, it's the most obvious such number. $\endgroup$ – fleablood Jan 30 '18 at 0:08
1
$\begingroup$

I think it might be go to first go over outline or proof without proving the details.

1) An odd number has odd prime factors.

2) All odd numbers are either of the form $4n + 1$ or $4n + 3$.

3) If a composite number has only prime factors of the form $4n+1$ then that composite number is of the form $4n+1$.

3a) There for if a number is of the form $4n + 3$ it must have a prime factor of the form $4n + 3$.

4) If $p_2,..., p_n$ are prime and none are $3$ then $M = 4p_2...p_n + 3$ is not divisible by any of the $p_k$ and $M$ is not divisible by $3$.

4a) So either $M = 4p_2 .... p_n + 3$ is prime, or its prime factors are all different primes from $3, p_2,.... p_n$.

5) assume there are only finitely many primes of the form $4n+3$.

5a) so we can list them $3, p_2, p_3 .... p_n$

6) Consider $M = 4p_2,p_3... p_n + 3$.

7) By 3a) $M$ must have a prime factor of the form $4n + 3$.

7b) By 4) $3, p_2, p_3, ... p_n$ are not prime factors of $M$.

7c) So the prime factor of the form $4n + 3$ is not one of the primes $3, p_2, p_3, .... p_n$.

8) This contradicts that 5a) was a list of all the prime factors of the form $4n+3$.

=====

Okay, final time:

Claim: There are more than $7$ primes of the form $4n + 3$ and the primes $3, 7, 13,17,29,37,41$ are not all the primes of the form $4n+3$.

Proof:

Lemma: All numbers of the form $4n+3$ have a prime factor of the form $4n+3$.

Proof: Suppose not. Let $N=4n+3$ have a prime factorization of $\prod q_i^{a_i}$ and none of the $q_i= 4n+3$. As the $q_i$ are odd they must all be of the form $4n_i + 1$. By induction and several multiplications $\prod q_i^{a_i} = \prod (4n_i + 1)^{a_i} = 4M + 1$ so $N$ is not of the form $4n+3$. QED Lemma.

Now, consider then number $M = 4*(7*13*17*29*37*41)+3$. $M$ is of the form $4n + 3$ so by the Lemma, $M$ must have a prime factor, $q$ of the form $4n+3$.

What is $q$.

It can't be $3$ because: $3\not \mid M$ because $3|3$ but $3\not \mid 4*(7*13*17*29*37*41)$

It can't be $7$ because: $7\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $7\not \mid 3$

It can't be $13$ because: $13\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $13\not \mid 3$

It can't be $17$ because: $17\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $17\not \mid 3$

It can't be $29$ because: $29\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $29\not \mid 3$

It can't be $37$ because: $37\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $37\not \mid 3$

It can't be $41$ because: $41\not \mid M$ because $7|4*(7*13*17*29*37*41)$ but $41\not \mid 3$

So it must be some prime of the form $4n+3$ that is not $3, 7, 13,17,29,37,41$

So $3, 7, 13,17,29,37,41$ are not all the primes of the form $4n +3$. There must be others.

QED Claim:

So instead of proving there are more than $7$ primes, prove that for any number $n$ there are more than $m$ primes. Do it the EXACT same way. IF $3, p_2, ....., p_m$ were the ONLY primes of the form $4n+3$ then then number $M = 4(p_2....p_m) +3$ must have a prime factor of the form $4n+3$ that is different than all $3, p_2,....., p_m$. So there must be more than $m$ primes of the form $4n+3$. As there are more primes of the form than any $m$, there are infinitely many primes of the form.

BTW: $M = 4*(7*13*17*29*37*41)+3 =272228687$ is a prime number. And it is in the form of $4n+3$.

So now we know there are at least eight primes of the form $4n+3$.

If we consider $4*(7*13*17*29*37*41*272228687)+3$ we will be able to find a ninth.

.... indeed... $74108457209057911 = 271 × 273462941730841$ and $271$ is of the form $4n+3$. We can do this all day.

$\endgroup$
16
  • 1
    $\begingroup$ And $3$ is !!!!!!!***NOT***!!!!!! excluded. $3$, like EVERY other only of the $p_k$ does not divide $M$. $3$ is absolutely, positively, and utterly required to be !!!!!!!!!!***IN***CLUDED!!!!!!!! $\endgroup$ – fleablood Jan 30 '18 at 18:12
  • 1
    $\begingroup$ I addressed i) if $a|b$ and $a\not \mid c$ then $a\not \mid b+c$. So if $p_k|4p_2p_3..p_n$ (which it obviously does) and $p_k\not \mid 3$ (which it obviously does not) then $p_k\not\mid 4p_2p_3..p_n+3=M$. And as $3|3$ and $3\not\mid 4p_2p_3...p_2$ so $3\not\mid 4p_2p_3..p_n+3=M$. ii) is utterly incoherent. $\endgroup$ – fleablood Jan 31 '18 at 15:17
  • 1
    $\begingroup$ I meant "Also, why term-wise a series of (sum of) two terms are taken for M" is utterly incoherent. I have absolutely NO idea what you mean by that. $\endgroup$ – fleablood Jan 31 '18 at 15:47
  • 1
    $\begingroup$ If $a|b$ and $a\not \mid c$ then $a \not \mid b+c$ is a fundamental number theory proposition. So $3\not \mid M$. (because $3|3$ but $3\not \mid 4p_2....p_n$). And $p_2\not \mid M$. (because $p_2|4p_2....p_n$ but $p_2\not \mid 3$). And $p_3\not\mid M$ (because $p_3|4p_2....p_n$ but $p_2\not \mid 3$. And so on. So none of $3, p_2, p_3,....,p_n$ divide $M$. $\endgroup$ – fleablood Jan 31 '18 at 15:52
  • 1
    $\begingroup$ I think we've discussed it as far as we can. The proof is before you. And for the most part you understand it.There are some details thought processes as to how one can come up with it on one's own and how to adapt it true prove other things, but those are things a student must come to on his/her own with experience. $\endgroup$ – fleablood Feb 5 '18 at 17:46

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.