Tallteori, største felles divisor (oppgave)

[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.

[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.

[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..

[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.