Prime numbers

[Illiad]

Theory:All primes except for 1,2,3 can be described as 6n+5 or if not, 6n+7.

can some one help me check please? I'm really bad at programming

Edited August 10, 2010 by Illiad
sorry

[Donk]

Let's look at numbers of the form 6n+x:

 

If x is even (0,2,4) then the result is even, so not a prime.

If x is odd, it has to be 1,3,5 (your value of 7 is equivalent to a 1).

6n+3 divides by 3, so is not a prime.

 

Therefore, all primes must be of the form 6n+1 (=6n+7) or 6n+5.

 

So you're right ;)

[Tormod]

Here is some more background about this:

 

Euler's 6n+1 Theorem -- from Wolfram MathWorld

[Qfwfq]

I'm really bad at programming

I have earned yeas of salary by programming, but if it weren't for Donk's argument you couldn't really expect a program to be a conclusive proof. You could run it for all numbers up to whatever size, without finding counterexamples but that doesn't really prove the case with certainty.

[CraigD]

Illiad’s original assertion, [math]p = 6n \pm 1[/math], is a special case of the general

[math]p = an \pm b[/math], where a and b are relatively prime positive integers, and [math]b \le \frac{a}2[/math].

 

From this, we can get the trivial [math]p = n[/math],

the only slightly less trivial (slightly fudged) [math]p = 2n +1[/math],

and the follows-the-OP’s case [math]p = 10n \pm 1[/math] or [math]10n \pm 3[/math].

Using the notation 5n+-1,2 to mean [math]p = 10n \pm 1[/math] or [math]10n \pm 3[/math], here’re some small-numbered examples:

n
2n+-1
3n+-1
6n+-1
5n+-1,2
10n+-1,3
15n+-1,2,4,7
30n+-1,7,11,13
7n+-1,2,3
14n+-1,3,5
21n+-1,2,4,5,8,10
42n+-1,5,11,13,17,19
35n+-1,2,3,4,6,8,9,11,12,13,16,17
70n+-1,3,9,11,13,17,19,23,27,29,31,33
105n+-1,2,4,8,11,13,16,17,19,22,23,26,29,31,32,34,37,38,41,43,44,46,47,52
210n+-1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103
11n+-1,2,3,4,5
22n+-1,3,5,7,9
33n+-1,2,4,5,7,8,10,13,14,16
66n+-1,5,7,13,17,19,23,25,29,31
55n+-1,2,3,4,6,7,8,9,12,13,14,16,17,18,19,21,23,24,26,27
110n+-1,3,7,9,13,17,19,21,23,27,29,31,37,39,41,43,47,49,51,53
13n+-1,2,3,4,5,6
26n+-1,3,5,7,9,11
39n+-1,2,4,5,7,8,10,11,14,16,17,19
78n+-1,5,7,11,17,19,23,25,29,31,35,37
65n+-1,2,3,4,6,7,8,9,11,12,14,16,17,18,19,21,22,23,24,27,28,29,31,32
130n+-1,3,7,9,11,17,19,21,23,27,29,31,33,37,41,43,47,49,51,53,57,59,61,63
17n+-1,2,3,4,5,6,7,8
34n+-1,3,5,7,9,11,13,15
51n+-1,2,4,5,7,8,10,11,13,14,16,19,20,22,23,25
102n+-1,5,7,11,13,19,23,25,29,31,35,37,41,43,47,49
19n+-1,2,3,4,5,6,7,8,9
38n+-1,3,5,7,9,11,13,15,17
57n+-1,2,4,5,7,8,10,11,13,14,16,17,20,22,23,25,26,28
114n+-1,5,7,11,13,17,23,25,29,31,35,37,41,43,47,49,53,55

 

A general form of Donk’s proof applies to all.

[Illiad]

, where a and b are relatively prime positive integers, and .

did you mean to say b is a positve prime number less than half of a (and cannot have any common factor with a)?

if so, a can be any positive number then? or how is it decided?

From this, we can get the trivial ,

the only slightly less trivial (slightly fudged) ,

and the follows-the-OP’s case or .

Using the notation 5n+-1,2 to mean or , here’re some small-numbered examples:

I'm lost here~ I never really studied prime numbers in detail and are theyjust more of a curiosity to me.

it would help if you can go step by step or provide links to where i can find it. Really appreciate the replies you all have given, thanks alot

Edited August 12, 2010 by Illiad

[Qfwfq]

did you mean to say b is a positve prime number less than half of a (and cannot have any common factor with a)?

Yes, but the essential thing is the second: no common factor. For any such pair of a and b, changing b by any multiple of a gives an equivalent pair. If b > a it is always possible to subtract a from b until b < a and, if it is more than half, one further subtraction makes it negative. That's why Craig put the [imath]\pm[/imath] sign in.

 

if so, a can be any positive number then? or how is it decided?

Yes, any number in principle, but some will be more useful and others less, as a heuristic:

I'm lost here

The first is with a = 1 and is obviously no utter use as a heuristic, it just means p is a number, like n. The second is for n = 2 and just says all primes except 2 are odd. This is the most immediate heuristic that isn't totally trivial. If a is itself prime, only its multiples are discarded and b can be any number except 0 (and apart from reducing it by subtraction).

 

The general argument is not all that difficult. If a and b have any common factors, it is obvious that an + b is a multiple of these and so it can't be prime, so that's why a and b must be co-prime. Considering any given a, we can write any prime number as p = an + b where, if b is "reduced" by subtraction with corresponding increments of n, it is just the remainder from the integral division operation.

[Illiad]

ah..its more clearer now~ thanks again