1. ## infinite primes

Prove that there are infinitely many primes of the form 6x-1.

I have been fighting this proof for an hour. I have no idea how to get started or on how to finish. Any help would be greatly appreciated.

2. All integers can be represented as:

$n = 6k + m$

Where:

$m \in \{0,1,2,3,4,5\}$ and

$k \in \mathbb{Z}$

Now, first we try to find the statements for which this is seemingly prime:

$\text{For } m = 0$

$n = 6k$

It's immediately clear that this is divisible by 6.

$\text{For } m = 1$

$n = 6k + 1$

This has no immediate factors, MAY be prime.

$\text{For } m = 2$

$n = 6k + 2 = 2(3k + 1)$

It is immediately clear that it is divisible by two.

$\text{For } m = 3$

$n = 6k + 3 = 3(2k + 1)$

It is immediately clear that it is divisible by three.

$\text{For } m = 4$

$n = 6k + 4 = 2(3k + 2)$

Immediately clear that it is divisible by two.

$\text{For } m = 5$

$n = 6k + 5$

It has no immediate factors. MAY be prime.

The only candidates for primacy are:

$q = 6k + 1$

Or

$p = 6k + 5$

But, $6k + 5 = 6m - 1$ for $m = k + 1$

Therefore, all integers that are candidates for primacy are:

$p = 6n \pm 1$

Since it has already been proven that there are infinitely many primes, then there are also infinitely many primes represented by each:

$q = 6n + 1$

and

$p = 6n - 1$

Thus, there are infinitely many primes represented by $p = 6x - 1$

$Q.E.D.$

I know it may not be as good as you need. But you can use it to build your own proof if you would like.

3. Originally Posted by Aryth
Therefore, all integers that are candidates for primacy are:

$p = 6n \pm 1$

Since it has already been proven that there are infinitely many primes, then there are also infinitely many primes represented by each:

$q = 6n + 1$

and

$p = 6n - 1$

Thus, there are infinitely many primes represented by $p = 6x - 1$

$Q.E.D.$
Excuse me, but this part is wrong, you have not shown that there are infinitely many primes of the form $p=6k-1$. Maybe there are infinetely many prime numbers of the form $p=6k+1$ and a finite number of primes of the form $p=6k-1$

Indeed, suppose there's a finite number of primes of the form $p=6l-1$, let $a_1,a_2,...,a_m$ be all the primes of that form

Let $x=6\cdot{a_1\cdot{a_2\cdot{...\cdot{a_m}}}}-1$

This number must have a prime factor of the form $p\equiv{-1}(\bmod.6)$, but it is not divisible by any prime of the form $p=6l-1$ (by our assumption). This is absurd, therefore there have to be infnitely prime numbers of the form $p=6k-1$

4. We can generalize this result. Let $p \equiv - 1(\bmod n)$. Suppose that all the (odd) primes are either $p\equiv \pm 1(\bmod n)$. Then there are infinitely many primes $p\equiv -1(\bmod n)$. And the proof is similar. Suppose there are finitely many and define $m = n (p_1\cdot ...\cdot p_k) - 1$. Now any prime divisior of $m$ has form $p\equiv \pm 1(\bmod n)$. It cannot be that all have form $p\equiv 1(\bmod n)$ because then $m$ would have that form too. So it must mean that one of the prime factors of $m$ satisfies $p\equiv -1(\bmod n)$ but then the LHS is divisible by $p$ but not the RHS.

5. Originally Posted by PaulRS
This number must have a prime factor of the form $p\equiv{-1}(\bmod.6)$...
How come?

6. ## Question

Originally Posted by PaulRS
This number must have a prime factor of the form $p\equiv{-1}(\bmod.6)$, but it is not divisible by any prime of the form $p=6l-1$ (by our assumption). This is absurd, therefore there have to be infnitely prime numbers of the form $p=6k-1$
I have a similar type of problem on an assignment, but with $4n+3$ instead. However, I'm not allowed to use modular arithmetic. Using the $6k-1$ example, I was just wondering if I could restate this last part as:

By the Fundamental Theorem of Arithmetic, there must be a prime of form $p=6k-1$ such that $p|x$. But $x$ is not divisible by any prime of form $6l-1$ by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form $6k-1$.

Such a proof should also hold for the case of primes in the form of $4n+3$ too right?

7. Originally Posted by star_tenshi
I have a similar type of problem on an assignment, but with $4n+3$ instead. However, I'm not allowed to use modular arithmetic. Using the $6k-1$ example, I was just wondering if I could restate this last part as:

By the Fundamental Theorem of Arithmetic, there must be a prime of form $p=6k-1$ such that $p|x$. But $x$ is not divisible by any prime of form $6l-1$ by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form $6k-1$.

Such a proof should also hold for the case of primes in the form of $4n+3$ too right?
That is what post #4 says.

All odd primes are either: $4k+1,4k+3$.
If there are finitely many such primes of form $4k+3$ it means we can form $N = 4p_1...p_n - 1$.

This number $N$ factors into odd primes. Say all these primes where of form $4k+1$. Then $N$ would be of form $4k+1$ which is a contradiction. Thus, there exists $q$, and odd prime divisor of form $4k+3$. But that forces $q|1$ which is a contradiction. Thus, there are infinitely many such primes.

And the same argument works for primes of form $3k+2$ also.

Note: In case you are wondering proving that there are infinitely many primes of forms $4k+1$ is more difficult.

8. Awesome, thanks!

9. Would this work?

Numbers at 6n-1 are prime unless one of their factors is at 6n-1. If x is the highest prime at 6n-1 then every number > x at 6n-1 has a product at 6n-1 < x. It must be easy to show that this is impossible.