Dirichlet's Theorem on arithmetic progressions is often stated as something like:

If (a,m)=1 then there are infinite primes p such that pa(modm)

but how to come up an proof of its weak version, If (a,m)=1(a,m)=1 then there is at least one prime pp such that pa(modm)