$\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.

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

Innlegg Aleks855 » 14/12-2017 20:43

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
Aleks855 online
Rasch
Rasch
Innlegg: 5767
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg stensrud » 14/12-2017 23:08

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$
stensrud offline
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Bosted: Cambridge

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

Innlegg Aleks855 » 14/12-2017 23:38

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 online
Rasch
Rasch
Innlegg: 5767
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg Aleks855 » 15/12-2017 00:05

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
Aleks855 online
Rasch
Rasch
Innlegg: 5767
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg Gustav » 15/12-2017 00:43

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.
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4269
Registrert: 12/12-2008 12:44

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

Innlegg Aleks855 » 15/12-2017 15:55

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
Aleks855 online
Rasch
Rasch
Innlegg: 5767
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg Gustav » 15/12-2017 16:20

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. )
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4269
Registrert: 12/12-2008 12:44

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

Innlegg Aleks855 » 15/12-2017 17:18

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
Aleks855 online
Rasch
Rasch
Innlegg: 5767
Registrert: 19/03-2011 15:19
Bosted: Trondheim

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

Innlegg Gustav » 15/12-2017 19:23

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
Gustav offline
Tyrann
Tyrann
Brukerens avatar
Innlegg: 4269
Registrert: 12/12-2008 12:44

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

Innlegg stensrud » 16/12-2017 00:04

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.
stensrud offline
Descartes
Descartes
Innlegg: 438
Registrert: 08/11-2014 21:13
Bosted: Cambridge

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 4 gjester