Gebruiker:Wim Coenen/Kladblok2

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

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 drietallenBewerken

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

TestBewerken

 
Een kortere weg.
 

De kleine stelling van FermatBewerken

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

 

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

Een handig gevolg van de kleine stelling van Fermat is:

 

De stelling is alleen geldig als   en   onderling ondeelbaar zijn. Als   een priemgetal is, mag   geen veelvoud van   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 

  en   is een priemgetal.

  •   is de rest bij geheeltallige deling van   door  

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

  • Zij  , dan  

dus ook

  • Indien  , dan  

Bewijs voor de kleine stelling:

Zij   een priemgetal en  . Er zijn twee mogelijkheden:

  •  ; het spreekt in dit geval vanzelf dat  .
  •  ; beschouw alle getallen  . Deze   getallen zijn modulo   ongelijk aan 0. Het product van een van deze getallen met   is modulo   weer gelijk aan een van deze getallen. Dus   en als  , dan   of  . Het product kan dus niet 0 zijn. Voor   geldt dat  . Dus vormen de getallen   een permutatie van de getallen  . Hieruit volgt voor de vermenigvuldiging met   dat  , dus is  . Daaruit volgt dat   en door beide zijden met   te vermenigvuldigen dat  .
Analytisch bewijs van de kleine stelling van Fermat 

 

Elk getal   kan worden geschreven als  

 

 

 

  moet een p-voud zijn.

Inductiestap een.

 

De som van de binomiaalcoëfficiënten. 

 

 

 

 

 

 

 

Voor   is de stelling waar.

Inductiestap twee

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

Dus:

 

 

Inductiestap drie.

 

 

 

 

 

De stelling is dus juist.

Pseudo-priemgetallenBewerken

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

 ,

dan is niet noodzakelijkerwijs   een priemgetal.

Een getal   dat geen priemgetal is, maar waarvoor geldt dat

 

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

 

voor zekere   dan is   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 FermatBewerken

  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   geen geheeltallige oplossing heeft verschillend van 0 voor alle gehele waarden van   groter dan 2. De stelling werd in november 1994 bewezen door de Britse wiskundige Andrew Wiles.

LiteratuurBewerken

Categorie:Discrete wiskunde Categorie:Modulair rekenen Fermat