Lite om Dugga 2

Uppgift 6 är en standardtillämpning av Euklides algoritm. Se till att ni kan detta inför tentan!

Uppgift 7 har lett till en del frågor och funderingar. På föreläsningen gick jag igenom ett liknande exempel, som visade att ekvationen \[x^3 - 13y^2 = 2\] saknar heltalslösningar.

Tricket är att använda kongruensräkning. Om ekvationen hade någon lösning, så skulle även kongruensen \[ x^3 - 13y^2 \equiv 2 \quad (\text{mod $n$})\] ha en lösning, oavsett vilket $n$ vi väljer. En strategi för att bevisa att ekvationen saknar lösningar (eller för att hitta dem om det finns!) är att välja några värden på $n$ och se om ekvationen (alltså motsvarande kongruens) har någon lösning modulo $n$.

Det fiffiga med moduloräkning är att det bara finns ett ändligt antal kongruensklasser. Skulle vi till exempel undersöka den här ekvationen modulo 3, finns det bara 9 olika fall. Det finns 3 kongruensklasser, och var och en av $x$ och $y$ måste tillhöra någon av dem. Nu visar det sig att ekvationen har lösningar modulo 3, till exempel $x\equiv 0$ och $y\equiv 1$. Då kan vi inte dra någon slutsats. Bara för att ekvationen har lösningar modulo 3 behöver det inte finnas någon "riktig" lösning.

Om vi i stället väljer att titta på ekvationen modulo 13, händer något intressant. Eftersom termen $13y^2$ då blir kongruent med 0, spelar det ingen roll vad $y$ är, utan vi får ett villkor på bara $x$, nämligen \[x^3 \equiv 2 \quad (\text{mod $n$}).\] Det finns bara 13 fall att testa, så vi kan göra en tabell och gå igenom alla. Enklast blir det om vi testar $x$ i intervallet $-6\leq x \leq 6$, eftersom $(-x)^3 = -x^3$. Men 13 konsekutiva tal vilka som helst går bra, vi måste bara få med ett tal i varje kongruensklass, så att vi täcker in alla fall.
Vi har
$0^3\equiv 0$, $1^3 \equiv 1$, $2^3 \equiv 8$, $3^3\equiv 1$, $4^3\equiv 12$, $5^3\equiv 8$, $6^3\equiv 8$.
Samt $(-1)^3\equiv -1 \equiv 12$, $(-2)^3 \equiv -8 \equiv 5$, $(-3)^3\equiv -1\equiv 12$, $(-4)^3 \equiv -12 \equiv 1$, $(-5)^3\equiv -8\equiv 5$, och $(-6)^3\equiv -8\equiv 5$.
Då har vi testat alla kongruensklasser, och ser att oavsett värde på $x$, så måste $x^3$ vara kongruent med något av talen 0, 1, 5, 8, och 12. Det blir alltså aldrig kongruent med 2, och därför kan ekvationen inte ha några heltalslösningar.

Jag såg också att någon har postat den här uppgiften på pluggakuten. Jag har ju sagt att ni får diskutera uppgifterna (och det är i själva verket ett pedagogiskt "trick" från min sida), så det här är inget som är förbjudet. I det här fallet har någon svarat på ett bra sätt utan att skriva en hel lösning. Så då kan jag lika gärna länka härifrån så blir det rättvist och bra!

På uppgift 8 krävs inte mycket motivering, men något litet nyckelord vill jag att ni skriver som förklaring.

Uppgift 9 verkar vara ganska "straightforward".

Uppgift 10 handlar om grafer, uppspännande träd, och isomorfi. Antalet uppspännande träd i $K_4$ efterfrågas även i uppgift 7.14 i boken. Notera att villkoret att grafen ska vara sammanhängande (som det står i uppgift 7.14) inte är nödvändigt för själva definitionen av begreppet uppspännande träd. Det är bara det att det inte finns några om grafen inte är sammanhängande. Det villkoret behöver ni således inte fundera över.
Isomorfi är en ekvivalensrelation, och de uppspännande träden i $K_4$ kan alltså delas in i klasser, där träd i samma klass är isomorfa, och träd i olika klasser inte är isomorfa.