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.

  • 3
    $\begingroup$ Sidenore: If you think that is uncanny, you have not seen Ramanujan's work. $\endgroup$
    – chubakueno
    Jan 5, 2014 at 7:38
  • $\begingroup$ (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.$ $\endgroup$ May 22, 2014 at 19:31
  • $\begingroup$ Make a 4 by 4 table to show that 3 (mod 4) ony occurs when 1 and 3 (mod 4) are multiplied. $\endgroup$ Aug 30, 2014 at 10:45
  • $\begingroup$ @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. $\endgroup$
    – jiten
    Jan 29, 2018 at 17:34
  • $\begingroup$ See this answer which gives a proof including both Euclid's proof and this one. $\endgroup$ Jun 12, 2021 at 22:30

2 Answers 2


(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$.

  • $\begingroup$ 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 $\endgroup$
    – jiten
    Jan 29, 2018 at 22:14
  • $\begingroup$ I am not sure why you posted this Jiten. $\endgroup$
    – user43138
    Mar 24, 2018 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.

  • $\begingroup$ Thanks, but can you please amplify your answers 1, 2? Are you able to answer my other questions? $\endgroup$ Apr 7, 2014 at 14:40
  • $\begingroup$ 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. $\endgroup$
    – jiten
    Jan 29, 2018 at 22:35

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.