Blogg | Spektraklet

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.

Årsfestveckan har kommit och gått, men finns det verkligen några minnen kvar? Ryktena är många, historierna är fantasifulla, men vad är det verkligen som har hänt? Om minnesluckor existerar kan jag trösta er med en kort förklaring över vad som borde ha hänt under denna oförglömliga vecka. Tyvärr har jag inte funnit några bildbevis över denna fantastiska tillställning, så därför får ni en bild på en korkstol.

Torsdag 14.3
Denna sköna torsdagkväll gick HUS-rundan av stapeln. Det ryktas att det enda anmälda laget klarade HUS-rundan utan större problem. Stiliga och klädda för fest lär de ha gott omkring och provsmakat sina drycker. Rykten om att Münschenstopet skulle ha tagits senare under kvällens lopp har ännu inte kunnat bekräftas…

Måndag 18.3
Detta var dagen då alla skulle bli upplysta med ny information som de inte ens i sina vildaste fantasier skulle ha trott att existerade. Jag talar självfallet om seminariet ”Vetenskap i vardagen”. Det försvann dock mystiskt och till allas förtret. Tur att vi spektrumiter inte är käda för att gräva huvudet ner i sanden och gråta.

Tisdag 19.3 Bandkväll på Klubben var något som nästan alla hade hört ryktas om, men som få tidigare fått uppleva. Säkra källor har viskat i mitt öra att det bjöds på underhållning av högsta kvalitét och att musiken föll Spektrumiterna i smaken. Såväl Två Smeder som allas vår Sebbe sjöng så att stämbanden och diafragman nästan smälte av förtjusnig.

Onsdag 20.3 Företagsexkursion stod på programmet idag och detta blev en stor succé. Kemira var företaget som vänligt tog emot oss och visade oss runt. Intresset var stort för företaget, t.o.m. så pass stort att det drog med zig finska kemister på vår lilla utfärd. Efter en fin presentation och en rundvandring med många möjligheter att nästan peta på saker bjöds det sist och slutligen på en smaklig lunch.

Torsdag 21.3 Det finns vaga minnen om att Vasagatan skulle ha inträffat detta datum. Mångas minnen är troligen suddiga från denna förträffliga tillställning. Kan dock meddelas att alla lag (även arrangörerna hittade till Klubben även denna gång) kom i mål och det vinnande laget hade ett namn. Vad namnet var minns inte skribenten på rak arm. Många bravader lär ha utförts, men där sviker nog minnet.

Fredag 22.3 Förkör och bastubad var något som människor fick njuta av denna fantastiska fredagkväll. Bastubadet gick som vanligt av stapeln vid Majstranden, medan förköret fick ha sin tillflyktsort på Klubben. Maten var, om dock kryddstark, utmärkt och sällskapet ännu bättre. Efter ett lugnt förkör började själva efterfesten snabbt med kolven. Denna sagda kolv torde ännu vara hel och välanvänd.

Lördag 23.3 Ryska lunchen och själva festsupén fick pryda lördagens program. Den ryska lunchen var utsökt och trots lite tidspress mot slutet så hann alla glatt med färjan till Sveaborg. Festen var otroligt fin och alla verkade njuta av sällskapet och underhållningen. Tal hölls, piano spelades, stipendier gavs ut och nya bekantskaper hittades. Även här var maten fantastisk och glada och mätta kunde alla Spektrumiter ta sina två vänsterfötter ut på dansgolvet. Efter dansandet bar det av mot Alinasalen där Nachspielet hölls. Detta var tekninskt sett under söndagen, men, men… Mycket av tiden på Alinasalen spenderades med att spela Caps, resten av tiden kommer man nog inte ihåg.

Söndag 24.3 Sista dagen av vår fantastiska årsfestvecka kom till sist med dunder och brak. Sillisen hölls även den i Alinasalen och vilken tillställning det blev. Sånger sjöngs, humöret var på topp och maten var precis det man behövde få i magen. Efter några återställare sjöngs sångerna ännu högre och humöret steg ännu mer. Tyvärr gick deltagarna miste om ett fantastiskt spex p.g.a. tekninska svårigheter. Men misströsta inte, ty spexet återuppstår nämligen nu! Här kommer Spexet i all dess prakt och glans. Hoppas att ni finner det ens lite underhållande!

[youtube=http://youtu.be/szL6fxjMy34]

Jag vill sist, men inte minst, tacka alla som deltagit, hjälpt till och planerat denna fina tillställning. Ni har verkligen gjort det till ett minne för livet.

– Sandra

Spektraklet

Kategoriarkiv: Blogg

Matematikhörnan: Delbarhet

Definitioner och några enkla satser

Några välkända delbarhetsresultat

Fler delbarhetsresultat

Årsfestveckan – ett hejdundrande kalas!

Spektrum rfs medlemstidning