Tallteori

Oppsummering av Tallteori (MA1301 ved NTNU).

Aritmetikkens fundamentalteorem

Aritmetikkens fundamentalteorem sier at alle naturlige tall kan faktoriseres i primtall på en entydig måte opp til faktorenes orden (rekkefølgene på faktorene). Eksempel: 12 = 2 * 2 * 3 – dette er eneste måten å skrive 12 som produkt … Les mer


Primtall

Blant de naturlige tallene finnes det to typer tall; Primtall og sammensatte tall (foruten 1, det er ingen av delene). Definisjon: Et naturlig tall p > 1 som ikke har noen andre positive divisorer enn 1 og seg selv kalles … Les mer


Binomialkoeffisienter

Binomialkoeffisienter er kort forklart hvor mange muligheter vi kan plukke ut k elementer av totalt n elementer. For 0≤k≤n er binomialkoeffisienten definert slik: n!/(k!*(n-k)!). Derom k < 0 eller k > n er dessuten dette definert som 0. I denne … Les mer


Euklids algoritme

Euklids algoritme brukes for å beregne største felles divisor til to tall. Dette er en enkel teknikk som er veldig effektiv, også med relativt store tall. Hele ideen er basert på at man kan bytte ut tallene med mindre tall … Les mer

Induksjonsbevis

Inudksjonsbevis er en bevisform der man beviser noe for alle n blant de naturlige tallene. Dette består av to steg: basissteget: Her viser vi at det stemmer for n=1 Induksjonssteget: Her antar vi at det stemmer for n=k, og viser at … Les mer

Logikknotasjon

  Notasjon Betydning Beskrivelse  ∧  og  ∨  eller enten en av uttrykkene, eller begge  ¬  ikke  ⇒  medfører «hvis … så …»  ⇔  ekvivalent med «hvis og bare hvis».  ∀  for alle tall  uttrykket gjelder for alle tall markert med … Les mer