Tallteori

Oppsummering av Tallteori (MA1301 ved NTNU).

Pytagoreiske tripler

Definisjon: x,y,z naturlige tall er en pytagoreisk trippel hvis x2+y2=z2. Notasjon: (x,y,z). Eksempel: (3,4,5). Definisjon: største felles divisor av tre naturlige tall a,b,c er det største tallet d som er slik at d\a og d\b og d\c. Lemma: (x,y,z) er … Les mer


primitive røtter

Definisjon: n er et naturlig tall. Da er a en primitiv rot av n hvis a har orden φ(n) modulo n. Teorem: n er et naturlig tall. a1, a2, …, aφ(n) er relativt pimiske til n og ikke større enn n. … Les mer


Orden

Definisjon: n er et naturlig tall, a er et heltall relativt primisk til n. Det minste naturlige tallet k slik at ak ≡ 1 (mod n) kalles ordenen til a modulo n. Eks: 2 har orden 10 modulo 11 fordi 10 … Les mer


RSA Kryptering

RSA er et krypteringssystem som benytter seg av offentlig nøkkel-kryptografi. Det vil si at den har to «nøkler»; én offentlig for å kryptere, og én privat for å dekryptere. En melding som er kryptert med en offentlig nøkkel kan kun … Les mer

Eulers Teorem

Lemma: n er et naturlig tall, a er et tall relativt primisk til n. φ(n) naturlige tall er relativt primisk til n. a1, a2, … , aφ(n) er disse tallene. Da er a*a1, a*a2, … , a*aφ(n) kongruente med tallene a1, … Les mer

Tallteoretiske funksjoner

Kort forklart er en tallteoretisk funksjon en funksjon som ser på egenskapene til input. For å sette opp formlene under definerer vi n = a1k1*a2k2*…*arkr Τ (Tau): T(n) er antall positive divisorer d til n sik at 0 < d ≤ n. … Les mer

Wilsons Teorem

Lemma: p er et primtall og a er et tall slik at p ikke deler a. Da er a sin egen invers hvis og bare hvis a ≡ 1 eller -1 (mod p). Teorem: n er et naturlig tall > 1. … Les mer

Fermats lille teorem

Teorem: La p være et primtall og a et heltall så p ikke deler a. Da er ap-1 ≡ 1 (mod p) Eksempel på bruksområde: regn ut 6^195 mod 17. 17 er primtall og deler ikke 6, dermed kan vi bruke … Les mer

Det kinesiske restteoremet

Det kinesiske restteoremet handler om å løse et likningssystem som består av flere kongruenslikninger med forskjellig modulus. For å løse det må vi definere noen ting først. Definisjon: La a,c og m være heltall med m > 0. Hvis ac ≡ … Les mer

Kongruensregning

Selve kjernen i tallteori, ofte kalt klokkearitmetikk. Definisjon: la a,b,m være heltall med m > 0. hvis m \ (a-b) så er a kongruent med b modulo m. Tallet m kalles modulus Notasjon: a ≡ b (mod m). Dersom a ikke … Les mer