In 1935, Erdos found an elementary proof that the congruence class a mod m contains infinitely many primes, provided only that gcd(a,m)=1 and a particular sum of prime divisors of m is less than 1.
Kevin O'Bryant