løsning af 61=9x+15y?

Hvis du vil bruge Euklids algoritme må du enten bruge et CAS værktøj eller sætte  dig ind i algoritmen.

En anden måde er at prøve sig frem.  Jeg er ikke sikker på hvad den første af ligningerne er, så jeg holder mig til den sidste  Vælg en af koefficienterne for eks. 16. Træk 16 fra og se om 9 går op i facit. Gør den ikke det trækker du yderligere 16 fra og ser efter om 9 går op, Gør den ikke trækker du yderlig 16 fra  o.s.v. Når 9 går op har du et y som passer. Derefter er det nemt at finde et x som passer eller du kan bare bruge det sidste forsøg

Jeg må desværre ikke prøve mig frem. Så jeg skal have sat mig ind i algoritmen, men håbede lidt at der var en der måske kunne forklare den på en anden måde end bøgerne. For har lidt svært ved at se hvordan man finder x og y i den. Der er jo de der skemaer hvor man indsætter q_k, r_k, x_k og y_k. Kan sagtens finde ud af at bestemme q og r. Men ved ikke hvordan jeg skal bestemme x og y.

q og r er formentlig x og y eller y og x.

Nej desværre. :-)

Der kan ses et skema på side 3 her: http://imfufa.ruc.dk/~am/opslag/e1/05/Z.pdf
 

Ved ikke om det er noget lignende jeg skal ud i? Er lidt lost, for sfd(15;9)=3 ... Så ved slet ikke hvor 61 kommer fra...

Lidt uddybning til #3

Det du har er normalt 2 tal e og n hvor du skal find 2 tal d og k så e*d+n*k = 1

I Euklids algoritme indæser man 2 tal a0 og a₁ og får som resultat 2 hele tal l og m hvorom det gælder

a₀*l  +  a₁m  = sfd(a₀, a₁)   sammenligner du med det du vil finde

e*d  +   n*k    = 1

bruger du Euklids algoritme med a₀ = e  og a₁ = n vil l  kunne bruges for  d og m fo k såfremt den største fælles devisor gor e og n er 1

Ja, men hvordan viser jeg så at 61 kan skrives på denne måde?

Jeg synes heller ikke den beskivelse filen i #4 er særlig læsevenlig. Her er så en kort og præcis version i psudokode. Jeg bruger betegnelserne fra #5

trin 0.

  Initialisering. Indlæs  a₀ og a₁: sæt u₀=1, v₀=0, u₁=0:v₁ = 1:i = 1

trin 1.

sæt q_i =  heltal af a_i-1/a_i                         Finder kvotienten ved heltalsdivision af de seneste a'er

sæt a_i+1 = a_i-1-q_i*a_i-1                                sætter næste a til resten ved division af de 2 foregående a'er

sæt u_i+1 = u_i-1-q_i*u_i-1: vi+1 = vi-1-qi*vi     opdaterer u og v så a_i+1 = u_i+1*a0+v_i+1*a₁

trin 2 Hvis ai+1 > 0 i := i+1 gå til trin 1 ellers stop

a_i = u_i*a₀ +v_i*a₁ = sfd(a₀,a₁)

For at at tage det eksempel tilpasset RSA med find x og y så 15x+9y = sfd(15, 9)

trin 0. a0 =15, a1 = 9 u0 = 1, v0 = 0, u1 = 0 v1= 1 i= 1

trin 1

q1 = heltal(15/9) = 1 a2 = 15-9*1 = 6, u2= 1-1*0 = .1, v2 = 0-1*1 = -1       ( 6 = 1*15+ (-1)*9 )

trin 2 

a2 > 0 så  i = 1+1 = 2,  og man starter forfra med trin 1

trin1  (i andet gennemløb)

q3 = heltal (a2/a1) = heltal(9/6) = 1; a3 = 9-6 = 3 ; u3 = 0-1*1 = -1, v3 = 1- 1*(-1) = 2     (3= -1*15+2*9)

trin 4 i andet løb

a3 =  3 så i=2+1 = 3 og start igen med trin 1

Det kan du selv fortsætte med men næste gennemløb giver a4 = 0 så algoritmen stopper

Ja. Alt dette har jeg også gjort. Men så får jeg jo ikke at sfd(15,9) er 61? Dette giver jo 3.. Det er lidt der mit problem ligger. Men er det så fordi at ligningen er falsk, altså at der ikke findes nogle hele tal for x og y? Det er jo også kun hvis denne passer at jeg skal give en løsning.

Skal jeg regne baglæns eller hvad? Føler mig lidt på vildspor. :-)

sfd(15,9) = 3 så det er ikke så mærkeligt at du ikke får at den er 61. Hvad mener du med at regne baglæns ?

Altså har jo fået disse to opgaver jeg skal løse:

Findes der hele tal af x og y, så primtallet 61 kan skrives på formen 61=9x+15y? Giv i bekræftende fald en løsning på værdierne for x og y.

og

Findes der hele tal af x og y, så primtallet 61 kan skrives på formen 61=9x+16y? Giv i bekræftende fald en løsning på værdierne for x og y.

Så om jeg skal regne baglæns så jeg får sfd(x,y)=61? eller hvad? for den største fælles divisor for srd(16,9) giver jo heller ikke 61. Og det ville jo være mærkeligt hvis der ikke minimum er én af opgaverne der kan løses, så man kan illustrer udregningen. Det er nemlig to opgaver der skal med i min SRP. :-)

#11

Ligningen c = ax + by hvor a,b,c∈Z har en heltalsløsning hvis og kun hvis sfd(a,b)|c.

I dette tilfælde er den største fælles devisor for a og b lig med 3