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

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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)$?
Bilde
stensrud
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

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
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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?
Bilde
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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)$?
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Gustav skrev: 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. :lol:

Ser det rimelig ut?
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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!
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Aleks855 skrev: 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
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Sted: Cambridge

Aleks855 skrev: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.
Svar