Waarom is (2^p-2)/p geheel voor p is priem?

[Lord Daemon]

Ik zat tijdens een som over chaostheorie een beetje te spelen met de 'zaagtand-afbeelding', en toen vond ik het volgende resultaat (hoe ik dat vond staat onderaan de post):

(2^p - 2)/p is een geheel getal, voor elke p is priem.

Nu vraag ik me af of iemand enig idee heeft hoe je dit getaltheoretisch zou kunnen bewijzen?

(Het is overigens, helaas, geen voldoende criterium voor een priemgetal. Ergens in de 300 vindt je al het eerste niet-priemgetal dat eraan voldoet.)

------------------

Hoe ik aan het resultaat kwam. Stel je hebt de afbeelding x_n+1 = 2 x_n modulo 1, die het interval [0,1> op zichzelf afbeeldt. (1 valt er dus net buiten.)

Deze grafiek heeft 1 vast punt: 0. Dit kan je vinden door de afbeelding te combineren met de voorwaarde x_n+1 = x_n, wat de definitie van een vast punt is.

Als je nu de q-maal ge-itereerde afbeelding neemt, heeft deze 2^q - 1 snijpunten met x_n+1 = x_n. Stel dat q een priemgetal is, dan liggen al deze punten of op banen die, in de oorspronkelijke afbeelding, na q maal weer in het oorspronkelijke punt terug keren, of op banen die na 1 keer al in het oorspronkelijke punt terug keren. Maar van deze laatste soort is er maar 1: 0. Dus zijn er voor iedere q is priem q^2 - 2 punten die liggen op banen die via q punten na q keer weer in het oorspronkelijke punt terug keren. Omdat er q punten op zo'n baan liggen, zijn er dus (2^q - 2)/q afzonderlijke banen, en aangezien er een geheel aantal banen moet zijn is dit een geheel getal.

[AxzZzeL]

Een formule heeft altijd een = teken. Anders kan het niks betekenen.
x^2=4 betekent bijvoorbeeld dat x=-2 of x=2

[Diadem]

Ik heb geen idee waarom dit zo is. Ik weet wel dat ze dit ook gebruiken om snel grote priemgetallen te vinden (oa voor encryptie handig).

Dit is een speciaal geval van een meer algemene formule, toevallig heb ik hier gisteren tijdens werkcollege Wat is Wiskunde nog mee zitten spelen.

Let me think...

[Lord Daemon]

[Edit - Diadem poste er tussendoor, dit is dus een antwoord op de post daarvoor.]

Uhm - HUH? Sorry, maar (2^p -2)/p is een geheel getal voor elke p is priem is wel degelijk een goede wiskundige statement. Speciaal voor jou wil ik hem nog wel wat exacter opstllen hoor:

Voor alle p geldt dat als p een priemgetal is er geldt: 2^p - 2 = n * p, met p,n in N.

Mara het leek me eigenlijk wel duidelijk?

[joepP]

Kan de stelling niet nog sterker? Dus:

(n^p - n) mod p = 0 voor p=priem, n=natuurlijk getal

Nu nog ff bewijzen

[Diadem]

Hebbes.

Uit 'Foundations of Higher Mathematics, third edition' van Peter Fletcher en C. Wayne Patty.

Theorem 4.17

Fermat's Little Theorem

Let p be a prime, and let a be in N, such that p does not divide a. Then a^p-1 = 1 (mod p).


PROOF None of the p-1 integers, a, 2a,...,(p-1)a, is divisible by p because if P|ja for some j=1,2,...,p-1, then by Exercise 98 in Section 3.5, p|j. We show that no two of the integers a, 2a,...,(p-1)a are congruent modulo p. To see this, assume that there exists i,j (i != j) such that ia = ja (mod p). Then by Theorem 4.12, i = j (mod p). This is impossible because both i and j are less than p. Therefore, we have established that the set of integers a,2a,...,(p-1)a is congruent (in some order) to the set of integers 1,2,...,p-1. Hence 1a*2a*3a...(p-1)a = 1*2*3...(p-1)(mod p), and so, a^p-1(p-1)! = (p-1)! (mod p). Since gcd((p-1)!,p)=1, by Theorem 4.12, a^p-1 = 1 (mod p).

Dit is wat het boek zegt. Ik zal zo ff Theorem 4.12 en Exersie 98 in Section 3.5 opzoeken.

(in feite moet elke = in het bovenstaande stukje in feite een drievoudige = zijn. Zo eentje dus met 3 streeptjes boven elkaar. Maar ja, ik kan niet alles in ascii)

[Virgol]

(n^p - n) mod p = 0 voor p=priem, n=natuurlijk getal

Nee dat gaat niet. Dat gaat fout bij 341. Dat is naemlijk deelbaar door 11.

[Diadem]

Even uitleg waarom bovenstaande stelling en LD's stelling gelijk zijn.

a^p-1 = 1 (mod p).
Dus a^p-1 - 1 = 0 (mod p)
Dus (a^p-1 - 1) / p = k, voor k in N

Neem a = 2

(2^p/2 - 1) / p = k, voor k in N
(2^p - 2) / p = 2K, voor k in N

bewijs.

[edit]
Merk op dat dus (2^p) -2 / p niet alleen geheel maar zelfs even is.

[Lord Daemon]

Hm, het bewijs ontgaat mij gedeeltelijk. Weet iemand wat a|b betekent? En eigenlijk wil ik ook nog theorem 4.12 zien.

[Diadem]

Section 3.5, Exercise 98: Proof Corollary 3.11

(leuk toch zo'n boek). ok

Corollary 3.11:
If a, b, and c are integers, such that a and b are relatively prime and a|bc, t hen a|c.

(relatively prime betekent dat:
Two nonzero integers a and b are relatively prime provided that gcd(a,b) = 1
(gcd = greatest common diviser)


Owja, Theorem 4.12 nog.
Let n be in N, let a, b, c be in Z, and let d = gcd(c,n), and suppose that ac = bc (mod n). Then a = b (mod n/d).

PROOF Since ac = bc (mod n), n|(ac - bc). Therefore, there is an integer k such that c(a-b) = ac - bc = kn. Thus, (c/d)(a-b)=k(n/d). Since d = gcd(c,n), by Exercise 103 in Section 3.5, gcd(n/d,c/d)=1. Therefore, by Exercise 98 in Section 3.5 <small>(Commentaar van Diadem: hey, die kennen we)</small>, (n/d)|(a-b). Hence a = b(mod n/d).

Exercise 103 in Section 3.5 is simpelweg het bewijs dat gcd(a,b) = d if and only if gcd(a/d,b/d) = 1

[Verwijderd]

Op woensdag 28 november 2001 15:48 schreef Lord Daemon het volgende:

Weet iemand wat a|b betekent?

Even een wilde gok: a of b.

[joepP]

Op woensdag 28 november 2001 15:48 schreef Lord Daemon het volgende:
Hm, het bewijs ontgaat mij gedeeltelijk. Weet iemand wat a|b betekent? En eigenlijk wil ik ook nog theorem 4.12 zien.

a|b = a deelt b, dus b mod a = 0

[Diadem]

Op woensdag 28 november 2001 16:02 schreef joepP het volgende:

[..]

a|b = a deelt b, dus b mod a = 0

ja. Klopt. Ik wist dit niet zeker meer, heb het nog geprobeerd op te zoeken, maar staat nergens in mijn boek. Nogal slecht, termen gebruiken die je niet definieert. Maar goed, we zijn eruit.

[Diadem]

Zoals ik in mijn eerste post al zei wordt dit dus gebruikt om snel grote priemgetallen te vinden, wat weer handig is bij oa encryptie.

a^p-1 = 1 (mod p) als p een priemgetal is. Helaas is het geen voldoende voorwaarde dus, maar het is wel mogelijk de kans uit te rekenen dat p een priemgetal is als het aan deze voorwaarde voldoet (vraag me niet hoe). Als je dat dan weet kun je gewoon een paar verschillende a's uitproberen, en weet je al snel vrij zeker of p een priemgetal is of niet.

Je zou dan voor de zekerheid p nog kunnen checken op de normale manier als je voor meerdere a's een positief resultaat hebt.

[Verwijderd]

Goed ik was hier dus een heel verhaal aan het tikken dat de kleine stelling van Fermat bewees, maar m'n browser vond het nodig om m'n post te verneuken toen ik op backspace drukte, toen ik even niet in het tikvenstertje zat .

Nog 1 keertje dan, nu zonder bewijzen...

Stelling van Lagrange:
De orde (aantal elementen) van een ondergroep is een deler van de orde de groep.

Lemma:
De orde van een element is een deler van de orde van de groep.

Lemma:
x^|G| = e (met |G| de orde van de groep)

Stelling van Euler:
ggd(x,n) = 1 => x^(phi(n) = 1 mod n, met phi(n) = Euler phi functie = aantal getallen relatief priem met n (en kleiner of gelijk aan n)
(rel. priem = geen gemeenschappelijke delers)

Kleine stelling van Fermat:
Zij p priem, a geen veelvoud van p, dan
a^(p-1) = 1 mod p