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

[Aleks855]

Har litt problemer med å bevise denne påstanden.

Min tankerekke hittil er å betrakte at hvis vi har en divisor $d$ slik at
$$d\mid a \ \ \wedge \ \ d \mid b$$ $$\Rightarrow \ \ a = dc_1 \ \ \wedge \ \ b = dc_2$$ $$\Rightarrow d \mid b-a = d(c_2-c_1) $$

Her stopper det. Et hint jeg fikk var å se på dette, og konkludere at $\gcd(a, b) \leq \gcd(a, b-a)$, siden kandidater for førstnevnte er mindre en mengden av sistnevnte.

Men er ikke det motsatte riktig? For eksempel for heltallige $a, b$ vil jo $b > b-a$ og må ikke da $\gcd(a, b) \geq \gcd(a, b-a)$?

[stensrud offline]

Strategien er altså å vise $\gcd(a,b-a)\leq\gcd(a,b)\leq \gcd(a,b-a)$, som er nok. Vi starter med ulikheten til høyre slik du gjorde: Hvis $d$ deler både $a=xd$ og $b=yd$ så vil $d$ også dele $b-a=d(y-x)$ som følge av definisjonen av delelighet. Da vil $d$ også dele $\gcd(a,b-a)$, så hver kandidat $d$ for $\gcd(a,b)$ er også en kandidat for $\gcd(a,b-a)$, som impliserer $\gcd(a,b)\leq \gcd(a,b-a)$.

Den andre ulikheten viser vi helt likt: Hvis $d\mid a=xd$ og $d\mid b-a=zd$, så vil $d$ også dele $b=(x+z)d$, og argumentet går som over. $\square$

[Aleks855]

Sikkert noe grunnleggende jeg overser, men gitt at $d \mid b-a$, konkluderer du at $d \mid \gcd(a, b-a)$?

Jeg ser at $d$ er blant kandidatene for $\gcd$, men hvis den ikke er det, må den nødvendigvis dele den?

[Aleks855]

Ok, vent. Lærte akkurat at $\gcd(a, b)$ kan skrives som en heltalls lineærkombinasjon av $a, b$. Og hvis $d$ deler både $a$ og $b$ så må det nødvendigvis også dele lineærkombinasjoner av disse.

Er det slik man kan argumentere for at $d \mid \gcd(a, b)$?

[Gustav]

Hvis $d|a$ og $d|b$ så vil ("selvsagt") $d|gcd(a,b)$ (fra Bézout's identitet). Det er det eneste stensrud har brukt.

Edit:
Du kan jo også unngå å bruke Bezout ved å argumentere slik:

For $gcd(a,b)\leq gcd(a,b-a)$:

La $d=gcd(a,b)$. Da vil $d|a$ og $d|b$, og følgelig $d|b-a$, så $d$ er en felles divisor for $a$ og $b-a$. Da er det åpenbart at $d\leq gcd(a,b-a)$: Bevis ved motsigelse: Anta $d>gcd(a,b-a)$, som er en motsigelse siden $d$ er en felles divisor.

[Aleks855]

La $d=gcd(a,b)$. Da vil $d|a$ og $d|b$, og følgelig $d|b-a$, så $d$ er en felles divisor for $a$ og $b-a$. Da er det åpenbart at $d\leq gcd(a,b-a)$: Bevis ved motsigelse: Anta $d>gcd(a,b-a)$, som er en motsigelse siden $d$ er en felles divisor.

Ah, og på samme mynt, så kan beviset gjenbrukes ved å innføre $b \to b-a$?

La $d=gcd(a,b-a)$. Da vil $d|a$ og $d|b-a$, og følgelig $d|b$, så $d$ er en felles divisor for $a$ og $b$. Da er det åpenbart at $d\leq gcd(a,b)$: Bevis ved motsigelse: Anta $d>gcd(a,b)$, som er en motsigelse siden $d$ er en felles divisor.

Dermed er likhet bevist. Fremgangsmåten for å vise at $d\mid a \wedge d\mid b-a \Rightarrow d\mid b$ er implisitt, men littegrann annerledes. Dog, Stensrud viste det ovenfor.

Innser nå at jeg repeterer stensruds første innlegg, men det var først nå jeg skjønte hele greia.

Ser det rimelig ut?

[Gustav]

Ja, det ser riktig ut!

Forskjellen på dette og stensrud sitt bevis (som er vel så bra som mitt) er bare at vi her betrakter den største felles divisoren, istedenfor en vilkårlig felles divisor. Fordelen med det er at vi da slipper å vise følgende: Hvis d|a og d|b så vil $d|gcd(a,b)$,

(Det er jo åpenbart at gcd(a,b) deler både a og b da gcd(a,b) per definisjon er en felles divisor av a og b. )

[Aleks855]

Jeg det funka.

Jeg må nok likevel se nærmere på påstanden om at "enhver felles divisor nødvendigvis må dele den største felles divisoren". Da kommer vel Bézout inn i bildet igjen.

Takk for veiledninga, begge to!

[Gustav]

Jeg må nok likevel se nærmere på påstanden om at "enhver felles divisor nødvendigvis må dele den største felles divisoren". Da kommer vel Bézout inn i bildet igjen.

Ja, for alle heltall $a,b$ så eksisterer det, av Bezout, to heltall $n,m$ slik at $an+bm=gcd(a,b)$. Hvis $d|a$ og $d|b$ så kan vi skrive $a=dk$ og $b=dl$ der $k,l$ er heltall. Dermed blir $an+bm=dkn+dlm=d(kn+lm)=gcd(a,b)$, ergo vil $d|gcd(a,b)$.

Bevis av Bezouts lemma er ikke helt trivielt, som du ser her https://proofwiki.org/wiki/B%C3%A9zout%27s_Lemma

[stensrud offline]

Jeg det funka.

Jeg må nok likevel se nærmere på påstanden om at "enhver felles divisor nødvendigvis må dele den største felles divisoren". Da kommer vel Bézout inn i bildet igjen.

Takk for veiledninga, begge to!

Forresten kan du jo se på om vi trenger entydig primtallsfaktorisering for at beviset skal fungere. Jeg har ikke dobbeltsjekka nå, men jeg tror jeg brukte det en gang i beviset over, og jeg er ganske sikker på at vi egentlig ikke trenger det. (Som regel så er det ikke særlig greit å anta entydig primtallsfaktorisering når vi skal bevise elementære (men ikke nødvendigvis enkle) resultater slik som dette)

Hvis vi skal bruke Bezout i beviset så kan vi bruke det mer eller mindre direkte: Enhver lineærkombinasjon av $a,b$ er også en lineærkombinasjon av $a$ og $b-a$, og motsatt, siden $ax+by=a(x+y)+(b-a)y$. Gcd er det minste positive heltallet som kan skrives som en lineær kombinasjon av de to tallene (bortsett fra $\gcd(0,0)=0$), så dette er nok.