Springen naar inhoud

Kleine stelling van fermat


  • Log in om te kunnen reageren

#1

Zjarlotte

    Zjarlotte


  • 0 - 25 berichten
  • 1 berichten
  • Gebruiker

Geplaatst op 15 december 2005 - 16:36

Zou iemand mij het bewijs van de kleine stelling van fermat nog even gedetailleerd en logisch willen uitleggen? ik snap het bewijs nog niet helmeaal.. bedankt!

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

*_gast_PeterPan_*

  • Gast

Geplaatst op 15 december 2005 - 17:09

p is een priemgetal en b een ander getal.
Deel b door p.
Als de deling niet helemaal op gaat, houd je een rest over.
Die rest is een van de getallen 1,2,3,4,...,p-1.

Nu het probleem.
p is een weer priemgetal en a is niet deelbaar door p.

Bekijk nu het rijtje
a, 2a, 3a, 4a, 5a, ..., (p-1)a.

We delen al die getallen door p en kijken dan alleen naar de rest die je overhoudt.

Je krijgt dan het rijtje
r1, r2, r3, ..., rp-1

Al die r-retjes zijn dan getallen tussen 1 en p (p zelf niet).

Ik beweer nu dat al die r-retjes verschillend zijn.

Stel maar eens dat dat niet waar is.
Dan is bijvoorbeeld ri = rj (i>j).
Maar als ri = rj, dan geeft ia en ja dezelfde rest als je ze door p deelt.
Maar dan is ia - ja deelbaar door p. !!!
ia - ja is echter niet deelbaar door p, want ia-ja = (i-j)a en a is niet deelbaar door p en i-j ook niet want i-j<p.

Dus alle r-retjes zijn verschillend.
Maar dat kan alleen als het de getallen 1,2,3,...,p-1 zijn, maar dan niet per se in deze volgorde.
Dan is dus r1. r2.
Dus als je a.2a.3a.4a.....(p-1)a door p deelt krijg je dezelfde rest dan wanneer je r3. ... .rp-1 = 1.2.3.4.5.....(p-1)
door p deelt.
Met (p-1)! = 1.2....(p-1) geldt dus
(p-1)!ap-1 is equivalent met (p-1)! mod p.
Door (p-1)! delen en klaar is Kees.

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 15 december 2005 - 17:18

Even opnieuw, want in het vorige bericht zat iets fout.
p is een priemgetal en b een ander getal.
Deel b door p.
Als de deling niet helemaal op gaat, houd je een rest over.
Die rest is een van de getallen 1,2,3,4,...,p-1.

Nu het probleem.
p is een weer priemgetal en a is niet deelbaar door p.

Bekijk nu het rijtje
a, 2a, 3a, 4a, 5a, ..., (p-1)a.

We delen al die getallen door p en kijken dan alleen naar de rest die je overhoudt.

Je krijgt dan het rijtje
r1, r2, r3, ..., rp-1

Al die r-retjes zijn dan getallen tussen 1 en p (p zelf niet).

Ik beweer nu dat al die r-retjes verschillend zijn.

Stel maar eens dat dat niet waar is.
Dan is bijvoorbeeld ri = rk (i>k).
Maar als ri = rk, dan geeft ia en ka dezelfde rest als je ze door p deelt.
Maar dan is ia - ka deelbaar door p. !!!
ia - ka is echter niet deelbaar door p, want ia-ka = (i-k)a en a is niet deelbaar door p en i-k ook niet want i-k<p.

Dus alle r-retjes zijn verschillend.
Maar dat kan alleen als het de getallen 1,2,3,...,p-1 zijn, maar dan niet per se in deze volgorde.

Dus als je a.2a.3a.4a.....(p-1)a door p deelt krijg je dezelfde rest dan wanneer je r1, r2, r3, . ... .rp-1 = 1.2.3.4.5.....(p-1)
door p deelt.
Met 1.2....(p-1) afgekort tot (p-1)! geldt dus
(p-1)!ap-1 is equivalent met (p-1)! mod p.
Door (p-1)! delen en klaar is Kees.

#4

Nabuko Donosor

    Nabuko Donosor


  • >25 berichten
  • 94 berichten
  • Ervaren gebruiker

Geplaatst op 15 december 2005 - 23:45

Kleine stelling van Fermat Voor elk natuurlijk getal a en elk priemgetal p is p een deler van a^p - a.
Bewijs We gebruiken inductie naar a. Voor a = 0 is a^p-a=0 en dus geldt de stelling. Stel dat de stelling waar is voor a=k. Beschouw (k+1)^p = k^p + (p 1)k^(p-1) + ... + (p p-1)k + 1. (waar (p i) de binomiaalcoŽfficiŽnt p over i voorstelt). Stel nu p een willekeurig priemgetal, dan is (p k) deelbaar door p voor k = 1, 2, ... , p-1. (dit moet je maar eens controleren met de definitie van binomiaalcoŽfficiŽnt) Uit deze stelling volgt dat (k+1)^p - k^p - 1 deelbaar is door p. Onze inductiehypothese stelde dat k^p - k deelbaar is door p. Merk op dat [(k+1)^p - k^p - 1] + (k^p-k) = (k+1)^p - (k+1). Omdat het linkerlid deelbaar is door p en er een gelijkheidsteken staat, geldt dus dat (k+1)^p - (k+1) deelbaar is door p. Onze stelling is dus bewezen voor a=k+1 en bijgevolg voor alle natuurlijke getallen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures