Waar vind ik het bewijs dat Priems = 6n-1 of 6n+1 maar niet omgekeerd ?

[RedCat]

Klopt: "alle priemgetallen zijn van de vorm 6k±1 (op 2 en 3 na) zijn, maar niet omgekeerd"

Onderliggend principe:

(1) n = 6*k + r

Alle getallen n zijn te schrijven in de vorm n=6k+r, met 0 ≤ r ≤ 5.
Dat wil zeggen: 6k+0, 6k+1, 6k+2, 6k+3, 6k+4 of 6k+5
Merk op: de getallen n die te schrijven zijn als 6k-1 = de getallen n die te schrijven zijn als 6k+5

Alleen de getallen waarvan ggd(r, 6) = 1 kunnen andere priemgetallen dan 2 of 3 bevatten:
n = 6k+0 is altijd deelbaar door 2 en 3: n is dus nooit priem
n = 6k+1: gcd(1, 6) = 1: n is niet deelbaar door 2 noch door 3
n = 6k+2: is altijd deelbaar door 2: n is dus nooit priem
n = 6k+3: is altijd deelbaar door 3: n is dus nooit priem
n = 6k+4: is altijd deelbaar door 2: n is dus nooit priem
n = 6k+5: gcd(5, 6) = 1: n is niet deelbaar door 2 noch door 3

n=6k+1 en n=6k+5(≡6k-1) zijn dus de enige 2 vormen waarvoor n priem kan zijn (uitgezonderd priemgetallen 2 en 3).

Deze 2 vormen bevatten voor getallen 1 t/m 1000:
X=166 (alle priemgetallen behalve 2 en 3)
Y=333 (=het totale aantal getallen in deze 2 groepen)
waardoor X/Y = 166/333 = 49.85% (dit hadden we eerder ook al gevonden).


(2) n = 30*k + r

Voor n=30k+r (0 ≤ r ≤ 29) correspondeert dit met:

"alle priemgetallen zijn van de vorm 30k±1 of 30k±7 of 30k±11 of 30k±13 (op 2, 3 en 5 na) zijn, maar niet omgekeerd"

Als n=30k+r en d=ggd(r, 30)>1, dan zijn zowel 30 als r te delen door d, en is n dus ook te delen door d en daardoor nooit priem (uitgezonderd n = 2, 3 of 5).
Nu is ggd(r, 30)=1 alleen voor r = 1, 7, 11, 13, 17(≡-13), 19(≡-11), 23(≡-7) en 29(≡-1), en geldt:
n=30k+1, n=30k+7, n=30k+11, n=30k+13, n=30k+17, n=30k+19, n=30k+23, n=30k+29 zijn dus de enige 8 vormen waarvoor n priem kan zijn (uitgezonderd priemgetallen 2, 3 en 5).

Deze 8 vormen bevatten voor getallen 1 t/m 1000:
X=165 (alle priemgetallen behalve 2, 3 en 5)
Y=266 (=het totale aantal getallen in deze 8 groepen)
waardoor X/Y = 165/266 = 62.03%

[Regor]

@RedCat,

Weeral bedankt hoor,

Is er dan nog een andere maar gelijkaardige formule (niet op basis van 6 of 30 ) die een grotere X/Y oplevert ?

[RedCat]

De exacte priemdichtheid X/Y voor getallen n = m*k + r (bij gegeven m; en daardoor bepaalbare k en r met 0 ≤ r ≤ m-1) kunnen we laten berekenen door de computer: net als eerder tellen de getallen n mee als d = ggd(m, r) = 1 (immers: als d > 1 zijn r en m (en dus ook n) deelbaar door d, en is n zeker niet priem), dit levert Y, en tellen we hoeveel van die getallen priem zijn, dit levert X.

Het aantal getallen n (≤ N) waarvoor r een gegeven vaste waarde heeft is ongeveer N/m
(hooguit een verschil van 1 getal: N/m = 1000/6 = 166.66..., er zijn 167 getallen voor r = 1 t/m 4 (r=4 voor n= 4, 10, 16, ... 994, 1000 = 167 getallen, en 166 getallen voor r=5 of 6)

Als m het product is van de eerste q priemgetallen:
\(\displaystyle m = \prod_{i=1}^q p_i = p_1 \cdot p_2 \cdot p_3 \cdot ... \cdot p_q = 2\cdot 3\cdot 5 \cdot ... \cdot p_q\)
dan is de Euler phi van m:
\(\displaystyle \varphi(m) = \prod_{i=1}^q (p_i-1) = (p_1-1) \cdot (p_2-1) \cdot (p_3-1) \cdot ... \cdot (p_q-1) = 1\cdot 2\cdot 4 \cdot ... \cdot (p_q-1)\)
en dit is het aantal getallen r dat copriem is met m (ofwel: waarvoor ggd(m, r) = 1)

Noem verder \(\pi(N)\) het aantal priemgetallen kleiner of gelijk aan N
(een aantal goed bruikbare waarden van \(\pi(N)\) vindt u hier: https://en.wikipedia.org/wiki/Prime-cou ... _and_li(x))

De benaderde priemdichtheid X/Y voor getallen n = m*k + r wordt daardoor:

\(\frac{X}{Y} = \frac{\pi(N)-q}{\varphi(m)\cdot (N/m)}\)

In de teller het aantal priemgetallen kleiner dan N, verminderd met de q eerste priemgetallen die we er al uit gefilterd hebben.
In de noemer het aantal waarden van r waarvoor ggd(m, r)=1, vermenigvuldigd met het aantal getallen 1 ≤ n ≤ N waarvoor
n = m*k + de betreffende waarde van r.

Resultaten:

---- m = 6, N = 1000: ----
X/Y exact: 166 / 333 = 49.85%
X/Y benaderd: (168-2)/(2*1000/6) = 166/333.33 = 49.80%

---- m = 30, N = 1000: ----
X/Y exact: 165 / 266 = 62.03%
X/Y benaderd: (168-3)/(8*1000/30) = 165/266.67 = 61.88%

---- m = 210, N = 1000: ----
X/Y exact: 164 / 228 = 71.93%
X/Y benaderd: (168-4)/(48*1000/210) = 164/228.57 = 71.75%

---- m = 2310, N = 1000: ----
X/Y exact: 163 / 207 = 78.74%
X/Y benaderd: (168-5)/(480*1000/2310) = 163/207.79 = 78.44%

---- m = 30030, N = 1000: ----
X/Y exact: 162 / 190 = 85.26%
X/Y benaderd: (168-6)/(5760*1000/30030) = 162/191.81 = 84.46%

---- m = 510510, N = 1000: ----
X/Y exact: 161 / 179 = 89.94%
X/Y benaderd: (168-7)/(92160*1000/510510) = 161/180.53 = 89.18%

---- m = 9699690, N = 1000: ----
X/Y exact: 160 / 170 = 94.12%
X/Y benaderd: (168-8)/(1658880*1000/9699690) = 160/171.02 = 93.55%

[Regor]

@RedCat,

Boeiend !
Mag ik tussendoor besluiten dat alle priems van de vorm 2n+1 en van de vorm
6n +-1 zijn ...... op 2 en 3 na in sommige gevallen. ? ........... maar (uiteraard) niet omgekeerd.?

[RedCat]

Klopt, hier wat er gebeurt in de zeef van Eratosthenes (https://nl.wikipedia.org/wiki/Zeef_van_Eratosthenes):

Het eerste priemgetal is 2, eerst worden alle tweevouden (geel) weggezeefd.
De overige priemgetallen (rood) zijn allemaal in de vorm 2k+1 = oneven:

Vervolgens worden alle overgebleven drievouden (groen) weggezeefd.
2*3=6, als we kijken naar de zesvouden zijn daarvan dus weggezeefd:
eerst de getallen 6k+0, 6k+2, 6k+4 (= deelbaar door 2),
en daarna ook de getallen 6k+3 (= deelbaar door 3).
Blijven over: getallen in de vorm 6k+1 en 6k+5, waar alle resterende priemgetallen (buiten 2 en 3) deel van uitmaken.

Daarna worden alle overgebleven vijfvouden (blauw) weggezeefd.
2*3*5=30, als we kijken naar de dertigvouden zijn daarvan dus weggezeefd:
eerst de getallen 30k+0, 30k+2, 30k+4, .... , 30k+28 (= getallen deelbaar door 2),
daarna ook de getallen 30k+3, 30k+9, 30k+15, 30k+21, 30k+27 (= deelbaar door 3),
en tenslotte ook de getallen 30k+5 en 30k+25 (= deelbaar door 5),
Blijven over: getallen 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 en 30k+29, waar alle overige priemgetallen (buiten 2, 3 en 5) deel van uitmaken.

Op deze manier vangen we steeds ten koste van 1 priemgetal alle (resterende) veelvouden daarvan weg, waardoor de relatieve dichtheid van de overgebleven priemgetallen (hier rood gekleurd) toeneemt.

[Regor]

@RedCQat,

Bedankt,
Stop aub om er nog energie en tijd in te steken ... ik krijg schuldgevoel.
En toch nog eens de vraag, graag heel kort, klopt of klopt niet aub ?

Mag ik dus besluiten dat ALLE priems ENKEL van de vorm 2n+1 en van de vorm
6n +-1 zijn ...... op 2 en 3 na in sommige gevallen. ?

[RedCat]

Stop aub om er nog energie en tijd in te steken ... ik krijg schuldgevoel.

Voor getaltheorie mag u mij altijd wakker maken.

Mag ik dus besluiten dat ALLE priems ENKEL van de vorm 2n+1 en van de vorm
6n +-1 zijn ...... op 2 en 3 na in sommige gevallen. ?

U kijkt nu voor een gegeven waarde m naar een verzameling natuurlijke getallen n = m*k±1 (met k een vrij te kiezen geheel getal), en wilt weten of daarin alle priemgetallen aanwezig zijn (behalve een eindig ('klein') aantal).
Dit is zo voor:
m=1: elk natuurlijk getal n is te schrijven in de vorm n=1*k±1, dus ook alle priemgetallen zijn in deze vorm te schrijven (= triviaal).
m=2: elk natuurlijk oneven getal n is te schrijven in de vorm n=2k±1, dus ook alle oneven priemgetallen. We missen zo alleen p=2, het enige even priemgetal.
m=3: als n=3k±1, dan missen we alleen de drievouden 3k en dus ook 3 zelf. Alle andere priemgetallen behalve p=3 zijn dus in deze vorm te schrijven.
m=4: elk natuurlijk oneven getal n is te schrijven in de vorm n=4k±1, dus ook elk oneven priemgetal. We missen hierbij alleen p=2.
m=6: hiermee missen we alleen 2 en 3, zoals al eerder beschreven.

Dit zijn alle mogelijke waarden van m waarvoor dit geldt: voor alle andere getallen is de Euler phi functie φ(m) groter dan 2,
en worden de resterende priemgetallen over φ(m) > 2 restklassen verdeeld.

Ter illustratie: m=5 heeft φ(5)=4 restklassen (de witte kolommen) waarover de priemgetallen (behalve 5) verdeeld worden:
(want ggd(5, 1) = ggd(5, 2) = ggd(5, 3) = ggd(5, 4) = 1)

meq5 69 keer bekeken

evenzo: m=12 heeft φ(12)=4 restklassen (de witte kolommen) waarover de priemgetallen (behalve 2 en 3) verdeeld worden:
(want ggd(12, 1) = ggd(12, 5) = ggd(12, 7) = ggd(12, 11) = 1)

meq12 70 keer bekeken

[Regor]

@RedCat,

Dank U,
Vollediger kan niet.
Mijn inzichten zijn aangepast ......... forever !