1.1 Delelighet, primtall og aritmetikkens fundamentalteorem

$$a\mid b,$$

og leser det «$a$ deler $b$». Hvis det ikke finnes noe slikt $t$, skriver vi $a\nmid b$.

Her er $a$ og $b$ hele tall, og $a\ne 0$. Merk retningen på symbolet: det lille tallet står først. $3\mid 12$ er sant, $12\mid 3$ er galt. Dette er den vanligste forvekslingen i faget, og den koster hele oppgaver.

Poenget med formen «det finnes en $t$»: når du skal bevise noe om delelighet, er $t$ det du får utdelt gratis. Sier oppgaven $a\mid b$, skriver du straks $b=at$ og har et tall å regne med. Sier oppgaven at du skal vise $a\mid b$, er jobben å produsere en $t$.

Når $a\mid b$, kaller vi $a$ en divisor i $b$, og $b$ et multiplum av $a$.

Hvert tall $n>1$ har alltid minst fire divisorer å regne med: $1$, $-1$, $n$ og $-n$. Disse kalles de trivielle divisorene, fordi de finnes uansett hva $n$ er. En divisor $d$ med $1<d<n$ kalles en ekte divisor.

Det er de ekte divisorene alt handler om: et tall er et primtall nettopp når det ikke har noen.

I dette faget arbeider vi nesten alltid med positive divisorer, og skriver bare $1$ og $n$ når vi mener de trivielle. Fortegnet spiller sjelden noen rolle, siden $a\mid b$ nøyaktig når $|a|\mid|b|$.

1. Hvis $a\mid b$ og $a\mid c$, så $a\mid(b+c)$ og $a\mid(b-c)$.
2. Hvis $a\mid b$, så $a\mid bc$ for hvilken som helst $c$.
3. Lineærkombinasjonsregelen (den viktigste): hvis $a\mid b$ og $a\mid c$, så
$$a\mid(bx+cy)\qquad\text{for alle hele tall }x,y.$$
4. Hvis $a\mid b$ og $b\mid c$, så $a\mid c$.

Regel 3 inneholder regel 1 og 2 som spesialtilfeller ($x=y=1$, henholdsvis $y=0$). Denne regelen må sitte utenat — den er verktøyet i et flertall av delelighetsbevisene på eksamen, og den er selve grunnen til at Euklids algoritme virker.

Alle fire bevises på samme måte: skriv $b=at$ og $c=as$, og faktoriser ut $a$.

$$ax+by,$$

der $x$ og $y$ er hele tall. Både $x$ og $y$ får være negative eller null.

Uttrykket ser uskyldig ut, men det er det sentrale i hele Del 1. To eksempler på hvor det dukker opp: Bézouts identitet (kap. 1.2) sier at $\gcd(a,b)$ selv er en lineærkombinasjon av $a$ og $b$; og en lineær diofantisk likning (kap. 1.3) spør nettopp om hvilke tall som er lineærkombinasjoner av $a$ og $b$.

Lineærkombinasjonsregelen over sier derfor noe sterkt: enhver felles divisor i $a$ og $b$ deler alle lineærkombinasjoner av dem.

Hvis $a\mid b$ og $b\mid c$, så $a\mid c$.

Beviset er én linje og verdt å kunne kjøre: $b=at$ og $c=bs$ gir $c=(at)s=a(ts)$, og $ts$ er et helt tall.

Praktisk bruk: transitiviteten er grunnen til at det holder å finne én primdivisor når du skal vise at et tall er sammensatt. Har du vist at $7\mid n$, og $7$ er et primtall, er $n$ sammensatt — du behøver ikke faktorisere resten.

$$a=qb+r,\qquad 0\le r<b.$$

Tallet $q$ heter kvotienten og $r$ heter resten.

To ting er verdt å merke seg, og de er begge kilder til feil:

- Resten er alltid ikke-negativ, og alltid strengt mindre enn $b$. Betingelsen $0\le r<b$ er ikke pynt — det er den som gjør paret entydig.
- Entydigheten er det vi bruker. Har du på ett vis funnet $a=qb+r$ med $0\le r<b$, så er det det svaret; ingen annen framstilling finnes.

Dette må sitte utenat, med begge betingelsene. Divisjonsalgoritmen er den ene setningen Euklids algoritme kjøres på, om og om igjen.

I $a=qb+r$ er kvotienten $q$ hvor mange hele $b$-er som får plass i $a$, og resten $r$ er hva som blir liggende igjen.

Notasjon vi bruker gjennom boka: $a\bmod b$ betyr resten $r$. Altså er $17\bmod 12=5$.

Sammenhengen med delelighet er direkte: $b\mid a$ nøyaktig når $a\bmod b=0$. Delelighet er altså spesialtilfellet «ingen rest» av divisjonsalgoritmen, og resten er målet på hvor langt fra delelighet vi er. Hele resten av faget handler om det målet.

Ta $a=-37$ og $b=10$. Fristelsen er å skrive $-37=(-3)\cdot 10-7$, altså rest $-7$. Men $-7$ er negativ, så det bryter betingelsen. Riktig framstilling er

$$-37=(-4)\cdot 10+3,\qquad 0\le 3<10.$$

Regelen: rund kvotienten nedover (mot minus uendelig), aldri mot null. Da blir resten automatisk ikke-negativ.

Kontrollen tar to sekunder: er resten din negativ eller $\ge b$, har du valgt feil $q$. Legg til eller trekk fra én, og juster resten med $b$.

Et helt tall $p>1$ er et primtall hvis det ikke har andre positive divisorer enn $1$ og $p$ selv — altså ingen ekte divisorer.

De første er $2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,\dots$

Tre presiseringer som er verdt å ha på plass:

- $1$ er ikke et primtall. Grunnen er ikke smakssak: hadde $1$ vært med, ville entydig faktorisering falt bort, siden $6=2\cdot 3=1\cdot 2\cdot 3=1\cdot 1\cdot 2\cdot 3$.
- $2$ er et primtall, og det eneste like. Alle andre primtall er odde — et faktum som brukes i praktisk talt hver case-analyse i Del 6.
- Kravet $p>1$ utelukker også $0$ og de negative tallene fra definisjonen.

I dette faget dukker primtallene opp i tre roller: som byggesteiner i faktoriseringen, som moduler (Fermat og Wilson gjelder bare modulo primtall), og som selve emnet i bevisoppgavene.

$$n=ab\qquad\text{med}\qquad 1<a\le b<n.$$

Tallet $1$ er verken primtall eller sammensatt — det står i en klasse for seg (det kalles en enhet).

Merk hva det koster å vise de to tingene. For å vise at $n$ er sammensatt holder det å finne én divisor. For å vise at $n$ er et primtall må du utelukke alle. Det er derfor prøvedivisjon trenger trikset i neste kort — uten det ville jobben vært håpløs.

Hvis $n$ er sammensatt, har $n$ en primdivisor $p$ med $p\le\sqrt n$.

Utledningen tar to linjer og utledes på stedet: skriv $n=ab$ med $1<a\le b<n$. Var begge faktorene større enn $\sqrt n$, ville $n=ab>\sqrt n\cdot\sqrt n=n$ — umulig. Altså er $a\le\sqrt n$, og enhver primdivisor i $a$ er da også $\le\sqrt n$ og deler $n$.

Konsekvensen er hele grunnen til at prøvedivisjon er praktisk: finner du ingen primdivisor $\le\sqrt n$, er $n$ et primtall. Du slipper å teste videre.

Bildet bak navnet: divisorene i $n$ kommer i par $(a,b)$ med $ab=n$, og i hvert par ligger én på hver side av $\sqrt n$. Finner du ingen på undersiden, finnes det ingen par — og da ingen ekte divisor.

Slik avgjør du om $n$ er et primtall, med penn og enkel kalkulator:

1. Regn $\sqrt n$, og finn det største hele tallet under (dette er den øvre grensen).
2. Prøv å dele $n$ på primtallene $2,3,5,7,11,\dots$ opp til denne grensen.
3. Går ingen av dem opp, er $n$ et primtall. Går én opp, er $n$ sammensatt — og du har funnet en faktor.

Bare primtallene trenger testes. Grunnen: hvis et sammensatt tall som $6$ deler $n$, gjør $2$ det også, så $2$ ble allerede fanget.

Prosedyren må sitte utenat, og den er verdt å kjøre til den er automatisk — under kode D er det den eneste faktoriseringsmetoden du har. To snarveier å ha i fingrene: $3\mid n$ nøyaktig når siffersummen er delelig med $3$, og $11\mid n$ nøyaktig når den alternerende siffersummen er delelig med $11$.

$$\gcd(a,b).$$

Notasjonen skrives $\gcd$ med bakstrek i formler, aldri bare «gcd» inne i en formel. Noen bøker skriver $(a,b)$; denne boka gjør det ikke, fordi det kolliderer med parentesbruk ellers.

Tre verdier du bør kunne umiddelbart: $\gcd(a,a)=a$ for positiv $a$; $\gcd(a,0)=a$; og $\gcd(a,1)=1$.

Hvorfor begrepet er så sentralt: $\gcd(a,b)$ avgjør om likningen $ax+by=c$ har heltallsløsninger (kap. 1.3), hvor mange løsninger kongruensen $ax\equiv b\pmod m$ har (kap. 1.4), om et tall har en modulær invers, og om du får bruke Eulers teorem (kap. 2.1). Fire av bokas fem søyler går gjennom dette ene tallet.

$$\operatorname{lcm}(a,b).$$

Skrivemåten er $\operatorname{lcm}$ med \operatorname i formler, slik at det settes som et funksjonsnavn og ikke som produktet $l\cdot c\cdot m$.

Merk at $\operatorname{lcm}$ og $\gcd$ er speilbilder: $\gcd$ er den største som deler inn i begge, $\operatorname{lcm}$ det minste som begge deler inn i. Alltid er $\gcd(a,b)\le a,b\le\operatorname{lcm}(a,b)$.

$\operatorname{lcm}$ dukker opp i det kinesiske restteoremet (kap. 2.4): når to kongruenser med moduler $m$ og $n$ skal gjelde samtidig, er perioden til den kombinerte løsningen $\operatorname{lcm}(m,n)$.

$$\gcd(a,b)=1,$$

altså hvis de ikke har noen felles primfaktor. Legg merke til at ingen av dem behøver å være primtall: $8$ og $9$ er relativt primiske, selv om begge er sammensatte.

Uttrykket parvis relativt primiske brukes om tre eller flere tall, og betyr at hvert par er relativt primisk. Det er strengere enn at ikke alle tre har en felles faktor: tallene $6$, $10$ og $15$ har ingen felles faktor for alle tre, men er ikke parvis relativt primiske, siden $\gcd(6,10)=2$.

Skillet er eksamensviktig. Det kinesiske restteoremet (kap. 2.4, 12 av 15 sett) krever at modulene er parvis relativt primiske, og fasitene i arkivet påpeker det eksplisitt. Å bruke formelen uten å sjekke er en av de best belagte feilene.

Der ellers vilkåret dukker opp: $\gcd(a,n)=1$ er kravet for at $a$ har en invers modulo $n$ (kap. 1.4), for at Eulers teorem gjelder (kap. 2.1), og for at $\phi$ er multiplikativ.

Med $a=\prod p_i^{k_i}$ og $b=\prod p_i^{l_i}$ (der eksponenten er $0$ for primtall som mangler):

$$\gcd(a,b)=\prod_i p_i^{\min(k_i,\,l_i)}.$$

Dette må sitte utenat. Intuisjonen: en felles divisor kan ikke bruke flere kopier av $p_i$ enn det knappeste av de to tallene har.

Men merk begrensningen. Metoden krever at du kan faktorisere. På eksamen er tallene i sjanger A og B typisk fire- og femsifrede, og faktorisering med prøvedivisjon tar da for lang tid. Derfor er Euklids algoritme (kap. 1.2) og ikke denne metoden hovedverktøyet — og derfor er dette kortet et forståelseskort, mens Euklid er et ferdighetskort.

$$\operatorname{lcm}(a,b)=\prod_i p_i^{\max(k_i,\,l_i)}.$$

Dette må sitte utenat. Intuisjonen: et felles multiplum må ha nok kopier av $p_i$ til å dekke det mest krevende av de to tallene.

Minnekroken for begge kortene: $\gcd$ tar minst, $\operatorname{lcm}$ tar mest. Og siden $\min(k,l)+\max(k,l)=k+l$ for hvert primtall, følger produktregelen i neste kort umiddelbart.

$$\gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab.$$

Dette må sitte utenat, og det er den billigste tidsbesparelsen i kapitlet: har du regnet ut $\gcd$ — for eksempel med Euklids algoritme, som er rask — får du $\operatorname{lcm}$ gratis ved én divisjon:
$$\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}.$$

Utledningen utledes på stedet, i én linje: for hvert primtall $p_i$ er summen av eksponentene på venstresiden $\min(k_i,l_i)+\max(k_i,l_i)=k_i+l_i$, som er nøyaktig eksponenten i $ab$. Siden faktoriseringene er entydige etter aritmetikkens fundamentalteorem, er de to sidene like.

Bruk den også som kontroll: har du regnet ut både $\gcd$ og $\operatorname{lcm}$ på hver sin måte, skal produktet bli $ab$. Stemmer det ikke, er én av dem gal.

For å vise at en påstand $P$ er sann:

1. Anta at $P$ er gal. Skriv antagelsen eksplisitt ned som egen linje — det er her de fleste bevis mister leseren.
2. Regn videre på den antagelsen, med vanlige gyldige skritt.
3. Kom fram til noe umulig — en påstand som strider mot antagelsen eller mot et kjent resultat.
4. Avslutt med en klar umulighetssetning: «men da er $q$ både et primtall og sammensatt — motsigelse». Derfor var antagelsen gal, og $P$ er sann.

Malen må sitte utenat, og punkt 4 er den som gir uttelling. Et motsigelsesbevis som «renner ut» uten å si hva som er umulig, er ufullstendig — leseren skal ikke måtte finne motsigelsen selv.

Malen brukes gjennom hele boka: her på primtallenes uendelighet, senere på irrasjonalitet (kap. 7.3) og på uløselige kongruenssystemer (kap. 2.4).

$$N=p_1p_2\cdots p_k+1.$$

Egenskapen som gjør det nyttig: ingen av primtallene i listen deler $N$. Grunnen er at hver $p_i$ deler produktet, så deler den også $N$, ville den delt differansen $N-p_1\cdots p_k=1$ — etter lineærkombinasjonsregelen. Men ingen primtall deler $1$.

$N$ er altså et tall som er «immun» mot hele listen din. Det er hele motoren i beviset under, og i alle varianter av det.

Merk at $N$ ikke behøver å være et primtall selv. For listen $2,3,5,7,11,13$ er $N=30\,031=59\cdot 509$ — sammensatt. Beviset trenger ikke at $N$ er prim, bare at $N$ har en primdivisor som ikke står i listen.

Med divisjonsalgoritmen på $b=2$: hvert helt tall er $n=2q$ (like) eller $n=2q+1$ (odde). Det er ikke mer å velge mellom, og det er derfor paritetsargumenter er så effektive — de deler alle tall i nøyaktig to grupper.

Tre fakta som brukes gjennom boka: like + like = like, odde + odde = like, like $\cdot$ hva som helst = like. Og: $2$ er det eneste like primtallet, siden alle andre like tall har $2$ som ekte divisor.

Paritet er også det enkleste tilfellet av case-analyse modulo $m$ (§ kap. 6.1) — det er case-analyse med $m=2$. Og den dukker opp som en av de tre betingelsene i den pytagoreiske parametriseringen i kap. 7.2, der $s$ og $t$ må ha ulik paritet.

Et tall på formen $p^k$, der $p$ er et primtall og $k\ge 1$, kalles en primtallspotens. Eksempler: $8=2^3$, $27=3^3$, $49=7^2$, og et primtall $p=p^1$ er selv en primtallspotens.

Divisorene i $p^k$ er nøyaktig $1,p,p^2,\dots,p^k$ — altså $k+1$ stykker, og ikke flere, etter aritmetikkens fundamentalteorem.

Primtallspotensene er byggeklossene i alle de multiplikative formlene senere i boka: $\phi(p^k)=p^k-p^{k-1}$ (kap. 2.1), $\tau(p^k)=k+1$ og $\sigma(p^k)=1+p+\dots+p^k$ (kap. 5.3). Fremgangsmåten er alltid den samme: regn ut formelen for en primtallspotens, og bruk deretter multiplikativiteten for å sette sammen svaret for et generelt $n$.

Et positivt helt tall er kvadratfritt hvis ingen eksponent i primtallsfaktoriseringen er større enn $1$ — altså hvis ingen primtallskvadrat deler det.

$30=2\cdot 3\cdot 5$ er kvadratfritt. $12=2^2\cdot 3$ er ikke, siden $4\mid 12$.

Begrepet er nyttig som språk: «$n$ er kvadratfritt» er en kort måte å si at alle primfaktorer forekommer bare én gang. Det kommer igjen i kap. 5.3, der kvadratfrie tall er nøyaktig de tallene der divisorantallet er en ren potens av $2$ ($\tau(n)=2^r$ for $r$ primfaktorer).

$$n=\prod p_i^{k_i}\ \text{er et kvadrattall}\iff \text{alle }k_i\text{ er like.}$$

Eksempel: $1764=2^2\cdot 3^2\cdot 7^2=(2\cdot 3\cdot 7)^2=42^2$. Motsatt er $1176=2^3\cdot 3\cdot 7^2$ ikke et kvadrattall, siden eksponentene $3$ og $1$ er odde.

Utledes på stedet (og utledningen står i oppgave 9): den ene retningen ved å halvere eksponentene, den andre ved å kvadrere faktoriseringen til $m$ og bruke entydigheten.

Resultatet er mer nyttig enn det ser ut. Det er nøkkelen til at $\tau(n)$ er odde nøyaktig når $n$ er et kvadrattall (kap. 5.3), og det er skrittet som bærer irrasjonalitetsbevisene i kap. 7.3.

En felles divisor i $a$ og $b$ er et tall som deler begge. Et felles multiplum er et tall som begge deler.

Strukturen bak de to begrepene er verdt å legge merke til, for den forklarer hvorfor ordene «største» og «minste» kan brukes:

- Mengden av felles divisorer er endelig (ingen divisor i $a$ er større enn $|a|$), så det finnes en største. Det er $\gcd(a,b)$.
- Mengden av positive felles multipler er uendelig, men har et minste element. Det er $\operatorname{lcm}(a,b)$.

Og et resultat som er sterkere enn navnet antyder: hver felles divisor deler $\gcd(a,b)$, og hvert felles multiplum er delelig med $\operatorname{lcm}(a,b)$. $\gcd$ er altså ikke bare den største — den er den som alle de andre går opp i. Det er den formen egenskapen har når den brukes i bevis.

Fasitene i arkivet bruker en fast notasjon, og boka følger den. Det lønner seg å skrive slik selv, fordi det gjør besvarelsen lesbar for den som retter.