# Proof — Infinitely many primes of the form $4k + 3$ — origin of $4(p_1…p_k - 1) + 3$

I know there are sundry questions like this pdf — and this

(10.) Prove that any positive integer of the form $$4k + 3$$ must have a prime factor of the same form.

Because $$4k + 3 = 2(2k + 1) + 1$$, any number of the form $$4k + 3$$ must be odd.
It can't have any factors of the form $$4k = 2(2k)$$ or $$4k + 2 = 2(2k + 1)$$ which are even
— so they must have forms $$4k + 1$$ and $$4k + 3$$.
Suppose that they were all of the form $$4k + 1$$. Multiplying two such forms yields $$(4k+1)(4m+1) = 4(4km+k+m) +1$$, another $$4k+1.$$
Thus $$\Pi$$ (factors of the form $$4k + 1$$) must be another $$4... + 1.$$
Thus $$\Pi$$ (factors of the form $$4k + 3$$) must have a prime factor of the form $$4k + 3\quad (♯)$$.

I still don't understand Elementary Number Theory — Jones — p28 — Theorem 2.9.

Prove by contradiction. Suppose that there are only finitely many primes of this form $$4k + 3$$, say $$p_1, ... , p_k$$. Let $$\color{red}{m = 4(p_1 ... p_k - 1) + 3}$$. Since $$m$$ is odd, and the only even prime is $$2,$$ so each prime $$p$$ dividing m is odd.

(1 — Red) Where did this choice of $$m$$ hail from — feels uncanny?

By reason of $$(♯)$$ overhead, $$m$$ must be divisible by at least one prime of the form $$4k + 3$$ - name it $$p_i$$. Thence $$p_i$$ divides $$(4p_l ... p_k -m = 1) \implies p_i = \pm 1$$, a contradiction because $$p_i$$ is prime.

(3) How can I prefigure to consider $$4p_1...p_k - m = 1$$, in order to instigate a contradiction?

(4) Why does the method of proof here fail for proving infinitely many primes of the form $$4k + 1$$? I tried https://math.stackexchange.com/a/391103/85100.

• Sidenore: If you think that is uncanny, you have not seen Ramanujan's work. – chubakueno Jan 5 '14 at 7:38
• (4) a number of the form $4n+3$ must necessarily have a prime factor of that form, where a number in the form $4n+1$ can have all its prime factors in the form $4n+3$. There are other constructions that might work though, consider $4(p_1p_2 \cdots p_n)^2 + 1.$ – Pol van Hoften May 22 '14 at 19:31
• Make a 4 by 4 table to show that 3 (mod 4) ony occurs when 1 and 3 (mod 4) are multiplied. – Mikael Jensen Aug 30 '14 at 10:45
• @chubakueno I muddled my head with this problem a lot till I saw this post, and am interested if you provide link (not necessarily hyperlinks) to more such 'uncanny' proofs in Ramanujan's works. – jiten Jan 29 '18 at 17:34

(1) The way I see it, we are doing a proof similar to Euclid's proof that there are infinitely many primes that most are familiar with, where we get a contradiction because every integer has a prime divisor (Euclid's case say $p_1,\dots,p_n$ are all the primes, let $N=p_1\cdots p_n+1$. $N$ has a prime divisor, but then it must be one of the $p_i$ but then as $p_i \mid (p_1\cdots p_n +1)$ this implies $p_i \mid 1$, a contradiction). Our goal here is basically to construct an integer $N$ that is of the form $4k+3$ so then it will be divisible by some prime of the form $4m+3$, and then we want that to lead to a contradiction. In this case, it leads to a prime dividing $-1$, a contradiction.

(3) The product of an even number integers of the form $4k+3$ is of the form $4k+1$. A product of an odd number integers of the form $4k+3$ is again of the form $4k+3$.

(4) Every integer of the form $4k+3$ has a prime factor of the form $4k+3$ however not every integer of the form $4k+1$ has a prime factor of the form $4k+1$.

Could consider $21=3\cdot7$, $21$ is of the form $4k+1$ but $3,7$ are both of the form $4k+3$ so it has no prime factors of the form $4k+1$.

• I request if the even or odd number of $4k+3$ form primes is of any use in proving the OP. I have my own post on this topic, which is based on Wallace's book proof on the same. Based on your response, can assume that if the last term index ($N$) is odd, then ignoring $p_1$ term (as done in book) would lead to even terms, and as even terms of $4k+3$ form would lead to $4k+1$, and hence to get $4k+3$ form back, need to have odd terms of $4k+3$ form; & vice-versa for $N$ being even. But, all this is useless to me as can't show anywhere. My post at: math.stackexchange.com/q/2623096/424260 – jiten Jan 29 '18 at 22:14
• I am not sure why you posted this Jiten. – name Mar 24 '18 at 9:21
1. The need for $-1$ is that $4(p_1 p_2 ....p_k)+3$ would divisible by $3$. So to prevent this you subtract $1$.

2. $$m = 4 (p_1 p_2 \ldots p_k) -4 + 3 = 4 p_1 p_2 \ldots p_k -1$$ One could have defined $m$ like this and shown that $m \equiv 3 \mod 4$. It is just a matter of taste

3. No prime can divide $1$. $1$ is divisible only by $\pm 1$ and neither are primes.

• Thanks, but can you please amplify your answers 1, 2? Are you able to answer my other questions? – Dwayne E. Pouiller Apr 7 '14 at 14:40
• It is the opposite of the general proof of this elementary sort, where in Wallace's book (Groups, Rings & Fields, pg.#68) the $p_1$ term is removed to prevent division of the $4(p_1p_2 \cdots p_N)$ term by $3$; to achieve contradiction based approach. – jiten Jan 29 '18 at 22:35