# Prime divisors of $4k - 1$

In this question, I have to prove that there exists infinitely many primes for $n = 4k - 1$. We can consider this sequence $3, 5, 7, 11, 19, 23, 31, \ldots$, which are all a form of $4k - 1$.

So, we start by considering the positive integers of the form $n=4k-1$ and their possible prime divisors.

1. Show that every prime divisor of $4k - 1$ is odd.

2. Show that an odd number is either of the form $4k - 1$ or $4k + 1$.

3. Show that a product of two numbers of the form $4k + 1$ again has that form (more precisely, given two numbers $4k + 1$, $4l + 1$, show that their product has the form $4m + 1$ for some integer $m$).

I need help up to this point to solve the rest of the question. Any pointers will be greatly appreciated!

1. Every divisor of an odd number is odd. As $4k$ is always even, $4k-1$ is therefore odd.

2.

Every number leaves a remainder of $0,1,2,$ or $3$ when divided by 4. If the number was originally odd, then it leaves a remainder of $1$ or $3$ when divided by 4.

If the number leaves a remainder of $1$ when it's divided by $4$, then it's clearly of the form $4k + 1$

If the number leaves a remainder of 3 when it's divided by 4, then it's of the form $4x + 3=4(x+1)-1$, which is of the form $4k-1$

3.

\begin{align}(4k+1)(4l+1)&=16kl+4k+4l+1 \\ &=4(4kl+k+l)+1 \end{align}

which is of the form $4m+1$

• Where are you going with this? I don't see that you reached a proof that infinitely many primes of the form $4k-1$ exist. – hardmath Sep 21 '17 at 14:53
• @hardmath The OP is unclear. it says “I need help up to this point”, which could be reasonably interpreted as “i don’t know how to do any of these steps” (which are necessary ingredients in the proof). – Erick Wong Sep 21 '17 at 15:51
• @ErickWong: Ok, I read the "I need help up to this point to solve the rest of the question" as (emphasis added) focusing on the rest of the question. Still, if Jazzachi does not wish to wait for clarification (that may never come), I'd advise adding at least a sketch of how to proceed. It is within the Answerer's control. – hardmath Sep 21 '17 at 15:57
• @hardmath I didn't finish the proof because RideTheWavelet has already done so with reference to the three questions. – user472341 Sep 21 '17 at 22:19

Assume the first three points have been proved. Then if $n=4k-1$ is not prime, it has only odd divisors (point 1), which must therefore all be of the form $4k'\pm 1$ (point 2). If all of these are of the form $4k+1,$ then $n$ itself would have to take this form (by point 3). Thus, if $n=4k-1$ is not prime, then it has a proper divisor of the form $4k'-1.$

Suppose by way of contradiction that there are only finitely many primes of the form $4k-1$, $p_{1},p_{2},\ldots,p_{n}.$ If $n$ is odd, then $\prod_{i=1}^{n}p_{i}$ is of the form $4k-1,$ and if $n$ is even, this product is of the form $4k+1,$ so let $p=\prod_{i=1}^{n}p_{i}+4$ if $n$ is odd, and otherwise let $p=\prod_{i=1}^{n}p_{i}+2.$ In either case, $p$ is of the form $4k-1.$ If $p$ were composite, it would have a proper divisor of the form $4k'-1,$ as we showed above. If this divisor is not prime, then it too has a divisor of the form $4k''-1,$ and we may repeat this argument to say that $p$ has a prime divisor $p'$ of the form $4k-1.$ But $p'$ must divide $\prod_{i=1}^{n}p_{i},$ since this is the product of all primes of the form $4k-1,$ and it cannot be the case that $p'|4$ or $p'|2,$ so in fact $p'\not|\,p,$ and thus $p$ is prime. Since $p$ is of the form $4k-1$, and strictly larger than any prime in the list $p_{1},\ldots,p_{n},$ this contradicts our assumption that this was the list of all of the primes of the form $4k-1.$ This contradiction completes the proof.

• One could also avoid the separate even/odd cases by taking $p=4\prod p_i - 1$. – Erick Wong Sep 21 '17 at 17:16