Gebruiker:Wim Coenen/Kladblok2

Nieuw kopje aangemaakt: /* Een kortere weg. */

Een bewijs van de kleine stelling van Fermat.
Een passende titel voor mijn pagina heb ik noch niet.
Voorlopig heb ik de pagina in mijn kladblok de titel "Een kortere weg." gegeven.
[1] https://en.wikipedia.org/wiki/Binomial_theorem#Inductive_proof

Pythagorese drietallen

Pythagorese drietallen Voor het genereren van Pythagorese drietallen heb ik een zestal formules bedacht.

Test

$y=x\cdot {\frac {a^{2}-1}{a+1}}$
Een kortere weg.
${\frac {A^{p-1}-1}{p}}={\frac {({\frac {a}{b}})^{p-1}-1}{p}}={\frac {{\frac {a^{p-1}}{b^{p-1}}}-{\frac {b^{p-1}}{b^{p-1}}}}{p}}={\frac {\frac {a^{p-1}-b^{p-1}}{b^{p-1}}}{p}}={\frac {a^{p-1}-b^{p-1}}{pb^{p-1}}}$

De kleine stelling van Fermat

De kleine stelling van Fermat zegt dat, als $p$ een priemgetal is, voor ieder geheel getal $a$ geldt:

$a^{p}\equiv a{\pmod {p}}$

De stelling is genoemd naar Fermat (1601 of 1606/7 - 1665).

Een handig gevolg van de kleine stelling van Fermat is:

$a^{p-1}\equiv 1{\pmod {p}}$

De stelling is alleen geldig als $a$ en $p$ onderling ondeelbaar zijn. Als $p$ een priemgetal is, mag $a$ geen veelvoud van $p$ zijn.

De stelling wordt bijvoorbeeld gebruikt om bij modulair rekenen de restklasse van een groot getal uit te rekenen.

Bewijs van de kleine stelling van Fermat 

$a,p\in \mathbb {Z}$ en $p$ is een priemgetal.

• $a{\bmod {p}}$ is de rest bij geheeltallige deling van $a$ door $p$

Het bewijs van de kleine stelling maakt gebruik van een hulpstelling over modulair rekenen:

• Zij $a{\bmod {p}}\neq 0$, dan $a\cdot m\equiv a\cdot n{\pmod {p}}\Leftrightarrow m\equiv n{\pmod {p}}$

dus ook

• Indien $a{\bmod {p}}\neq 0$, dan $a\cdot m\not \equiv a\cdot n{\pmod {p}}\Leftrightarrow m\not \equiv n{\pmod {p}}$

Bewijs voor de kleine stelling:

Zij $p$ een priemgetal en $a\in \mathbb {Z}$. Er zijn twee mogelijkheden:

• $a{\bmod {p}}=0$; het spreekt in dit geval vanzelf dat $a^{p}\equiv a{\pmod {p}}$.
• $a{\bmod {p}}\neq 0$; beschouw alle getallen $1,2,\ldots ,p-1$. Deze $p-1$ getallen zijn modulo $p$ ongelijk aan 0. Het product van een van deze getallen met $a$ is modulo $p$ weer gelijk aan een van deze getallen. Dus $a\not \equiv 0{\pmod {p}}$ en als $a\cdot b\equiv 0{\pmod {p}}$, dan $a{\bmod {p}}=0$ of $b{\bmod {p}}=0$. Het product kan dus niet 0 zijn. Voor $x,y\in \{1,2,\ldots ,p-1\}$ geldt dat $x\not \equiv y{\pmod {p}}\Leftrightarrow a\cdot x\not \equiv a\cdot y{\pmod {p}}$. Dus vormen de getallen $a\cdot 1,a\cdot 2,\ldots ,a\cdot (p-1){\pmod {p}}$ een permutatie van de getallen $1,2,\ldots ,p-1$. Hieruit volgt voor de vermenigvuldiging met $a$ dat $(1\cdot a)\cdot (2\cdot a)\cdot \ldots \cdot ((p-1)\cdot a){\bmod {p}}=1\cdot 2\cdot \ldots \cdot (p-1)$, dus is $1\cdot 2\cdot \ldots \cdot (p-1)\cdot a^{p-1}\equiv 1\cdot 2\cdot \ldots \cdot (p-1){\pmod {p}}$. Daaruit volgt dat $a^{p-1}\equiv 1{\pmod {p}}$ en door beide zijden met $a$ te vermenigvuldigen dat $a^{p}\equiv a{\pmod {p}}$.

Analytisch bewijs van de kleine stelling van Fermat 

$A\neq ap$

Elk getal $A$ kan worden geschreven als $A=(A-1)+1$

${\frac {A^{p-1}-1}{p}}={\frac {((A-1)+1)^{p-1}-1}{p}}={\frac {\textstyle \sum _{k=0}^{p-1}\displaystyle {\tbinom {p-1}{k}}{(A-1)}^{k}1^{p-1-k}-1}{p}}$

${\frac {A^{p-1}-1}{p}}={\frac {1+\textstyle \sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}(A-1)^{k}1^{p-1-k}-1}{p}}={\frac {\textstyle \sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}(A-1)^{k}}{p}}$

${\displaystyle {\frac {A^{p-1}-1}{p}}={\frac {1}{p}}\textstyle \sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}}{(A-1)^{k}}$

$\textstyle \sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}{(A-1)}^{k}$ moet een p-voud zijn.

Inductiestap een.

$\displaystyle {\frac {A^{p-1}-1}{p}}={\frac {2^{p-1}-1}{p}}={\frac {1}{p}}\sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}{(2-1)^{k}}={\frac {1}{p}}\sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}$

De som van de binomiaalcoëfficiënten. 

${\binom {p-1}{k}}+{\binom {p-1}{k+1}}={\frac {(p-1)!}{(p-1-k)!k!}}+{\frac {(p-1)!}{(p-1-k-1)!(k+1)!}}$

${\binom {p-1}{k}}+{\binom {p-1}{k+1}}={\frac {(p-1)!(k+1)}{(p-1-k)!k!(k+1)}}+{\frac {(p-1)!(p-1-k)}{(p-1-k-1)!(k+1)!(p-1-k)}}$

${\binom {p-1}{k}}+{\binom {p-1}{k+1}}={\frac {(p-1)!(k+1+p-1-k)}{(p-(k+1))!(k+1)!}}={\binom {p}{k+1}}$

$\sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}=\sum _{k=1,3,5,\ldots }^{p-2}{\binom {p}{k+1}}=\sum _{k=1,3,5,\ldots }^{p-2}{\frac {p(p-1)!}{(p-(k+1))!(k+1)!}}=pq$

${\frac {1}{p}}\sum _{k=1}^{p-1}\displaystyle {\tbinom {p-1}{k}}=\sum _{k=1,3,5\ldots }^{p-2}{\frac {(p-1)!}{(p-(k+1))!(k+1)!}}=q$

${\frac {A^{p-1}-1}{p}}={\frac {2^{p-1}-1}{p}}=q$

$q\in \mathbb {N}$

Voor $A=2$ is de stelling waar.

Inductiestap twee

We nemen de waarheid van de stelling voor een zeker getal $A$ aan.

Dus:

${\frac {A^{p-1}-1}{p}}=R$

$R\in \mathbb {N}$

Inductiestap drie.

${\frac {(A+p)^{p-1}-1}{p}}={\frac {\textstyle \sum _{k=0}^{p-1}{\binom {p-1}{k}}A^{p-1-k}p^{k}-1\displaystyle }{p}}$

${\frac {(A+p)^{p-1}-1}{p}}={\frac {\textstyle A^{p-1}+\sum _{k=1}^{p-1}{\binom {p-1}{k}}A^{p-1-k}p^{k}-1\displaystyle }{p}}$

${\frac {(A+p)^{p-1}-1}{p}}={\frac {\textstyle \sum _{k=1}^{p-1}{\binom {p-1}{k}}A^{p-1-k}p^{k}\displaystyle }{p}}+{\frac {A^{p-1}-1}{p}}$

${\frac {(A+p)^{p-1}-1}{p}}=\textstyle \sum _{k=1}^{p-1}{\binom {p-1}{k}}A^{p-1-k}p^{k-1}\displaystyle +R=Q$

$Q\in \mathbb {N}$

De stelling is dus juist.

Pseudo-priemgetallen

Het omgekeerde van de kleine stelling van Fermat is niet algemeen geldig. Als voor zekere gehele $a$ en $k$ geldt dat

$a^{k}\equiv a{\pmod {k}}$,

dan is niet noodzakelijkerwijs $k$ een priemgetal.

Een getal $q$ dat geen priemgetal is, maar waarvoor geldt dat

$a^{q}\equiv a{\pmod {q}}$

voor zekere $a$ wordt een pseudopriemgetal genoemd. Als $q$ de eigenschap heeft dat het bovengenoemde geldt voor elke $a$, dan heet $q$ een carmichael-getal. Hierbij is de naam fermattest bedacht: als een getal $r$ voldoet aan

$a^{r}\equiv a{\pmod {r}}$

voor zekere $a$ dan is $r$ een priemgetal of een pseudo-priemgetal.

Er is bewezen dat er oneindig veel pseudo-priemgetallen bestaan. Echter, binnen de gehele getallen zijn de pseudo-priemgetallen wel 'dunner gezaaid' dan de priemgetallen.

Laatste stelling van Fermat

Zie Laatste stelling van Fermat voor het hoofdartikel over dit onderwerp.

De kleine stelling van Fermat mag niet worden verward met de laatste stelling van Fermat, die zegt dat de vergelijking $x^{n}+y^{n}=z^{n}$ geen geheeltallige oplossing heeft verschillend van 0 voor alle gehele waarden van $n$ groter dan 2. De stelling werd in november 1994 bewezen door de Britse wiskundige Andrew Wiles.

Literatuur

• M.C. van Hoorn, college over kleine stelling van Fermat aan de RUG

Categorie:Discrete wiskunde Categorie:Modulair rekenen Fermat