p2 - 1 is deelbaar door 24

Het februarinummer van Pythagoras vermeldt een elementaire maar weinig bekende stelling over priemgetallen: voor elk priemgetal p groter dan 3 geldt dat p2 - 1 deelbaar is door 24. Het Pythagorasnummer citeert het probleem uit de sectie “Doe het zelf” van het boek “Opgelost, toepassingen van wiskunde en informatica” van Bennie Mols. Die suggereert om de stelling aan te tonen met behulp van het feit dat elk priemgetal p > 3 kan geschreven worden als 6n - 1 of 6n + 1. Ik ga hier een aantal verschillende bewijzen geven.

Stelling: voor elk priemgetal p groter dan 3 geldt dat p2 - 1 deelbaar is door 24.

Bewijs 1

Eerst via de gesuggereerde weg. Als we getallen schrijven in de vorm 6n + k, zijn er 6 mogelijkheden: 6n, 6n + 1, 6n + 2, 6n + 3, 6n + 4 en 6n + 5. Daarvan kunnen we 6n, 6n + 2 en 6n + 4 al schrappen omdat die getallen even zijn. 6n + 3 is deelbaar door 3 dus schrappen we ook. Dan hebben we nog twee mogelijkheden over voor priemgetallen groter dan 3: 6n + 1 en 6n + 5, en die laatste kunnen we (voor een andere n) ook schrijven als 6n - 1.

Daarmee hebben we ons tussenresultaat al bewezen. Hoe bewijzen we hier nu uit dat p2 - 1 deelbaar is door 24? We vullen gewoon in: p2 - 1 = (6n ± 1)2 - 1 = 36n2 ± 12n = 12n(3n ± 1). Als n even is, dan is dit deelbaar door 12*2 = 24. Als n oneven is, dan is 3n ± 1 deelbaar door 2 en is p2 - 1 weer deelbaar door 12*2 = 24. QED

Bewijs 2

Een ander bewijs gaat rechtstreeks en vind ik een veel elegantere redenering: p2 - 1 is een veelterm die te ontbinden is tot (p - 1)(p + 1). Omdat p oneven is, zijn zowel p - 1 als p + 1 even. Meer nog, p - 1 en p + 1 zijn opeenvolgende even getallen, dus één van de twee is ook nog eens deelbaar door 4. p2 - 1 is dus al zeker deelbaar door 8. Bovendien moet één getal in de reeks van drie opeenvolgende getallen p - 1, p en p + 1 deelbaar door 3 zijn. Aangezien we p > 3 hebben gekozen en p een priemgetal is, is p - 1 of p + 1 deelbaar door 3. Aangezien 3 en 8 onderling ondeelbaar zijn, is hun product 24 ook een deler van p2 - 1. QED

Bewijs 3

Ik heb deze stelling ooit op nog een andere manier zien bewijzen: helemaal niet mooi, maar door puur rekenwerk en gevallen elimineren. Voor de volledigheid vermeld ik dit bewijs ook, zodat je zelf eens kan vergelijken:

p is een priemgetal groter dan 3 en dus niet deelbaar door 3, dus van de vorm 3n + 1 of 3n + 2. p2 - 1 is in beide gevallen gelijk aan 9n2 + 6n respectievelijk 9n2 + 12n + 3. In beide gevallen is p2 - 1 dus deelbaar door 3. Nu gaan we naar de deling door 8 kijken: p is een priemgetal groter dan 3 en dus niet even, dus van één van de vier volgende vormen: 8n + 1, 8n + 3, 8n + 5 of 8n + 7. Voor deze vier gevallen berekenen we p2 - 1: respectievelijk 64n2 + 16n, 64n2 + 48n + 8, 64n2 + 80n + 24 en 64n2 + 112n + 48. Al deze gevallen zijn deelbaar door 8. Voor alle mogelijke gevallen van p is p2 - 1 dus deelbaar door 3 en 8 en dus ook door 24. QED

Conclusie

Ik ben de laatste tijd erg geïnteresseerd geraakt in verschillende manieren om stellingen te bewijzen en hoe we die verschillende bewijzen beoordelen. Ik vind zelf bewijs 2 hier het elegantste, en niet alleen omdat het zo eenvoudig en kort is: buiten de ontbinding in factoren van p2 - 1 komt er geen expliciet rekenwerk in voor. Met wat redeneren over deelbaarheid kom je er en zie je als het ware waarom de stelling waar is. Bewijs 1 is ook nog vrij eenvoudig en niet al te lelijk.

Bewijs 3 vind ik echter heel lelijk. Het spreekt me helemaal niet aan: je bewijst de stelling wel, maar het is meer een kwestie van alle mogelijke gevallen afgaan en uitrekenen dat p2 - 1 in elk geval deelbaar is door 24. Het is niet echt slim, je zou het een computer kunnen leren. Het doet me dan ook een beetje denken aan een miniversie van het computerbewijs van het vierkleurenprobleem, dat de stelling in kwestie ook bewijst door alle mogelijke gevallen (in dat bewijs mogelijke tegenvoorbeelden) af te gaan en uit te rekenen.

Een extra argument voor de elegantie van bewijs 2 is dat de aanpak een andere stelling suggereert: voor elk priemgetal p groter dan 5 geldt dat p4 - 1 deelbaar is door 120. Het bewijs: p4 - 1 is (p2 - 1)(p2 + 1). Het eerste deel is deelbaar door 24, hebben we bewezen. Nu moeten we nog bewijzen dat één van de factoren p -1, p + 1 en p2 + 1 deelbaar is door 5 voor een priemgetal p > 5. We hebben vier mogelijke waarden van p mod 5 (dit is de rest van p bij deling door 5): 1, 2, 3 en 4. Als p = 1 mod 5, dan is p - 1 deelbaar door 5. Als p = 4 mod 5, dan is p + 1 deelbaar door 5. Als p = 2 of 3 mod 5, dan is p2 + 1 deelbaar door 5, want 22 + 1 en 32 + 1 zijn respectievelijk gelijk aan 5 en 10. p4 - 1 is dus voor priemgetallen p > 5 deelbaar door 24 en deelbaar door 5, dus deelbaar door 120. QED

Comments

  1. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    bewjs 2 is het mooiste, maar heeft één groot gebrek: het vergeet aan te tonen dat p helemaal geen priemgetal hoeft te zijn

    het is voldoende dat p oneven is en ondeelbaar door drie

    25^2 - 1 = 624 = 26 * 24

    een klein bewijsje hiervan staat op de blog van de conceptuele ingenieur

    een variant hiervan:

    p is niet deelbaar door drie
    dan p = 3m + 1 of p = 3m + 2 (m= 0,1,2…)

    p^2 - 1 = 9m^2 + 6m, of
    p^2 - 1 = 9m^2 + 12m + 3

    beiden deelbaar door 3

    (Je kan ook de kleine stelling van Fermat gebruiken)

    analoog

    p is oneven dan
    p = 4m + 1 of 4m + 3

    uitrekenen geeft weer dat p^2 - 1 deelbaar is door acht

    en dan verder zoals in de bewijzen hierboven.

  2. Koen VervloesemNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Dat klopt, maar daar is dan ook maar een kleine aanpassing in bewijs 2 voor nodig: op maar één plaats wordt daar het feit gebruikt dat p een priemgetal groter dan 3 is, en daar kan je dat zonder moeilijkheden vervangen door p is niet deelbaar door 3. Dat is dan ook een voordeel van het bewijs: dat het met een triviale aanpassing meer bewijst dan gevraagd is.

  3. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    OK, ik liet dit maar weten omdat ik dacht dat je die stelling besprak in je thesis. Dan kan je niet nauwkeurig (pedant?) genoeg zijn. Ik heb mijn bewijs even opgesteld omdat het “manifest” van de veronderstelling vertrekt dat p oneven is en niet deelbaar is door drie.

    Misschien moet je ook even kijken naar je uitbreiding naar p^4 - 1. Een striktere formulering is hier (evident) dat voor p oneven en niet deelbaar door 3 of 5 de uitdrukking p^4 - 1 deelbaar is door 120.

    Bijvoorbeeld: 49^4 - 1 = 48040 * 120

    Hier kan overigens weer met vrucht de kleine stelling van Fermat gebruiken, die zonder enig rekenwerk bevestigt dat voor p niet deelbaar door 5 de uitdrukking p^4 - 1 deelbaar is door 5.

    W

  4. Koen VervloesemNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Bedankt trouwens voor de tip om de kleine stelling van Fermat hier te gebruiken, daar had ik nog niet aan gedacht. Het zorgt natuurlijk voor minder ‘elementaire’ bewijzen, terwijl bewijs 2 zoals ik het hier voorstel door een middelbare scholier met een minimale basiskennis van getaltheorie kan begrepen worden.

  5. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Overigens… hier stelt zich de vraag… wat is de algemene vorm van de stelling?

    Is het dit?

    “Neem een priemgetal q. Noem q1, q2… de priemgetallen kleiner dan q. Q1=2, q2=3, q3=5 enzovoort.

    Neem a oneven en niet deelbaar door q. Dan is is a^(q-1) - 1 deelbaar door q1^3*q2*…*q.”

    Lijkt me interessant om te bewijzen. Of toch te proberen.

    Dat a^(q-1) - 1 deelbaar is door q volgt alvast uit Fermat…

  6. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Neen, dat klopt helaas niet. Voor q=7 en a=13 spreekt mijn Casio me tegen. Niet deelbaar door 5.

  7. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Maar voor q=7 en a=11, a=13, a=17, a=19, a=23, a=25 (!!), a=29, a=31 geeft de formule a^(q-1) - 1 wel getallen deelbaar door 24 en door 7. Net als voor a=25.

    A=9, a=15, a=27 en a=33 werken niet voor de delers 24 en 7.

    Zou de stelling zijn:

    “Neem een priemgetal q. Neem een a niet deelbaar door 2, 3 en q. Dan is a^(q-1) - 1 deelbaar door 2^3*3*q” ?

    Mmm… Ik raak geen klap verder… Nachtje over slapen.

    Veel succes met je thesis!

    Dit is overigens allemaal wonderlijk. Het doet me -als u mij permitteert!- twijfelen aan het idee dat de wiskunde een “sociale constructie” is. Of beter gezegd: aan het idee dat de beschrijving “sociale constructie” ook maar iets toevoegt aan wat alle wiskundigen al weten.

  8. aliaspgNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Het werkt ook voor q=7 en a=5, dat was ik nog vergeten. 5^6 - 1 = 15624 = 24*7*93. Merkwaardig.

  9. MaximaNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Hallo. Bekend is mij dat oneven niet priemgetallen altijd deelbaar zijn door 3,5,7,11 of 13. Ik vraag mij af hoe dit te bewijzen is. Weet u een manier om dit te bewijzen? Ik hoop op een reactie. Alvast bedankt.

  10. Koen VervloesemNo Gravatar" onclick="javascript:urchinTracker( wrote:

    Dat klopt niet. Neem bijvoorbeeld het oneven niet-priemgetal 323: dit is deelbaar door 17 en 19, maar niet door 3, 5, 7, 11 of 13.

  11. Arno van AsseldonkNo Gravatar" onclick="javascript:urchinTracker( wrote:

    @Maxima: Een ander tegenvoorbeeld voor de uitspraak “Een samengesteld oneven getal is altijd deelbaar door 3, 5, 7, 11 of 13″ is het getal 51. Dit heeft de priemfacoren 3 en 17. Er geldt wel dat een samengesteld oneven getal uitsluitend in oneven priemfactoren is te ontbinden, en dat 3 de laagst mogelijke oneven priemfactor is.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*

*