Lcm og gcd

[Karl_Erik]

Jeg er litt usikker på om denne har vært oppe her før, men klarer ikke å finne den om så er tilfellet. Uansett: La [tex]a[/tex] og [tex]b[/tex] være to positive heltall slik at [tex]lcm(a,b) + \gcd(a,b) = a+b[/tex]. Vis at en av [tex]a, b[/tex] deler den andre.

[Nebuchadnezzar]

Prøver meg jeg, helt sikkert at dette er feil...

La oss anta at [tex]a>b[/tex] om [tex]a=b[/tex] så blir dette beviset trivielt siden [tex]\frac{a}{a}=1[/tex]
Om [tex]a[/tex] deler [tex]b[/tex] kan vi skrive at [tex]bm=a[/tex]

[tex]lcm(bm,b)=bm[/tex] og [tex]gcd(bm,b)=b[/tex]

[tex]lcm(a,b)+gcd(a,b)=a+b[/tex]

[tex]lcm(bm,b)+gcd(bm,b)=bm+b[/tex]

[tex]bm+b=bm+b[/tex]

Derfor deler [tex]a,b[/tex] når [tex]lcm(a,b)+gcd(a,b)=a+b[/tex]

[Karl_Erik]

Dette blir nok litt feil, ja. Du antar først at [tex]b[/tex] deler [tex]a[/tex], og viser at dette 'passer' i likningen, altså at om vi har delelighet er likningen oppfylt. Det følger dessverre ikke av dette at om likningen er oppfylt har vi delelighet. Hvis du vil ha et hint legger jeg det nederst i ROT-13. (www.rot13.com)

Hint (ROT-13): Cebqhxgrg ni ypz(n,o) bt tpq(n,o) re yvx no.

[BMB]

Anta [tex]a \geq b[/tex]. Av den oppgitte likheten får vi [tex]\gcd(a,b) \equiv b \pmod a[/tex]. Siden både [tex]\gcd(a,b)[/tex] og [tex]b[/tex] er positive og mindre enn eller lik [tex]a[/tex], følger det at [tex]\gcd(a,b)=b[/tex], så [tex]b|a[/tex].

[Karl_Erik]

Fin løsning. Kortere og mer elegant enn min, som går ut på å faktorisere likningen til [tex](a-g)(b-g)=0[/tex].