Etikettarkiv: Matematik

2013, Blogg

Medelvärdesspektrumiten

2 augusti, 2013 Joar Jensén Lämna en kommentar

I period 2 på hösten 2012 gick jag och ett antal andra spektrumiter kursen Matriisilaskennan sovellukset som förelästes av Samuli Siltanen. Kursen behandlade, såsom man från dess namn kunde gissa, olika tillämpningar av matrisräkning, bl.a. olika sorters matrisdekompositioner och sätt att beräkna egenvärden för matriser.

Under kursen användes programmet MATLAB, som är behändigt då man behandlar matriser. Dock behöver inte matriserna vara endast tråkiga matematiska objekt; man kan även beskriva t.ex. bilder som matriser! Då får varje punkt på bilden ett värde enligt dess färg. Under kursen demonstrerades några matrismetoder för bildmanipulation och den mest underhållande av dessa var hur man kan räkna ut ett medeltal av en mängd bilder. Föreläsaren hade samlat ihop ett antal bilder på människors ansikten och beräknade sedan ut ett medeltal av dem.

Bildmedeltalsmetoderna gav naturligtvis oss spektrumiter en lysande idé: vad om vi skulle ta reda på hur en spektrumit ser ut i medeltal? Metoderna hade vi ju redan färdigt, så det enda vi behövde var bilder på möjligtvis många spektrumiter. För detta ändamål visade sig julfesten vara utmärkt. Fredi, vår flitiga fotograf, lånade ut sin kamera under kvällen och såg sedan till att fotografierna kunde användas till artikeln.

Efter ett antal timmar av bildeditering och bråkande med Octave (en open-source MATLAB-klon), så kan jag nu stolt presentera er medelvärdesspektrumiten:

Om detta vore en vetenskaplig artikel, borde jag nu analysera resultatet och dra några slutsatser. Istället ger jag er som avslutning en till, Disney-inspirerad medelbild:

Priceless! Tänk vad roligt matrisräkning kan vara!

Ps. Det ser ut som att kursen Matriisilaskennan sovellukset föreläses även denna höst i period 2. Kursen rekommenderas varmt!

2013, Blogg

Delbarhet, del 2

5 juli, 2013 Spektraklet Lämna en kommentar

I artikeln Matematikhörnan: Delbarhet definierades delbarhetssekvenser för naturliga tal. Delbarhetssekvensen för det naturliga talet $n$ består av talen $10^i\:(mod \: n)$ , där $i \in \mathbb{N}_{0}$ . I nedanstående tabell ser vi början av delbarhetssekvenserna för några tal:

2: 1, 0, 0, 0, 0, 0…
3: 1, 1, 1, 1, 1, 1…
5: 1, 0, 0, 0, 0, 0…
7: 1, 3, 2, -1, -3, -2…
9: 1, 1, 1, 1, 1, 1…
11: 1, -1, 1, -1, 1, -1…

I föregående artikel märkte vi att alla av dessa sekvenser kommer att upprepa sig i något skede. För talen 2 och 5 beror detta på att något av talen är noll, och därmed kommer alla därpåföljande tal att vara noll, ty ifall $10^k \equiv 0 \:(mod \: n)$ , så är även $10^{k+m} \equiv 10^k10^m \equiv 0\:(mod \: n)$ .

De övriga sekvenserna i tabellen innehåller talet 1 på något annat index än 0. Då upprepas sekvensen, eftersom om $10^k \equiv 0\:(mod \: n)$ , så gäller $10^{k+m} \equiv 10^k10^m \equiv 10^m \:(mod \: n)$ .

Alltså, ifall en sekvens innehåller talet 0 eller 1 på något annat index än 0, kommer sekvensen att upprepas.

Sekvenser som innehåller talet 0

För att delbarhetssekvensen för talet $n \in \mathbb{N}$ skall innehålla talet 0, måste det för något $k \in \mathbb{N}$ gälla att

$10^k \equiv 0 \:(mod \: n)$ , dvs. $n \mid 10^k$ .

Eftersom $10 = 2*5$ , kan detta gälla endast ifall talet $n$ innehåller endast primtalsfaktorerna 2 och 5, dvs. om

$n=2^a5^b$ , där $a,b \in \mathbb{N}$ .

Ifall $n$ kan skrivas i ovanstående form, och vi betecknar $k=max(\{a,b\})$ , gäller $10^k \equiv 0\:(mod \: n)$ .

Sekvenser som innehåller talet 1

I vilka fall kan vi då vara säkra på att ett tal har en delbarhetssekvens som på något index olika noll har talet 1? Antag att $p \in \mathbb{P}$ är ett primtal. Ifall $p$ ej är talet 2 eller 5, kommer $p$ inte att dela talet $10^k$ för något $k \in \mathbb{N}$ , alltså är $10^k \not\equiv 0\:(mod \: p)$ för alla $k \in \mathbb{N}$ .

Som bekant bildar modulo-operationen $(mod \: p)$ ringen $\mathbb{Z}_{p}$ . Eftersom $10^k \not\equiv 0\:(mod \: p)$ om p inte är primtalet 2 eller 5, gäller det att $10^k \in \mathbb{Z}_{p} \char`\\ \{0\}$ . Dessutom vet vi att om (och endast om) $p$ är ett primtal, är ringen $\mathbb{Z}_{p}$ en kropp, alltså har alla tal förutom noll en multiplikativ invers. Detta är ekvivalent med att $\mathbb{Z}_{p} \char`\\ \{0\}$ bildar en grupp med multiplikationsoperationen.

Delbarhetssekvensen består per definition av talen $10^i\:(mod \: n)$ , där $i \in \mathbb{N}_{0}$ . I fallet där $p$ är ett primtal olika 2 och 5, innehålls alla tal i sekvensen alltså i den delgrupp av $\mathbb{Z}_{p} \char`\\ \{0\}$ som talet $10$ (eller närmare sagt dess ekvivalensklass) genererar. Eftersom gruppen $\mathbb{Z}_{p} \char`\\ \{0\}$ är ändlig, kommer även den genererade delgruppen att vara ändlig. Därmed existerar det ett $k \in \mathbb{N}$ för vilket $10^k \equiv 1 \:(mod \: p)$ .

Talen i sekvensen kommer alltså att upprepas efter ett visst index k. Närmare sagt, eftersom $10^k \equiv 1 \equiv 10^0 \:(mod \: p)$ , sä gäller

$latex \begin{array}{ll}
10^{k+1} \equiv 10^k10^1 \equiv 10^1\\
10^{k+2} \equiv 10^k10^2 \equiv 10^2\\
…\\
10^{k+k-1} \equiv 10^k10^{k-1} \equiv 10^{k-1}\\
\end{array}$ (mod p)

Sekvensen består alltså av cykler med längden k. Eftersom elementen i cykeln bildar en delgrupp av $\mathbb{Z}_{p} \char`\\ \{0\}$ , och gruppen $\mathbb{Z}_{p} \char`\\ \{0\}$ har p-1 element, vet vi enligt Lagranges sats att cykelns längd delar talet p-1. Vi ser också att eftersom $10^0 \equiv 1 \:(mod \: p)$ , kommer cykeln att starta från det första talet (alltså talet $10^0$ ) i sekvensen. Sekvensen har alltså ingen s.k. svans före cykeln.

Alltså alla primtal utom 2 och 5 har ett index olika noll på vilket delbarhetssekvensen har värdet 1. Naturligtvis kan även icke-primtal ha talet 1 i sin sekvens; i tabellen ovan ser vi att detta gäller för talet 9.

Övriga fall

Vi kan vara säkra på att delbarhetssekvensen för talet $n$ (icke-trivialt) innehåller talet 1 endast om $n$ är ett primtal. Därmed kunde man förvänta sig att det existerar tal vars delbarhetssekvens innehåller varken talet 0 eller talet 1. Det visar sig att detta gäller för talet 6. Låt oss alltså undersöka dess delbarhetssekvens:

För talet 10 gäller det att

$10 \equiv 4 \equiv -2 \:(mod \: 6)$ ,

och därmed ser vi att

$10^2 \equiv 10*10 \equiv -2*(-2) \equiv 4 \equiv -2 \:(mod \: 6)$ .

Av detta följer naturligtvis direkt att

$10^k \equiv 10^{k-1} \equiv \cdots \equiv 10 \equiv -2 \:(mod \: 6)$ .

Alltså är delbarhetssekvensen för talet 6 1,-2,-2,-2,… och sekvensen upprepar sig själv, fastän den inte icke-trivialt innehåller talet 0 eller 1.

Vad kan vi då säga om delbarhetssekvensen för talet $n$ som ej är ett primtal och har andra primtalsfaktorer än 2 och 5? Som vi redan tidigare konstaterat, bildar modulo-operationen $(mod \: n)$ ringen $\mathbb{Z}_{n}$ . Ringen är nu inte en kropp, eftersom vi antog att $n$ inte är ett primtal. Vi vet dock ändå att ifall vi multiplicerar två tal i ringen, kommer resultatet även att befinna sig i ringen.

Vi har alltså endast n stycken olika möjliga multiplikationsresultat. Därmed om vi beräknar talen $10^m \:(mod \: n)$ , där $m \in \mathbb{N}$ , måste vi i något skede stöta på ett tal som förekommit tidigare i sekvensen. Vi vet även att detta händer senast, då $m=n$ , eftersom vi inte kan ha $n+1$ olika tal i ringen. Alltså, vi hittar ett tal $m$ och ett annat tal $k < m$ för vilka

$10^m \equiv 10^k \:(mod \: n)$ .

Av detta följer naturligtvis att

$latex \begin{array}{ll}
10^{m+1} \equiv 10^m10^1 \equiv 10^k10^1 \equiv 10^{k+1}\\
10^{m+2} \equiv 10^m10^2 \equiv 10^k10^2 \equiv 10^{k+2}\\
…\\
10^{m+(m-k)-1} \equiv 10^{k+(m-k)-1} \equiv 10^{m-1}\\
10^{m+(m-k)} \equiv 10^{k+(m-k)} \equiv 10^k\\
\end{array}$ (mod n),

alltså går sekvensen efter talet $10^k$ in i en cykel med längden $m-k$ . Till skillnad från sekvenserna för primtal, kan denna sekvens ha en s.k. svans i början förrän cykeln börjar. Detta beror på att talet 1 inte nödvändigtvis förekommer i sekvensen förutom i början.

Öppna frågor

Talen 3 och 9 har exakt likadan delbarhetssekvens; den består endast av ettor. Finns det andra talpar som har exakt likadan delbarhetssekvens? Om det finns, kan vi hitta något samband för tal som har likadan delbarhetssekvens?

Finns det något samband mellan primtalsutvecklingen och delbarhetssekvensen för tal?

Kan vi på något vettigt sett gruppera icke-primtal i olika grupper, t.ex. enligt längden på cykeln?

Litteratur

Allmän algebra:

Jokke Häsä, Johanna Rämö: Johdatus abstraktiin algebraan, Gaudeamus, 2012.
Tauno Metsänkylä, Marjatta Näätänen: Algebra, Limes, 2005.

Nyttiga wikipedia-länkar:

Group
Ring
Finite field (ändlig kropp)

Lagrange’s theorem
Fundamental theorem of arithmetic

2013, Blogg

Matematikhörnan: Delbarhet

2 april, 2013 Spektraklet 1 kommentar

I vår nya fina Spektrakel-blogg kommer jag (och förhoppningsvis även andra) med slumpmässiga intervall att skriva artiklar om matematiska problem som jag tycker är intressanta. Denna del av bloggen har jag valt att kalla Matematikhörnan. Det första inlägget handlar om delbarhet.

Delbarhet är en grundläggande men viktig del av talteori. Detta inlägg går igenom grunderna med delbarhet och kongruenser, och i slutet presenteras några små resultat.

Obs! Ifall inte annat nämns, är alla tal i denna artikel heltal.

Definitioner och några enkla satser

Definition 1: Talet d delar talet n, om $\frac{n}{d}$ är ett heltal. Vi betecknar detta $d \mid n$ . Ifall d delar n kan vi alltså skriva $n = kd$ för något heltal k.

Definition 2: Vi säger att talen a och b är kongruenta modulo n, ifall $n \mid (a-b)$ . Detta betecknas $a \equiv b$ (mod n).

En observation: Ifall $a \equiv b$ , gäller $a-b = nk$ , dvs. differensen av a och b är en multipel av n.

Sats 3: Om $d|n$ och $d|m$ , så gäller för alla heltal a och b att $d|(an + bm)$ .

Bevis: Vi vet att $n = kd$ och $m = ld$ för några l och k, alltså gäller det att $an + bm = akd + mld = d(ak+ml)$ , dvs $d\mid(an + bm)$ .

Sats 4: Ifall $a \equiv b$ (mod n) och $c \equiv d$ (mod n), så gäller $a\pm c \equiv b \pm d$ (mod n) och $ac \equiv bd$ (mod n).

Bevis: Eftersom $n \mid (a-b)$ och $n \mid (c-d)$ , gäller enligt föregående sats att $n\mid((a-b)+(c-d)) = ((a+c) - (b+d))$ , och även $n\mid((a-b)-(c-d)) = ((a-c) - (b-d))$ . Alltså gäller första påståendet.

För att visa det andra påståendet räcker det att märka att enligt Sats 3 gäller det att $n\mid(c(a-b) + b(c-d)) = (ac - bd)$ .

Av Sats 4 följer enkelt följande:

Följdsats 5: Om $a \equiv b$ (mod n), så gäller $a^{m} \equiv b^{m}$ för alla positiva heltal m.

Några välkända delbarhetsresultat

Vi kan med hjälp av satserna ovan bevisa några praktiska resultat om delbarhet. Troligtvis vet vi alla från tidigare att ett tal är delbart med två om och endast om dess sista siffra är delbar med två, och att ett tal är delbart med fem om och endast om dess sista siffra är delbar med fem. Värför gäller då detta?

Som bekant kan vi skriva alla heltal k i formen $k = a_{n}10^{n} + a_{n-1}10^{n-1} + \cdots + a_{1}10^1 + a_{0}10^0.$

Eftersom $10 \equiv 0$ (mod 2) och $10 \equiv 0$ (mod 5), gäller alltså även att $10^{m} \equiv 0^{m} = 0$ (mod 2) och (mod 5) för alla positiva m, alltså får vi att

$k = a_{n}10^{n} + a_{n-1}10^{n-1} + \cdots + a_{1}10^1 + a_{0}10^0 \equiv a_{0}$ (mod 2) och (mod 5).

Delbarheten beror alltså endast på sista siffran.

Ett lite mindre trivialt, men ändå välbekant resultat är att ett tal är delbart med tre om och endast om dess siffersumma är delbar med tre: Eftersom $10 \equiv 1$ (mod 3), är även $10^{m} \equiv 1^{m} = 1$ (mod 3), och därmed följer

$k = a_{n}10^{n} + a_{n-1}10^{n-1} + \cdots + a_{1}10^1 + a_{0}10^0 \equiv a_{n} + a_{n-1} + \cdots + a_{1} + a_{0}$ (mod 3),

Exempel: 432 är delbart med tre, eftersom $432 \equiv 4 + 3 + 2 = 9 = 3*3 \equiv 0$ (mod 3).

För stora tal kan metoden användas flera gånger, dvs. om siffersumman blir så stor att man inte direkt ser om den är delbar med tre, kan man beräkna siffersummans siffersumma och kontrollera om den är delbar med tre.

Vi märker också att eftersom $10 \equiv 1$ (mod 9), kan vi använda samma metod för att bestämma delbarhet med nio.

Fler delbarhetsresultat

Till näst undersöker vi delbarhet med 11. Eftersom 10 = 11 – 1, gäller $10 \equiv -1$ (mod 11). Därmed är $10^{m} \equiv (-1)^{m} = 1$ (mod 11) om m är jämnt och $10^{m} \equiv (-1)^{m} = -1$ (mod 11) om m är udda. Då gäller alltså för talet k att

$k = a_{n}10^{n} + a_{n-1}10^{n-1} + \cdots + a_{1}10^1 + a_{0}10^0 \equiv \pm a_{n} \mp a_{n-1} \cdots -a_{1} +a_{0}$ (mod 11),

var tecknet på $a_{n}$ beror på om n är udda eller jämnt.

Exempel: $11 \mid 7623$ , eftersom $7623 \equiv -7 + 6 - 2 + 3 = 0$ (mod 11).

Exempel: $11 \mid 52415$ , eftersom $52415 \equiv 5 - 2 + 4 - 1 + 5 = 11 \equiv 0$ (mod 11).

Exempel: $11 \nmid 11372$ , eftersom $11372 \equiv 1 - 1 + 3 - 7 + 2 = -2 \not\equiv 0$ (mod 11).

Vi kan alltså bestämma delbarheten genom att multiplicera siffrorna i talet med antingen talet 1 eller -1 och sedan summera dem.

Sekvensen för vilket tal vi skall multiplicera med vilken siffra är för talet 11 alltså (ifall vi börjar från den minst betydande siffran) 1, -1, 1, -1 osv.

Från våra tidigare resultat får vi även sekvenserna för följande tal:

2: 1, 0, 0, 0…
3: 1, 1, 1, 1…
5: 1, 0, 0, 0…
9: 1, 1, 1, 1…
11: 1, -1, 1, -1…

Läsaren har säkert redan märkt att vi hoppat över ett primtal, nämligen talet 7. Ifall vi beräknar sekvensen för talet 7, kan vi ganska enkelt med huvudräkning bestämma om ett tal mindre än 169 är ett primtal, eftersom då är dess kvadratrot mindre än 13, och då måste (minst) en av primtalsfaktorerna vara mindre än 13.

Vilken sekvens hittar vi alltså för sjuan?

Första talet i sekvensen är naturligtvis 1, eftersom $1 \equiv 1$ (mod n) för alla n.

De övriga talen i sekvensen fås enligt följande:

$latex \begin{array}{ll}
10 \equiv 3\\

10^2 \equiv 3*3 = 9 \equiv 2\\

10^3 \equiv 3*2 = 6 \equiv -1\\

10^4 \equiv 3*(-1) = -3\\

10^5 \equiv 3*(-3) = -9 \equiv -2\\

10^6 \equiv (-1)^2 = 1
\end{array}$ (mod 7)

Vi ser nu att $10^7 = 10*10^6 \equiv 10 \equiv 3$ (mod 7), och därmed kommer sekvensen att upprepa sig. Vi kan alltså fylla på vår lista:

2: 1, 0, 0, 0, 0, 0…
3: 1, 1, 1, 1, 1, 1…
5: 1, 0, 0, 0, 0, 0…
7: 1, 3, 2, -1, -3, -2…
9: 1, 1, 1, 1, 1, 1…
11: 1, -1, 1, -1, 1, -1…

Vi har nu räknat ut delbarhetssekvenserna för vissa tal, varav alla har en viss period varefter sekvensen upprepar sig. Kommer då sekvensen för alla naturliga tal att ha en ändlig period, dvs. har alla tal en sekvens som i något skede börjar upprepa sig? Denna fråga undersökes i min nästa artikel i Matematikhörnan.

Sebbe

Referenser:

Anne-Maria Ernvall-Hytönen: Elementär talteori. Föreläsningsanteckningar, Helsingfors universitet, 2013.

Sekvenser som innehåller talet 0

Sekvenser som innehåller talet 1

Övriga fall

Öppna frågor

Litteratur

Definitioner och några enkla satser

Några välkända delbarhetsresultat

Fler delbarhetsresultat

Spektrum rfs medlemstidning