What is the simplest proof one can think of (perhaps as close as possible to the standard Euclidean one) that there are infinitely many primes of the form $36k-1$?
If you consider something like $36p_1p_2\ldots p_n - 1$ then there would a prime factor of the form $4m-1$, but it might not be congruent to $(-1)$ mod $9$.
More generally, my aim is to give an elementary proof that there is an infinite sequence $a_1, a_2, \ldots$ of positive integers such that GCD$(36a_i - 1, 36a_j - 1) = 1$ for $i\neq j$.
Any help appreciated!