Answer to Question #161084 in Combinatorics | Number Theory for Geek

Question

• Show that there are infinitely many primes p≅ 4(mod15).

Answer 1

Assume from the sake of contradiction that there exist only finitely many primes.

Denote them as $P={p1,p2,⋯,pk}$

Let $A=15⋅p1⋅p2⋯pk−1$

Then, we know that $A≡−11≡4(mod15).$

Since for all $p∈P$ such that $p∣A$

We know $A=k⋅pi,$ where $k∈Z∧pi∈P$

Hence, $A=pi⋅(15⋅p1⋅p2⋯pi−1⋅pi+1⋯pk)−1=k⋅pi$

This indicates that $pi∣1$

However, by property of primes, $pi$ should be greater than 1.

Hence, a contradiction.