I have been assigned this homework problem and I'm having trouble figuring out how to prove these statements.

If $n_1,\dotsc,n_k\in${$6z+1\mid z\in\mathbb{Z}$}, show that $n_1n_2\cdot\cdot\cdot n_k\in${$6z+1\mid z\in\mathbb{Z}$}.

Next, show that {$6z+5\mid z\in\mathbb{Z}$} contains infinitely many primes. (Without using Dirichlet's Theorem).

Thank you in advance!


Just mimic Euclid's proof of the infinitude of primes.

Assume that the set of primes of the form $6k-1$ is finite, say given by $\{p_1,\ldots,p_n\}$, and consider:

$$ N = 6p_1 p_2\cdot\ldots\cdot p_n-1. \tag{1}$$ We obviously have $N\equiv -1\pmod{6}$, hence any prime number $p\mid N$ is $\equiv \pm 1\pmod{6}$ and there is at least one prime $p\mid N$ such that $p\equiv -1\pmod{6}$. However, $p\neq p_i$ for every $i\in [1,n]$, since $\gcd(N,p_1)=1$. That leads to a contradiction.

  • $\begingroup$ @MathQuestion: you're welcome. $\endgroup$ – Jack D'Aurizio Sep 25 '15 at 18:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.