General form of a prime greater than 3.

Question

Is the general form of a prime number $> 3$, $6a \pm 1$, or $3a \pm 1$. I've seen both used here.

I'll try to find a few examples...but I've definitely seen $6a \pm 1$ and $3a \pm 1$. Perhaps I'm not reading them in the correct context though. — Math1, Nov 18 '16 at 20:52
If $\mathbb{P}$ denotes the set of prime numbers, then $(\mathbb{P}\setminus {2,3}) \subsetneq { 6a \pm 1 : a \in \mathbb{N}\setminus {0}} \subsetneq { 3a\pm 1 : a \in \mathbb{N}\setminus {0}}$. So both are correct, but one is more specific than the other. — Daniel Fischer, Nov 18 '16 at 20:54
Okay - I don't think I'm getting the idea with linking properly. I'll work on that. But, what I'm understanding though is that ALL primes are of the form $3a \pm 1$, but only primes $\ge 5$ are of the form $6a \pm 1$? — Math1, Nov 18 '16 at 20:58

score 1 · Accepted Answer · answered Nov 18 '16 at 20:56

1

You can solve this by process of elimination for primes greater than 3:

In terms of modular arithmetic, all numbers are of the form $6a+k$ for $k \in [0,5]$.

Let's eliminate which forms a prime can't be in:

Can't be $6a+2$ or $6a+4$ because these are even.

Can't be $6a+3$ because this is divisible by 3.

This leaves $6a+1$ or $6a+5$, the latter of which is equivalent to $6a'-1$. Thus all primes greater than 3 are of the form $6a \pm 1$.

The $3a \pm 1$ case is kind of obvious. All numbers that aren't divisible by 3 are of this form.

answered Nov 18 '16 at 20:56

gowrath

3,573
13
31

Okay - so both are correct, but $3a \pm 1$ is all encompassing (minus p =2) – Math1 Nov 18 '16 at 21:00
1

I mean yes. But you could also say all primes (excluding 2) are of the form $2n+1$ right? I don't really see this being a useful notion. You're essentially working mod a base and elimination all residue classes that can't be prime. – gowrath Nov 18 '16 at 21:02

Simply Beautiful Art · Answer 2 · 2016-11-18T21:10:09.590

0

No, since $6a+1=49$ and $3a+1=24$ when $a=8$, and we know $49$ and $25$ are not prime.

If you meant that all primes take that form, even though some numbers of this form are not prime, then this is true, though trivially true. It is as trivial as saying all prime numbers not including $2$ are odd. Simply see that prime numbers cannot be in the following forms:

$$\begin{array}{c|c}6a+0&\text{divisible by }6\\6a+1&\color{#034da3}{\text{possibly prime}}\\6a+2&\text{divisible by }2\\6a+3&\text{divisible by }3\\6a+4&\text{divisible by }2\\6a+5&\color{#034da3}{\text{possibly prime}}\end{array}$$

Notice $6a+5$ is the same as $6a-1$. Same argument for $3a\pm1$.

You may want to take a look at the prime counting function. A famous bound for prime numbers: (assuming the Riemann hypothesis)

$$|k-\operatorname{li}(x)|<\frac1{8\pi}\sqrt x\log(x)\ \forall\ x>2657$$

where $x$ is the $k$th prime number. Pretty good for finding prime numbers that are very large.

edited Nov 18 '16 at 21:10

answered Nov 18 '16 at 21:04

Simply Beautiful Art

74,685

1

I don't think op's claim was all numbers of that form are prime, even though that's what I initially thought too. – gowrath Nov 18 '16 at 21:08
@gowrath Well, just in case, there is the entire answer with the exception of the first line. – Simply Beautiful Art Nov 18 '16 at 21:09
Right, more that all primes $\ge 5$ are of that form. In a case like Proof that if pp and p2+2p2+2 are prime then p3+2p3+2 is prime too it seems like 3 is the only prime that works because of the fact that they can be written as $6a \pm 1$ – Math1 Nov 18 '16 at 21:09
@Math1 Well, of course. There are only two cases, so they must fall into one or the other. $2,3$ are different in that they fall under the cases "divisible by $2$ or $3$" *and* they have no other factors. – Simply Beautiful Art Nov 18 '16 at 21:11
1

@Math1 :D you got that link working! good job – Simply Beautiful Art Nov 18 '16 at 21:17

General form of a prime greater than 3.

2 Answers2