Add Me!Close Menu Navigation

Prime Congruence Class

Show that there are infinitely many primes of the form 4k - 1.

Alternatively, this is equivalent to showing that there are infinite number of primes congruent to 3 mod 4.

For now, assume by way of contradiction that there are only a finite number of primes satisfying 4k-1. Let’s order them as

    \[p_1 < p_2 < \cdots < p_k\]

Using a similar argument made by Euclid on the proof of the infiniteness of primes, we now define a composite number

    \[P = \prod_{p_i}^k p_i > 1\]

We first claim that 4P-1 \equiv 4-1 \mod 4

    \begin{align*} 4P-1-4+1 &= 4(P-1) \\ & \implies 4|((4P-1)-3) \\ & \implies 4P-1 \equiv 3 \mod 4\ \blacksquare \end{align*}

Now, the congruence class of 2k+1 \mod 4 or of the odds is partitioned between 1 and 3. Now, assuming that all prime factors of 4P-1 are congruent to 1 mod 4, then it will be the case that 4P-1 \equiv 1 \mod 4. Therefore, it must be the case that at least one of the prime divisors p of 4P-1 \equiv 3 \mod 4, or that p \in \{p_1, p_2, \cdots, p_k\}.

Finally, we show that (4P-1, p_i)=1\fa 1 \le i \le k.

    \begin{align*} (4P-1, p_i) &= (\left(4\prod_{p_j} p_j\right) - 1, p_i) \\ &= (\frac{4\prod_{p_j} p_j}{p_i} \times p_i - 1, p_i) \\ &= (p_i-1,p_i) \\ &= 1\ \blacksquare \end{align*}

Therefore, there cannot exists a prime p_i of the form 4k-1 that is a divisor of 4P-1, which leads to a contradiction as the above shows that P must have some p_i as its factor. Therefore, it cannot be the case that there are only a finite number of primes of the form 4k-1. \blacksquare

Posted By Lee


  • Pingback: URL()