Matematik

Euklids algoritme

11. september 2016 af sejereje91 - Niveau: Universitet/Videregående

Hej,
jeg har vedhæftet opgaven som jeg har problemer med.
Det drejer sig om (ii) og (iii). Jeg kan ikke helt gennemskue hvordan jeg skal lave 2'eren da jeg normalt kan gøre det med x og y men ikke x0 og y0. I 3'eren forvirrer det mig at jeg skal vise at r tilhører M. For ellers ville jeg jo bare sige at de to udtryk er ens, blot forskellige bogstaver der er isoleret.

Håber I kan hjælpe.

Vedhæftet fil: 1473592587533535621399.jpg

Brugbart svar (0)

Svar #1
11. september 2016 af peter lind

Brugbart svar (1)

Svar #2
11. september 2016 af peter lind

ii) sfd(a,b) er devisor i både a og b og går derfor op i både ax₀ og by₀ og dermed også i deres sum

iii) r = a-qm

både a og b går jo op i m ifølge ii) derfor kan m skrives m= x₀*a+y₀b,l. Heraf kan du se at r er en linearkombination af a og b

Svar #3
11. september 2016 af sejereje91

Hej Peter,
Mange tak for svar!
Kan du hjælpe med (iv) også? Jeg kan ikke gennemskue hvilke ligninger jeg skal indsætte i hvilke for at få r=0

Brugbart svar (1)

Svar #4
11. september 2016 af peter lind

r∈M er enten 0 eller et naturligt tal, der er mindre end m. m er det mindste naturlige tal i M så r må være 0

Svar #5
11. september 2016 af sejereje91

Tak, gennemskuede den også lige! :-).
I 5'eren skal jeg vise at m|a. Jeg har tænkt at det kan skrives som a=q*m. Og indsætte det på a's plads i m formlen. Men er det bevis nok? Og gøre det samme for b når der i næste opgave står: vis at m|b ?

Brugbart svar (1)

Svar #6
11. september 2016 af peter lind

Du kan jo bare konstaterer at ifølge iii) og iv) er a = q*m hvilket er bevis for at m går op i a

Svar #7
11. september 2016 af sejereje91

Ja, men kan jo ikke lave samme konklusion mht m går op i b :-)

Brugbart svar (0)

Svar #8
11. september 2016 af peter lind

jo. Problemet er jo helt identisk for a og b, så du kan forklare det ved at foretage en bogstavombytning. Matematiske problemer er ikke af hvad man kalder de forskellige størrelser

Brugbart svar (1)

Svar #9
11. september 2016 af VandalS

En lille rettelse til iii): Delopgave ii) siger at sfd(a,b)|m , hvilket ikke medfører at og gør det.

Resten af argumentet er fint hvis der i stedet bruges at $m=a \cdot x_0+ b \cdot y_0$ er en definition, så $r= a- q\cdot m = a - q\cdot (a \cdot x_0+ b \cdot y_0)=a\cdot (1-q\cdot x_0) + b\cdot q \cdot y_0$ , hvilket stemmer overens med formen på tal i da , x_0 og y_0 er hele tal.

Svar #10
11. september 2016 af sejereje91

Så når jeg fx m|a får:
A=q*m
Indsætter i m:
m= ax0+by0 = q*mx0+by0, så kan jeg godt sige at på den måde går m op i a og tilsvarende for b ved samme metode?

Brugbart svar (0)

Svar #11
11. september 2016 af VandalS

#10

Du har vist at $a=q \cdot m$ , og da alle tallene er hele tal viser dette direkte at går op i ( gange). Du kan få en tilsvarende konklusion for hvis du gentager delopgaverne iii), iv) og v) med start i $b=p\cdot m + r_2$ .

Brugbart svar (0)

Svar #12
18. september 2016 af 9003n

Hej,

Jeg har problemer med delopgave i). Jeg ved ikke helt, hvordan jeg skal redegøre for, at M indeholder mindst et naturligt tal? Er det bare at sige, at M har mindst et naturligt tal,

hvis fortegene for x,y er det samme som a,b (x,y>0 og a,b>0)

da b≠0

og da m>0.

Jeg har problemer med, hvordan det skal formuleres. Nogen der kan hjælpe?:)

tak på forhånd

Svar #13
18. september 2016 af sejereje91

Da a, b, x og y er hele tal er ax+by også et helt tal.
X og y vælges altså så ax+by er større end 0. Vælges a=x og b=y får du
Ax+by =a*a+b*b og da b ikke er 0, vil b*b blive større end 0.

Brugbart svar (0)

Svar #14
18. september 2016 af 9003n

aha, nu kan jeg se meningen i det. tak!

Skriv et svar til: Euklids algoritme

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.