diofantisk ekvation lösning

Fick inte plats i PM, fick en förfrågning så jag får svara här istället.

Diofantiska ekvationen:

17s+6m = 250

s är semlor och m är mandelkakor. s kan tolkas som x, och m kan tolkas som y i ett koordinatsystem, men det är lättare att hålla reda på vad som är vad om man skriver s och m istället.

På formen:

as+bm = c
Där a,b,c∈ℕ
Där SGD(a,b)=1
Om SGD(a,b)≠1

Finnes endast lösningar om SGD(a,b) är en delare till a,b,c

Undersökning av SGD(a,b) med Euklides algoritm:

SGD(a,b) = SGD(17,6)
17 = 6*2+5
6 = 5*1+1

Finn multiplikativ invers:

1 = 6-5 = 6-(17-6*2) = -1*17+6*3 = 1

Modulär aritmetisk tolkning:

Den multiplikativa inversen av 17 (mod 6) är -1
Den multiplikativa inversen av 6 (mod 17) är 3

Diofantisk tolkning:

s₀ = -1
m₀ = 3

Allmän lösning ges av:

s = cs₀±bn
m = cm₀∓an
Där n∈ℤ

Insättning:
s = -250+6n
m = 750-17n

Eftersom vi bara var intresserade av att köpa positiva semlor/kakor och inte sälja någon semla eller kaka så får vi lösa olikheten för de positiva heltalen. Då måste alltså s och m vara positivt (inte så konstigt). Uppgifterna för diofantiska ekvationer är också ofta "luddigt" förmulerade, men jag antar också att han faktiskt skall köpa minst en semla, annars är det lätt att lösa olikheten nedan annorlunda där man inkluderar noll i lösningen för semlor. I vilket fall skall han bara ha udda antal mandelkakor, eftersom noll inte är ett udda tal så skall semlor vara större än eller skiljt från noll.

Löser olikheten för semlor:

-250+6n > 0
6n > 250
n > 41.6666

Löser olikheten för mandelkakor:

750-17n > 0
750 > 17n
44.11 > n

Intervallet för n:

44.11 > n > 41.6666

Men eftersom n skall vara ett heltal måste vi förenkla. n skall vara större än och skiljt från 41.666, vilket betyder att närmaste heltal som är större än 41.666 är 42. n skall också vara mindre än och skiljt från 44.11, närmaste heltal här är 44.

Alltså:

44 ≥ n ≥ 42

Detta visar då att den diofantiska ekvationen har tre olika lösningar för de positiva heltalen nämligen när n antar värdet 44, 43 och 42. Geometrisk tolkning av detta är en linje negativ lutning som skär y-axeln på ett positivt värde och skär x-axeln på ett positivt värde, någonstans i den första kvadranten finns det då tre par av heltal på linjen, det finns endast just tre par av heltal. Detta är då lösningen på hur många semlor och mandelkakor vi har, det finns alltså tre olika sätt att kombinera dessa.

Lösning:

s = cs₀±bn
m = cm₀∓an ₁₂₃
⇒
s₁ = -250+44*6 = 14
s₂ = -250+43*6 = 8
s₃ = -250+42*6 = 2

m₁ = 750-44*17 = 2
m₂ = 750-43*17 = 19
m₃ = 750-42*17 = 36

Vi vet nu att antalet mandelkakor skulle vara ett udda tal, det enda udda värdet av mandelkakor som finns här är 19, alltså är den enda lösningen just talparet (koordinaten) (s₂, m₂) = (8, 19).

Prövar lösningen, om den stämmer:
17s+6m = 250
17*8+6*19 = 136+114 = 250

Ja det stämmer! Detta talparet av semlor och mandelkakor kostar exakt 250 kronor och är det enda udda talparet av mandelkubbar i vår lösning.

Svar:
8 Semlor och 19 Mandelkakor skulle Per köpa.

Tänk vad användbart diofantiska ekvationer kan vara om man glömt av hur många mandelkakor man skulle köpa!

Mvh BengtZz

Greppar inte hur du trollar fram -1 och *3 i tredje ledet?

Ursäkta för långsamt svar! Men bättre sent än aldrig.

1 = 6-5 = 6-(17-6*2)

Sådär vad har vi här nu då? Jo vi har exakt en sexa minus en parentes med någonting. Minustecknet framför parentesen kan vi se som en negativ etta, den multiplicerar vi då in i parentesen.[indent]6-17+6*2 =/INDENT]Har nu multiplicerat in -1 i parentesen. Nu måste vi kolla, hur många sexor har vi? först en, sedan två stycken till, alltså tre stycken.

-17+6*3

my eyes are open :=)

kan inte du förklara lite närmare om de här med modulerna? Kan modulräkning(ngt sånär) men det här känner jag inte riktigt till.. Eller ngn annan för all del.

Hur fick du fram den diofantiska tolkningen?

bump?

Vi tar påståendet:
Den multiplikativa inversen av 17 (mod 6) är -1

Det betyder alltså att om vi t.ex. har ekvationen
17x = a (mod 6)

Så kan vi lösa den genom att multiplicera den med -1

x = -a (mod 6)

17(*-1) ) = 1, om vi är i världen av modulo 6.



Om vi inte tänker oss modulo, utan vanlig enkel algebra så är t.ex. den multiplikativa inversen till 6 lika med 1/6, eftersom 1/6 gånger 6 är lika med 1.


För om vi tittar på ekvationen:
17x = a
Så löser vi ju den i vanliga fall genom att multiplicera med 1/17. Men 1/17 finns inte som ett tal i (mod 6). Så hur löser man det då? Jo man finner den multiplikativa inversen av 17 mod 6 genom t.ex. euklides algoritm. Det finns för övrigt bara en multiplikativ invers om sgd(17, 6) = 1.

Vi kan då finna att den inversen är -1

Jag kände för att skriva en uppdaterad variant av lösningen.

Diofantiska ekvationen:

17s+6m = 250

s är semlor och m är mandelkakor.

På formen:

as+bm = c
Där a,b,c∈ℕ
Där SGD(a,b)=1
Om SGD(a,b)≠1

Finnes lösning om och endast om SGD(a,b) är en delare till c

Allmän lösning ges av:

s = cs₀±bn
m = cm₀∓an

Där n∈ℤ
Där m₀ och s₀ är en partikulärlösning till 17s+6m = 1

Undersökning av SGD(a,b) med Euklides algoritm:

SGD(a,b) = SGD(17,6)
17 = 6*2+5
6 = 5*1+1

Finn multiplikativ invers m.h.a. SGD(a,b):

1 = 6-5 = 6-(17-6*2) = -1*17+6*3 = 1

Notera likheten för koefficienterna

17s+6m = 1
17(-1)+6*3 = 1

Det betyder att en partikulärlösning är:

s₀ = -1
m₀ = 3

Irrelevant för uppgiftslösningen, men intressant för sammanhanget:
Vi kan ur detta också tolka/inse att:

Den multiplikativa inversen av 17 (mod 6) är -1
Den multiplikativa inversen av 6 (mod 17) är 3

Eftersom Allmän lösning ges av:

s = cs₀±bn
m = cm₀∓an
Där n∈ℤ

Därmed gäller

s = 250(-1)±6n = -250±6n
m = 250(3)∓17n = 750∓17n

Vi kan välja att:

s = -250+6n
men då måste vi välja att
m = 750-17n

Eftersom enda kravet är att de måste vara olika tecken, vi hade lika gärna kunnat välja -6n och +17n.

Eftersom vi bara var intresserade av att köpa positiva semlor/kakor och inte sälja någon semla eller kaka så får vi lösa olikheten för de positiva heltalen. Då måste alltså s och m vara positivt (inte så konstigt). Uppgifterna för diofantiska ekvationer är också ofta "luddigt" förmulerade, men jag antar också att han faktiskt skall köpa minst en semla, annars är det lätt att lösa olikheten nedan annorlunda där man inkluderar noll i lösningen för semlor. I vilket fall skall han bara ha udda antal mandelkakor enligt uppgift.

Löser olikheten för semlor:

-250+6n > 0
6n > 250
n > 41.6666

Löser olikheten för mandelkakor:

750-17n > 0
750 > 17n
44.11 > n

Intervallet för n:

44.11 > n > 41.6666

Men eftersom n skall vara ett heltal måste vi förenkla. n skall vara större än och skiljt från 41.666, vilket betyder att närmaste heltal som är större än 41.666 är 42. n skall också vara mindre än och skiljt från 44.11, närmaste heltal här är 44.

Alltså:

44 ≥ n ≥ 42

Detta visar då att den diofantiska ekvationen har tre olika lösningar för de positiva heltalen, nämligen när n antar värdet 44, 43 och 42.

Lösning:

s = cs₀±bn
m = cm₀∓an
⇒
s₁ = -250+6*44= 14
s₂ = -250+6*43 = 8
s₃ = -250+6*42 = 2

m₁ = 750-17*44 = 2
m₂ = 750-17*43 = 19
m₃ = 750-17*42 = 36

Vi vet nu att antalet mandelkakor skulle vara ett udda tal enligt uppgift. Det enda udda värde av mandelkakor som finns här är 19, alltså är den enda lösningen just talparet (s₂, m₂) = (8, 19).

Prövar om lösningen stämmer:

17s+6m = 250
17*8+6*19 = 136+114 = 250

Ja det stämmer! Detta talpar av semlor och mandelkakor kostar exakt 250 kronor och är det enda udda talpar av mandelkakor i vår lösning.

Svar:
8 semlor och 19 mandelkakor skulle Per köpa.