matematikk.net

Hm.....

a) Finn ved hjelp av Euklids algoritme d=(a,b) når a=591 og b=759.

b) Vis ved hjelp av Euklids algoritme at største felles divisor for 21, 252 og 32 er lik 1.

c) La a, b og d være som i pkt. a). Finn hele tall p og q slik at pa+qb=d.

Nina

Euklids algoritme er ganske rett fram. Siden du har oppgaver med den regner jeg med at du også har et eksempel på hvordan du bruker den. Slik løser du i hvertfall a):

759 = 1*591 + 168
591 = 3*168 + 87
168 = 1*87 + 81
87 = 1*81 + 6
81 = 13*6 + 3
6 = 2*3 + 0

Når du får 0 som rest er du ferdig. Da er d(a,b) gitt ved den siste resten som ikke er 0, altså 3.

På b) finner du sfd for hvert par av tallene. Dersom en av disse er 1 så er du ferdig. Ellers må du sammenligne alle disse sfd-ene.

oppg c) kan løses ut fra løsning på a)

Du skriver om alle linjene med restene alene på høyre side slik:
759 - 1*591 = 168
...
87 - 1*81 = 6
81 - 13*6 = 3

Så setter du den nest nederste ligningen inn for 6 tallet i den nederste slik:

81 - 13*(87 - 1*81) = 15*81 - 13*87 = 3

Deretter nøster du deg oppover, altså setter den neste ligningen inn for 81, den neste inn for 87 osv....

ok?