Laatste berichten
-
00:15
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
22:27
positie 1
-
21:15
Weerfrustratie 9
-
18:24
Schroefdraad berekening 5
-
18:08
geen minkowski-ruimte toch? Doe ik dit nou fout? 15
-
14:16
do-re-mi-fa-so vliegtuigen 7
-
14:16
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
-
13:57
De Euro Nederlandse 100 qubit computer komt eraan
-
10:42
projectiel 8
-
10:37
Verschil tussen deze 2 vragen 5
-
09:25
[scheikunde] berekeningen labo vitamine c bepaling 1
-
22 apr
[wiskunde] rode en witte ballen verdelen 8
-
22 apr
Rotatie van het heelal 41
-
22 apr
Muntje opgooien 14
-
21 apr
Reactiviteit silyl enol ethers 1
-
21 apr
Criterium voor vochtretentie
-
21 apr
speciale rel. theorie 5
-
21 apr
Vogels in de stad zijn goede klussers
-
21 apr
Ervaringen met "herontdekkingen" 15
-
20 apr
Herleiden afmetingen vanaf een foto 19
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
Kleine stelling van fermat
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
-
- Berichten: 1
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!
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.
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.
-
- Berichten: 94
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.
