Talteori

Er der ingen som vil være sød at hjælpe mig?

Du har allerede en tråd, iøvrigt med fuldstændigt identiske indlæg som i denne. Det må du se at vænne dig af med. Hvis ingen svarer, kunne det jo tænkes, du ikke har formuleret dine spørgsmål særligt godt, og at en uddybning var på sin plads.

Hvis a og b er heltal siges de at være indbyrdes primiske hvis gcd(a,b)=1.

Denne her kryptiske sag:

"Jeg mangler at bevise
gcd(a,b)= gcd(b,r)
a = b*x +r "

er rent volapyk. Det er sikkert derfor, ingen har gidet/kunnet svare.

Clout'et til at gætte hvad du mener er Euklids algoritme. Det interessante må derfor være at vise sætningen:

SÆTNING:
Lad a>b,q,r være heltal så a=bq+r. Så er gcd(a,b)=gcd(b,r)

for det er netop dette faktum, der giver algoritmeskridtet. Det er meget let at vise, men jeg vil gøre det ret detaljeret, dog med risiko for at det forvirrer mere end det gavner.

Først skal vi bruge en hjælpesætning i form a følgende

LEMMA 1:
Hvis d er fælles divisor i a,b, så er d divisor i r.

BEVIS:
Da d er divisor i a og b findes heltal x og y så a=dx og b=dy. Så er

r = a-qb = dx-qdy = (x-qy)d (*)

Da q,x,y alle er heltal er x-qy ligeså. Derfor viser (*) at d er divisor i r.

Dernæst tager vi hjælpesætningen i anvendelse idet vi viser det du ønsker.

BEVIS:
Da gcd(a,b) er divisor i a og b følger af lemmaet, at gcd(a,b) tillige er divisor i r.

Da gcd(b,r) er divisor i b og r, er gcd(b,r) også divisor i qb+r = a.

Altså er både gcd(a,b) og gcd(b,r) divisorer i a,b,r.

Vi mangler at vise lighedstegnet.

Antag gcd(a,b) > gcd(b,r). Men så er gcd(b,r) ikke den største fælles divisor af b og r hvilket er en modstrid [overvej].

Antag gcd(a,b) < gcd(b,r). Men så er gcd(a,b) ikke den største fælles divisor af a og b hvilket er en modstrid [overvej].

Altså er gcd(a,b) = gcd(b,r)

----

I en fremstilling af aritmetik vil beviset for sætningen sikkert blot refereres til som triviel eller begrænse sig til en enkelt linie eller to. Jeg håber du får lidt ekstra udbytte af den ekstreme udpensling.