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