= Solution
A <prime number> is an integer $p>1$ whose only positive divisors are $1$ and $p$. Every integer greater than one has a <prime factorization>; in particular it has a <prime> divisor.
To prove <infinitely many primes congruent to minus one modulo six>, suppose a finite list $p_1,\ldots,p_n$ contains all such <primes>, and put $P=p_1\cdots p_n$; the empty product is one. The integer $N=6P-1>1$ is <coprime> to $6$, so each <prime factor> is congruent to $1$ or $-1$ modulo $6$. If all its <prime factors>, counted with multiplicity, were congruent to $1$, their product would also be congruent to $1$. But $N\equiv-1\pmod6$. Hence some <prime> divisor $q$ satisfies $q\equiv-1\pmod6$. None of the listed <primes> divides $N$, since $N\equiv-1\pmod{p_i}$. This contradicts completeness of the list.
For <infinitely many primes congruent to one modulo six>, suppose instead that $p_1,\ldots,p_n$ lists every <prime> congruent to $1$ modulo $6$, and use
$$
N=(2P)^2+3.
$$
It is odd. Since each listed <prime> is <coprime> to $3$, $P^2\equiv1\pmod3$, so $N\equiv1\pmod3$ and $3$ does not divide it. Any <prime> divisor $q$ is therefore greater than $3$ and satisfies the <modular congruence>
$$
(2P)^2\equiv-3\pmod q.
$$
The allowed quadratic-congruence result gives $q\equiv1\pmod6$. Yet $N\equiv3\pmod{p_i}$, and $p_i>3$, so no listed <prime> divides $N$. Again there is a new <prime> in the required residue class. Thus \b[both residue classes $6k-1$ and $6k+1$ contain infinitely many <primes>].
Back to article page
