Hoppa till huvudinnehållet
Logga inSkapa konto
3. Heltal och diofantiska ekvationer

Heltal och diofantiska ekvationer

Använd och Euklides algoritm för att finna och beskriva heltalslösningar.

Översikt

Division med rest bevarar gemensamma delare

Vid division med rest ligger resten mellan noll och divisorn minus ett. Ett tal delar både dividend och divisor precis när det delar både divisor och rest. Euklides algoritm upprepar detta tills resten är noll; den sista icke-nollresten är största gemensamma delaren. Baklängessubstitution skriver denna som en heltalskombination.

a=bq+r⟹gcd⁡(a,b)=gcd⁡(b,r)a=bq+r\quad\Longrightarrow\quad\gcd(a,b)=\gcd(b,r)

Exempel

Exempel: lös en linjär heltalsekvation

För koefficienterna 84 och 30 ger Euklides algoritm resterna 24 och 6. Största gemensamma delaren är sex. Baklänges får vi sex som tre gånger 30 minus 84. En särskild lösning är därför minus ett respektive tre. Alla lösningar fås genom att öka den första variabeln med fem och minska den andra med fjorton.

84x+30y=6⟺x=−1+5t, y=3−14t, t∈Z84x+30y=6\quad\Longleftrightarrow\quad x=-1+5t,\ y=3-14t,\ t\in\mathbb Z

Fördjupning

Existens och alla lösningar är olika frågor

Att högerledet är delbart med största gemensamma delaren avgör om lösningar finns. Det anger inte alla lösningar. Efter att en särskild lösning hittats måste den homogena ekvationen lösas för att parameterisera samtliga. Kontrollera slutligen både att varje angivet par uppfyller ekvationen och att parameterformen fångar varje heltalslösning. Om högerledet inte är delbart med den gemensamma delaren är det omöjligt redan före baklängesräkningen.

ax+by=c har heltalslo¨sningar  ⟺  gcd⁡(a,b)∣cax+by=c\text{ har heltalslösningar}\iff\gcd(a,b)\mid c

Formler i området

Euklides algoritm

a=bq+r⇒gcd⁡(a,b)=gcd⁡(b,r)a=bq+r\quad\Rightarrow\quad\gcd(a,b)=\gcd(b,r)
Vad gör formeln?
Upprepad division hittar största gemensamma delaren.
När får den användas?
Heltal med positiv divisor; resten är minst noll och mindre än divisorn.

Bézouts identitet

∃u,v∈Z: au+bv=gcd⁡(a,b)\exists u,v\in\mathbb Z:\ au+bv=\gcd(a,b)
Vad gör formeln?
Skriver största gemensamma delaren som en heltalskombination.
När får den användas?
Heltalen är inte båda noll.

Linjär

ax+by=c,d=gcd⁡(a,b)∣c,x=x0+bdt, y=y0−adt(t∈Z)ax+by=c,\quad d=\gcd(a,b)\mid c,\quad x=x_0+\frac bd t,\ y=y_0-\frac ad t\quad(t\in\mathbb Z)
Vad gör formeln?
En särskild lösning ger alla heltalslösningar.
När får den användas?
Koefficienterna är icke-nollheltal och en särskild lösning är känd; om delbarhetsvillkoret inte gäller saknas lösningar.

Hänger ihop med

Kan du använda heltal och diofantiska ekvationer?

Lös en riktig tentauppgift från SF1662 med ledtrådar och lösningsförslag. Inget konto behövs.

Prova en uppgift