Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.$ – user45878 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

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

share|cite|improve this answer
  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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.