# infinite primes

• Apr 10th 2008, 12:32 PM
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.
• Apr 10th 2008, 01:19 PM
Aryth
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.
• Apr 16th 2008, 12:18 PM
PaulRS
Quote:

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$ (Evilgrin)

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$
• Apr 16th 2008, 03:48 PM
ThePerfectHacker
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.
• Nov 3rd 2008, 08:18 PM
r0r0trog
Quote:

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

How come?
• Jan 22nd 2009, 08:39 AM
star_tenshi
Question
Quote:

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?
• Jan 22nd 2009, 09:03 AM
ThePerfectHacker
Quote:

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.
• Jan 22nd 2009, 09:29 AM
star_tenshi
Awesome, thanks!
• Jan 30th 2009, 09:42 AM
Whoever
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.