$\gcd(0, 0)$

[Aleks855]

I tallteorien er ideen om "største felles divisor" eller $\gcd$ ganske sentral. Boka jeg leser nevner i en bisetning at $\gcd(0, 0) = 0$ uten forklaring.

Hvordan defineres dette?

Jeg har googlet frem og tilbake, men alle forklaringer inkluderer begrepet "partial order of divisibility on the natural numbers", og forklarer at ordet "største" i denne sammenhengen ikke beskriver størrelsen med hensyn på rekkefølgen av naturlige tall, som man vanligvis forbinder det med.

Kan noen utdype hva dette betyr, og hvorfor vi får resultatet $\gcd(0, 0) = 0$?

[stensrud]

I tallteorien er ideen om "største felles divisor" eller $\gcd$ ganske sentral. Boka jeg leser nevner i en bisetning at $\gcd(0, 0) = 0$ uten forklaring.

Hvordan defineres dette?

Jeg har googlet frem og tilbake, men alle forklaringer inkluderer begrepet "partial order of divisibility on the natural numbers", og forklarer at ordet "største" i denne sammenhengen ikke beskriver størrelsen med hensyn på rekkefølgen av naturlige tall, som man vanligvis forbinder det med.

Kan noen utdype hva dette betyr, og hvorfor vi får resultatet $\gcd(0, 0) = 0$?

Sånn jeg ser det så er grunnen til problemene at $0$ oppfører seg litt rart når det kommer til delelighet. Den vanligste definisjonen for to heltall er at deres gcd er det største heltallet som deler begge tallene. Dette funker fint for alle par av tall hvor ikke begge er null, men hvis begge er null så vil ethvert naturlig tall dele $0$, så $\gcd{0,0}$ kan ikke defineres på denne måten.

Nå vet jeg ikke hvor mye du har lært om partielle ordninger, men her er en kort forklaring: Når vi snakker om delelighet, så er $0$ det "største" naturlige tallet, fordi det er det mest "delelige" tallet. Mer presist: Delelighet har den fine egenskapen at hvis $a\mid b$ og $b\mid c$, så vil $a\mid c$, liksom $a\leq b$ og $b\leq c$ impliserer $a\leq c$. På denne måten oppfører $\mid$ seg veldig likt som $\leq$, med den åpenbare forskjellen at ikke alle tall kan relateres ved hjelp av $\mid$, noe de kan med $\leq$ (vi kan hverken si $3\mid 5$ eller $5\mid 3$, men vi vet at $3\leq 5$...). Med $\leq$ så kan vi ordne alle elementene i $\mathbb{N}_0=\{0,1,2,3,\dotsc\}$ slik:
\[ 0\leq 1\leq 2\leq 3 \leq \dotsb \]
Men vi kan jo også prøve å ordne de ved hjelp av $\mid$, selv om vi ikke kan lage en rekke med alle elementene, slik som vi gjorde med $\leq$. For eksempel så har vi
\[ 1\mid 2\mid 4\mid 8\mid\dots, \]
hvor $1$ er "minst" og tallene blir "større" mot høyre. Grunnen til at jeg skriver "minst" og "større" er at selv om tallene i de fleste tilfeller vokser i størrelse mot høyre, så har vi kjeder som
\[ 1\mid 2\mid 4\mid 8\mid\dots\mid 0, \]
hvor dette ikke lenger er tilfellet. Her er $0$ det "største" elementet, og siden alle heltall deler $0$, så vil vi kunne legge på $0$ som et siste element på alle slike delelighetskjeder, slik som i
\[ 1!\mid 2!\mid 3!\mid\dots\mid 0. \]
Det er dette som menes med at $0$ er "størst" når vi snakker om delelighet. Dette kan gjøres mer formelt med partielle ordninger, men idéen er den samme. Og da kan det hende at definisjonen av gcd over gir litt mer mening, fordi $0$ kan sees på som det største tallet når vi kun er interesserte i delelighet.


Et annet poeng er at hvis vi har en definisjon for de fleste tilfellene av noe, og ønsker og utvide den til alle tilfeller, så vil vi gjerne at definisjonen skal bevare noen egenskaper ved det som allerede er definert. For eksempel så er $\gcd(a,0)=a$ for alle $a\neq 0$, og det vil da være naturlig å definere $\gcd(0,0)=0$ for å beholde denne egenskapen ved gcd. En annen egenskap er at $\gcd(a,b)$ er det minste positive heltallet $d$ som kan skrives på formen $ax+by$ hvor $x$ og $y$ er heltall, og skal vi utvide dette til å gjelde for $a=b=0$, så virker det naturlig å bruke $d=0$.


Det går også an å bruke mer avanserte metoder som ringteori til å definere gcd, men det enkleste er vel bare å tenke på det som en høyeste felles faktor (hcf), der hvor $0$ er den største faktoren av alle.

[Gustav]

Tanken er å definere en partiell ordning $\leq$ på de ikkenegative heltallene $\mathbb{N}_0$ slik at $gcd(0,0)$ blir veldefinert.

La $n\leq m\Leftrightarrow n|m\Leftrightarrow \exists k\in \mathbb{N}_0$ slik at $m=kn$. Med denne ordningen vil $n\leq 0$ for alle $n$, siden $0=0\cdot n$, så $0$ er det "største" elementet i $\mathbb{N}_0$ med hensyn på delelighetsordningen. Siden $0|0$ og $0$ er det største elementet i $\mathbb{N}_0$, er $gcd(0,0)=0$.

edit

[Aleks855]

Men vi kan jo også prøve å ordne de ved hjelp av $\mid$, selv om vi ikke kan lage en rekke med alle elementene, slik som vi gjorde med $\leq$. For eksempel så har vi
\[ 1\mid 2\mid 4\mid 8\mid\dots, \]
hvor $1$ er "minst" og tallene blir "større" mot høyre. Grunnen til at jeg skriver "minst" og "større" er at selv om tallene i de fleste tilfeller vokser i størrelse mot høyre, så har vi kjeder som
\[ 1\mid 2\mid 4\mid 8\mid\dots\mid 0, \]
hvor dette ikke lenger er tilfellet. Her er $0$ det "største" elementet, og siden alle heltall deler $0$, så vil vi kunne legge på $0$ som et siste element på alle slike delelighetskjeder, slik som i
\[ 1!\mid 2!\mid 3!\mid\dots\mid 0. \]
Det er dette som menes med at $0$ er "størst" når vi snakker om delelighet. Dette kan gjøres mer formelt med partielle ordninger, men idéen er den samme. Og da kan det hende at definisjonen av gcd over gir litt mer mening, fordi $0$ kan sees på som det største tallet når vi kun er interesserte i delelighet.

La meg se om jeg har forstått dette riktig. Hvis vi hadde snakket som $\mathbb N_0$ i stedet for $\mathbb N$ når vi generelt betrakter delelighet, primtall og denslags, så hadde vi alltid fått resultatet $\gcd(a, b) = 0$ for heltallige $a, b$?

For vi kan jo alltid legge på $0$ på slutten av en partiell ordning under $\mid$ og få at $0$ er "størst"?

[stensrud]

Hvis vi hadde snakket som $\mathbb N_0$ i stedet for $\mathbb N$ når vi generelt betrakter delelighet, primtall og denslags, så hadde vi alltid fått resultatet $\gcd(a, b) = 0$ for heltallige $a, b$?

For vi kan jo alltid legge på $0$ på slutten av en partiell ordning under $\mid$ og få at $0$ er "størst"?

Det er riktig at $0$ er det maksimale elementet med denne partielle ordningen, men det impliserer ikke at $\gcd(a,b)=0$ for alle $a,b$. $0$ deler generelt ikke heltall, så hvis vi bruker definisjonen som sier at $\gcd(a,b)$ er det største tallet som deler både $a$ og $b$, så kan ikke $\gcd(a,b)=0$ siden $0$ ikke deler begge.

[Aleks855]

Er dette da en "justering" av hvordan vi definerer $\gcd$ for tilfellet $0,0$? For $0$ deler jo heller ikke $0$.

[stensrud]

Er dette da en "justering" av hvordan vi definerer $\gcd$ for tilfellet $0,0$? For $0$ deler jo heller ikke $0$.

Den vanligste definisjonen av delelighet er at $a\mid b$ hvis det finnes et heltall $n$ slik at $b=an$, og da vil $0\mid 0$. (Selv om vi ikke kan dele $0$ på $0$!)

[Aleks855]

Ah, da faller det litt mer på plass.

Jeg hengte meg for langt opp i at delelighet skal medføre at vi faktisk kan dele det ene tallet på det andre.

Takk for forklaringa, og for oppfølger-svarene!