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:

$\displaystyle n = 6k + m$

Where:

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

$\displaystyle k \in \mathbb{Z}$

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

$\displaystyle \text{For } m = 0$

$\displaystyle n = 6k$

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

$\displaystyle \text{For } m = 1$

$\displaystyle n = 6k + 1$

This has no immediate factors, MAY be prime.

$\displaystyle \text{For } m = 2$

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

It is immediately clear that it is divisible by two.

$\displaystyle \text{For } m = 3$

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

It is immediately clear that it is divisible by three.

$\displaystyle \text{For } m = 4$

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

Immediately clear that it is divisible by two.

$\displaystyle \text{For } m = 5$

$\displaystyle n = 6k + 5$

It has no immediate factors. MAY be prime.

The only candidates for primacy are:

$\displaystyle q = 6k + 1$

Or

$\displaystyle p = 6k + 5$

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

Therefore, all integers that are candidates for primacy are:

$\displaystyle 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:

$\displaystyle q = 6n + 1$

and

$\displaystyle p = 6n - 1$

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

$\displaystyle 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:

$\displaystyle 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:

$\displaystyle q = 6n + 1$

and

$\displaystyle p = 6n - 1$

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

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

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

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

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

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

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

6. ## Question

Originally Posted by PaulRS
This number must have a prime factor of the form $\displaystyle p\equiv{-1}(\bmod.6)$, but it is not divisible by any prime of the form $\displaystyle p=6l-1$ (by our assumption). This is absurd, therefore there have to be infnitely prime numbers of the form$\displaystyle p=6k-1$
I have a similar type of problem on an assignment, but with $\displaystyle 4n+3$ instead. However, I'm not allowed to use modular arithmetic. Using the $\displaystyle 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 $\displaystyle p=6k-1$ such that $\displaystyle p|x$. But $\displaystyle x$ is not divisible by any prime of form $\displaystyle 6l-1$ by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form $\displaystyle 6k-1$.

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

7. Originally Posted by star_tenshi
I have a similar type of problem on an assignment, but with $\displaystyle 4n+3$ instead. However, I'm not allowed to use modular arithmetic. Using the $\displaystyle 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 $\displaystyle p=6k-1$ such that $\displaystyle p|x$. But $\displaystyle x$ is not divisible by any prime of form $\displaystyle 6l-1$ by our assumption. This is a contradiction, thus, there must exist infinitely many primes of the form $\displaystyle 6k-1$.

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

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

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

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

Note: In case you are wondering proving that there are infinitely many primes of forms $\displaystyle 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.