One of the last sections in our primes lab had to do with an interesting distribution of primes that are congruent to 1 and 3 mod 4. This means that our prime number, n, is congruent to either 1 (mod 4) or 3 (mod 4). We can divide these up into two sets of primes numbers:

$\pi_1(n)$= #{primes p| p $\leq$ n and p = 1 + 4k, for some positive integer k}

$\pi_3(n)$= #{primes p| p $\leq$ n and p = 3 + 4k, for some positive integer k}

So the question is, how many primes actually fit into these two sets?

n |
$\pi(n)$ |
$\pi_1(n)$ |
$\pi_3(n)$ |
$\pi_1(n)$/$\pi(n)$ |
$\pi_3(n)$/$\pi(n)$ |

10 |
5 |
1 |
1 |
.2 |
.2 |

25 |
9 |
3 |
4 |
.33 |
.44 |

50 |
15 |
6 |
7 |
.4 |
.47 |

100 |
26 |
11 |
12 |
.42 |
.46 |

1000 |
168 |
80 |
86 |
.48 |
.51 |

10000 |
1229 |
609 |
618 |
.5 |
.5 |

100000 |
9592 |
4783 |
4807 |
.5 |
.5 |

As we can see, as our n approaches infinity, the two sets comprise together roughly 100% of the primes. There are some primes missing, as evidenced with n is small. 2 is a good example of one that doesn’t work with this relationship. But, as we can see, when n gets really large, the relationship holds really well.

Through this, we can make an extension of our very first proof, where we found that there are an infinite number of primes.

Let’s prove: If $\pi(n) \geq \pi_1(n) + \pi_3(n)$, then as n approaches infinity, $\pi_1$ and $\pi_3$ are infinite sets.

We already know that $\pi(n)$ is an infinite set, so our question is whether $\pi_1(n)$ and/or $\pi_3(n)$ are also infinite. As n approached infinity, $pi_1(n) \approx 0.5\pi(n)$, and $pi_3(n) \approx 0.5\pi(n)$. So, we can plug in our values: $\pi(n) \geq 0.5\pi(n) + 0.5\pi(n)$, and since $\pi(n)$ is an infinite sets, it is the sum of two infinite sets. So, as n approaches infinity, $\pi_1$ and $\pi_3$ also approach infinity, so they are also infinite sets. This is what we wanted to prove in the first place, so we are done.