Puzzels
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Kleine stelling van fermat
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!
ads
-
PeterPan
- Artikelen: 0
Re: Kleine stelling van fermat
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.
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.
-
PeterPan
- Artikelen: 0
Re: Kleine stelling van fermat
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.
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.
ads
Steun Sciencetalk
5 stuks Plastic Labels 91201 geschikt voor Dymo LetraTag Labelprinter - Zwart op Wit - 12 mm x 4 m - S0721610 Labeltape - Telano
-
Nabuko Donosor
- Artikelen: 0
- Berichten: 94
- Lid geworden op: di 04 jan 2005, 11:33
Re: Kleine stelling van fermat
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.
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.
