Gelul waar Thabit zich maar bezig mee moet houden.

Definieer de functie mu op de positieve gehele getallen als:
neem een getal n en ontbind het in priemfactoren. Als er een priemfactor is die minstens in het kwadraat voorkomt dan definieren we
mu(n)=0.
In alle andere gevallen laten we k het aantal priemfactoren zijn en definieren we
mu(n)=(-1)^k

Voorbeeld: mu(1)=1, mu(2)=-1, mu(3)=-1, mu(4)=0, mu(5)=-1, mu(6)=1, ...

Nu definieren we ook nog voor een gegeven positief geheel getal n de functie Phi_n(x) als het produkt van de factoren (x^n/d-1)^mu(d), waarbij we d laten lopen over alle delers van n. Dat lijkt een uitvoerige berekening maar valt wel mee: de delers d die een priemfactor in het kwadraat meenemen mogen we negeren, mu(d) is dan namelijk 0.

Voorbeelden wederom:
Phi₁(x)=x-1,
Phi₂(x)=(x²-1)/(x-1)=x+1,
Phi₃(x)=(x³-1)/(x-1)=x²+x+1,
Phi₄(x)=(x⁴-1)/(x²-1)=x²+1, (hoe de berekening gaat is nu hopelijk duidelijk),
Phi₅(x)=x⁴+x³+x²+x+1,
Phi₆(x)=x²-x+1,
...

Wat heb je nu aan die Phi-dingen zul je wel denken. Wel, stel dat we willen weten voor een gegeven waarde van n welke priemgetallen p er aan L=n voldoen. Dat zijn precies de priemgetallen p die een deler zijn van Phi_n(10) en geen deler van n, niet meer en niet minder. Dus bijvoorbeeld voor n=6 berekenen we dat Phi₆(10)=91=7*13, waaruit volgt dat 7 en 13 de enige priemgetallen zijn met L=6.

Ik kan het *bijna* volgen. Snappen is nog een ander verhaal, maar ik denk dat ik het tenminste kan VOLGEN als ik weet wat je met " waarbij we d laten lopen over alle delers van n" bedoelt. Neem je dan voor iedere deler d van n een aparte term op in je berekening? Of sommeer je alle d's of zo?

_{Zoals ik al zei, ik ben geen wiskundige Ik heb alleen maar wat aan priemgetallen lopen rekenen, zonder stellingen en bewijzen en zo... Trouwens ik weet niet of de topictitel wel zo op z'n plaats is....}

[ Bericht 6% gewijzigd door Dr_Flash op 10-03-2004 09:48:36 ]

quote:

Op woensdag 10 maart 2004 09:42 schreef Dr_Flash het volgende:
Ik kan het *bijna* volgen. Snappen is nog een ander verhaal, maar ik denk dat ik het tenminste kan VOLGEN als ik weet wat je met " waarbij we d laten lopen over alle delers van n" bedoelt. Neem je dan voor iedere deler d van n een aparte term op in je berekening? Of sommeer je alle d's of zo?

Bijna, je vermenigvuldigt een aantal termen (inderdaad een aparte term voor iedere deler van d) met elkaar. Bijvoorbeeld n=4, de verzameling delers van n is dan {1,2,4}. Phi[sub]4[sub](x) is dus het volgende product van 3 termen:
(x^4/1-1)^mu(1) * (x^4/2-1)^mu(1) * (x^4/4-1)^mu(4)
Zoals thabit al opmerkte kun je de termen waarbij d een priemfactor in het kwadraat heeft (in dit geval de derde term, van d=4) negeren, want mu(d) is dan 0, en iets⁰=1. Je houdt dus over:
(x⁴-1)¹ * (x²-1)^-1 = x²-1.

quote:

Op dinsdag 9 maart 2004 21:16 schreef thabit het volgende:
Het volgende geldt in elk geval:

de kleine stelling van Fermat zegt dat als a een geheel getal is en p geen deler van a, dan is
a^p-1=1 mod p.
Een hele handige stelling! De stelling zegt echter niet dat p-1 ook de kleinste positieve waarde van k is waarvoor
a^k=1 mod p.
Deze kleinste waarde van a noemen we de multiplicatieve orde van a modulo p en kunnen we noteren met
k=ord_pa.
Er zal altijd gelden dat ord_pa een deler is van p-1.

de kleine stelling van fermat geld volgens mij alleen maar voor a en p waarbij a > p
(tenminste, dat concludeer ik als ik ga uitproberen)

daarnaast schrijf je: "Deze kleinste waarde van a noemen we de multiplicatieve orde van a modulo p"
bedoel je niet: "de kleinste waarde van k" ?? (ipv a)

quote:

Op woensdag 10 maart 2004 12:47 schreef Simple_Mind het volgende:
[..]
de kleine stelling van fermat geld volgens mij alleen maar voor a en p waarbij a > p
(tenminste, dat concludeer ik als ik ga uitproberen)

Nee, het geldt voor alle a die niet deelbaar zijn door p.

quote:

daarnaast schrijf je: "Deze kleinste waarde van a noemen we de multiplicatieve orde van a modulo p"
bedoel je niet: "de kleinste waarde van k" ?? (ipv a)

Ja, dat moet k zijn, stond erboven ook al.

maar als je a = 5 kiest, en p = 6, dan komt het volgens mij niet uit hoor..

5^6-1 = 5⁵ = 5 mod 6 (en dus NIET 1 mod 6)

of doe ik weer iets fout?

quote:

Op woensdag 10 maart 2004 16:48 schreef Simple_Mind het volgende:
maar als je a = 5 kiest, en p = 6, dan komt het volgens mij niet uit hoor..

5^6-1 = 5⁵ = 5 mod 6 (en dus NIET 1 mod 6)

of doe ik weer iets fout?

6 is geen priemgetal.

quote:

Op woensdag 10 maart 2004 17:02 schreef thabit het volgende:

[..]

6 is geen priemgetal.

oja.. DOH ik was vergeten dat p voor "priem" stond..
bedankt... snap ik het ook weer

quote:

Op woensdag 10 maart 2004 16:48 schreef Simple_Mind het volgende:
maar als je a = 5 kiest, en p = 6, dan komt het volgens mij niet uit hoor..

5^6-1 = 5⁵ = 5 mod 6 (en dus NIET 1 mod 6)

of doe ik weer iets fout?

Ik snap niet eens wat er met de term mod bedoeld wordt

_{Jaaaa laat maar komen die woordspelingen}

quote:

Op woensdag 10 maart 2004 19:08 schreef Dr_Flash het volgende:

[..]

Ik snap niet eens wat er met de term mod bedoeld wordt

_{Jaaaa laat maar komen die woordspelingen}

dat betekent dus modder, andere term voor bagger.. dat moet jou toch wel wat zeggen - baggeren??

(ga hier maar eens kijken)

quote:

Op woensdag 10 maart 2004 21:40 schreef Simple_Mind het volgende:

[..]



dat betekent dus modder, andere term voor bagger.. dat moet jou toch wel wat zeggen - baggeren??

(ga hier maar eens kijken)

Ik hoor het al, je hebt al mijn posts gelezen
Maar toch bedankt voor die link

He Flash
... je liep hier niet al 3 jaar mee, maar (in rudimentaire vorm) al wel minstens zo'n 9 jaar (9 = 3x3 = eerste oneven priemgetal). Op z'n minst sinds 1995 , waarschijnlijk wel 1994 .

Wat ik me afvroeg en wat ik de heren experts bij deze wil voorleggen,
is of dit soort eigenschappen van priemgetallen wordt gebruikt in de programmatjes
die computers op hun rekencappaciteit testen... (eens in de zoveel tijd verschijnt er een berichtje dat een nieuw priemgetal orde grootte 10E999 is gevonden, door de zoveelste generatie supercomputer...)

Met andere woorden:
Is een enorme staartdeling maken, om die decimalen-reeksen te voorschijn te toveren, en tegelijkertijd een zoekertje laten lopen die kijkt of de reeks repterend wordt...
reken/programmeer technisch sneller dan progressief 'ontbinden in factoren' ?

EDIT: heren (m/v) natuurlijk.

Hmm, ligt allemaal aan de algoritmes die ervoor ontworpen worden/zijn. Je kunt wel een hele snelle computer hebben, als de algoritme brak is, kun net zo goed een 8086 met een goed algoritme laten draaien, want dat gaat sneller.

GIMPS, the Great Internet Mersenne Prime Search (www.mersenne.org) voert wel eerst een processortest bij je uit voordat-ie gaat zoeken naar priemgetallen. Het is wel een van de beste tests voor je processor, Intel gebruikt het zelfs. Dit soort specifieke berekeningen zullen daar wel niet bij horen.