Page 1 of 1

Tallteori, største felles divisor (oppgave)

Posted: 24/09-2014 14:12
by Gjest12321
Har en oppgave jeg har prøvd lenge på nå uten noen særlig følelse av fremgang. Oppgaven lyder som følger:

La l, m, og n være heltall. La d være et naturlig tall slik at sfd(l, n) = d.
Anta at n | m. Bevis at sfd(l + m, n) = d. Tips: Benytt ligningen l = (l + m) − m i løpet
av beviset ditt.
Aner ikke hvor jeg skal benytte at l = (l + m) - m. Har prøvd å bruke at lx + ny = sfd(l, n) og sfd(l + m, n) = kd uten særlig hell.

Takk for all hjelp, om mulig ønsker jeg bare et godt hint slik at jeg kan komme i gang.

Re: Tallteori, største felles divisor (oppgave)

Posted: 24/09-2014 14:34
by Brahmagupta
Siden $n|m$ kan du skrive $m=nk$. La nå $d=sfd(l,n)$ og $d'=sfd(l+nk,n)$. Om du kan vise at $d|d'$ og at $d'|d$
er du i mål.

Re: Tallteori, største felles divisor (oppgave)

Posted: 24/09-2014 14:59
by Gjest12324
Så langt har jeg kommet. Problemet er at jeg mangler et eller annet fundamentalt, ellers så har jeg en mental sperre som gjør at jeg overser noe..

Re: Tallteori, største felles divisor (oppgave)

Posted: 24/09-2014 15:32
by Brahmagupta
Jeg kan vise den ene retningen, at $d|d'$. Per definisjon er $d=sfd(l,n)$ som vil si at $d|l$ og $d|n$. Da vil også $d$
dele enhver lineær kombinasjon av $l$ og $n$. Spesielt $d|l+kn$ som medfører at $d|sfd(l+nk,n)=d'$.

Det viktigste å merke seg er at hvis et tall $d_0$ deler både $p$ og $q$ så må det nødvendigvis være slik at
$d_0$ deler $sfd(p,q)$ siden dette per definisjon er det største tallet som har denne egenskapen.