Vad man bör kunna i kapitel 3 (Aritmetik)

Vi har nu tagit oss igenom kapitel 3 om aritmetik (talteori). Det kan vara dags att sammanfatta lite vad man bör kunna.

Division, kvot och rest. Detta är ju i den enklaste formen grundskolematematik; $47/11 = 4+3/11$. Här är "kvoten" 4, dvs 11 "går i" 47 4 gånger. Resten blir 3.

Delbarhet. Notationen $a | b$ betyder att $a$ delar $b$. Till exempel gäller att $14|42$ därför att $42$ kan skrivas som $14$ gånger ett heltal (3). Med andra ord $42/14$ är ett heltal.

Primtal är heltal större än 1 som inte har några andra delare än $\pm 1$ och (plus/minus) sig själva. Till exempel är 439 ett primtal därför att de enda tal som delar 439 är $\pm 1$ och $\pm 439$. Talet 440 är å andra sidan inte ett primtal, eftersom det har andra elare, till exempel 2, 5, 10 och 11. Talet $440$ kan faktoriseras som en produkt av primtal: $440 = 2\cdot 2\cdot 2\cdot 5 \cdot 11$.

Det finns oändligt många primtal, vilket bevisades av Euklides ungefär år 300 f Kr.

Enligt aritmetikens fundamentalsats kan varje positivt heltal skrivas som en produkt av primtal på (väsentligen) exakt ett sätt. Reservationen "väsentligen" syftar på att man givetvis kan skriva primfaktorerna i olika ordning, men varje primtal förekommer ett bestämt antal gånger. Om man till exempel skriver 440 som en produkt av primtal, kommer talet 2 alltid att förekomma exakt tre gånger. 

Delargrafen till ett tal är ingenting man behöver plugga in för dess egen skull. Den är bara till för att underlätta förståelsen, inte skapa nya problem.

En linjärkombination av två (eller flera) tal $x$ och $y$ är (precis som i linjäralgebran) ett uttryck på formen $ax+by$, där $a$ och $b$ är heltal. Om ett tal $d$ är gemensam delare till $x$ och $y$, så kommer $d$ också att dela $ax+by$.

Euklides algoritm är en metod för att beräkna de största gemensamma delaren till två tal $x$ och $y$, vilket samtidigt är den minsta positiva linjärkombinationen av $x$ och $y$.

Den minsta gemensamma multipeln $lcm(x,y)$ av två tal $x$ och $y$ är, som namnet antyder, det minsta tal som har både $x$ och $y$ som delare. Om man har beräknat största gemensamma delaren till $x$ och $y$, dvs $gcd(x,y)$, kan den minsta gemensamma multipeln beräknas genom \[lcm(x,y) = \frac{x\cdot y}{gcd(x,y)}.\]

När man adderar bråk, förlänger man så att bråken får "minsta gemensamma nämnare". De möjliga nämnarna är ju multipler av den ursprungliga, så "minsta gemensamma nämnare" betyder egentligen minsta gemensamma multipel (av nämnarna).

Diofantiska ekvationer betyder egentligen ekvationer där man söker heltalslösningar. De ekvationer vi tittar på i den här kursen är linjära ekvationer i två variabler, dvs ekvationer av typen \[ax + by = c,\] där konstanterna $a$, $b$ och $c$ är heltal. Geometriskt är lösningsmängden en rät linje i planet, så frågan är vilka heltalspunkter en sådan linje passerar genom.  Sådana ekvationer löses med Euklides algoritm.

Modulär aritmetik eller kongruensräkning handlar om att man räknar "modulo $n$", där $n$ är något positivt heltal. Man kan också säga att man enbart räknar med "rester" vid division med $n$. Om man till exempel räknar modulo 12 (klockan), så är $4$, $16$ och $-8$ samma sak. Man säger att de talen är kongruenta modulo 12, vilket skrivs \[4 \equiv 16 \equiv -8 \quad \text{(mod 12)}.\]

Systemet av restklasser modulo $n$ betecknas $\mathbb{Z}_n$.

Ekvationer av typen $ax = b$ i $\mathbb{Z}_n$ kan reduceras till diofantiska ekvationer i två variabler, och löses alltså med Euklides algoritm.

Det finns även ett avsnitt om binära tal och andra talbaser. Man bör kunna konvertera tal mellan binärt och decimalt. Exempelvis är talet $77 = 64+8 + 4 +1$, så binärt skrivs 77 som $1001101$.