{"id":17,"date":"2013-04-02T15:00:48","date_gmt":"2013-04-02T12:00:48","guid":{"rendered":"http:\/\/spektrakel.wordpress.com\/?p=17"},"modified":"2018-03-15T14:53:49","modified_gmt":"2018-03-15T11:53:49","slug":"matematikhornan-delbarhet","status":"publish","type":"post","link":"http:\/\/spektrum.fi\/spektraklet\/matematikhornan-delbarhet\/","title":{"rendered":"Matematikh\u00f6rnan: Delbarhet"},"content":{"rendered":"

I v\u00e5r nya fina Spektrakel-blogg kommer jag (och f\u00f6rhoppningsvis \u00e4ven andra) med slumpm\u00e4ssiga intervall att skriva artiklar om matematiska problem som jag tycker \u00e4r intressanta. Denna del av bloggen har jag valt att kalla Matematikh\u00f6rnan.<\/em> Det f\u00f6rsta inl\u00e4gget handlar om delbarhet.<\/p>\n

Delbarhet \u00e4r en grundl\u00e4ggande men viktig del av talteori. Detta inl\u00e4gg g\u00e5r igenom grunderna med delbarhet och kongruenser, och i slutet presenteras n\u00e5gra sm\u00e5 resultat.<\/p>\n

Obs! Ifall inte annat n\u00e4mns, \u00e4r alla tal i denna artikel heltal.<\/p>\n

Definitioner och n\u00e5gra enkla satser<\/h2>\n

Definition 1:<\/strong><\/em> Talet d delar<\/em> talet n, om \\frac{n}{d} \u00e4r ett heltal. Vi betecknar detta d \\mid n. Ifall d delar n kan vi allts\u00e5 skriva n = kd f\u00f6r n\u00e5got heltal k.<\/p>\n

Definition 2:<\/strong><\/em> Vi s\u00e4ger att talen a och b \u00e4r kongruenta modulo n, <\/em>ifall n \\mid (a-b). Detta betecknas a \\equiv b (mod n).<\/p>\n

En observation: Ifall a \\equiv b, g\u00e4ller a-b = nk, dvs. differensen av a och b \u00e4r en multipel av n.<\/p>\n

Sats 3:\u00a0<\/strong>Om d|n och d|m, s\u00e5 g\u00e4ller f\u00f6r alla heltal a och b att d|(an + bm).<\/p>\n

Bevis:<\/em> Vi vet att n = kd och m = ld f\u00f6r n\u00e5gra l och k, allts\u00e5 g\u00e4ller det att an + bm = akd + mld = d(ak+ml), dvs d\\mid(an + bm).<\/p>\n

Sats 4:\u00a0<\/strong>Ifall a \\equiv b (mod n) och c \\equiv d (mod n), s\u00e5 g\u00e4ller a\\pm c \\equiv b \\pm d (mod n) och ac \\equiv bd (mod n).<\/p>\n

Bevis:<\/em> Eftersom n \\mid (a-b) och n \\mid (c-d), g\u00e4ller enligt f\u00f6reg\u00e5ende sats att n\\mid((a-b)+(c-d)) = ((a+c) - (b+d)), och \u00e4ven n\\mid((a-b)-(c-d)) = ((a-c) - (b-d)). Allts\u00e5 g\u00e4ller f\u00f6rsta p\u00e5st\u00e5endet.<\/p>\n

F\u00f6r att visa det andra p\u00e5st\u00e5endet r\u00e4cker det att m\u00e4rka att enligt Sats 3 g\u00e4ller det att n\\mid(c(a-b) + b(c-d)) = (ac - bd).<\/p>\n

Av Sats 4 f\u00f6ljer enkelt f\u00f6ljande:<\/p>\n

F\u00f6ljdsats 5:<\/strong> Om a \\equiv b (mod n), s\u00e5 g\u00e4ller a^{m} \\equiv b^{m} f\u00f6r alla positiva heltal m.<\/p>\n

N\u00e5gra v\u00e4lk\u00e4nda delbarhetsresultat<\/h2>\n

Vi kan med hj\u00e4lp av satserna ovan bevisa n\u00e5gra praktiska resultat om delbarhet. Troligtvis vet vi alla fr\u00e5n tidigare att ett tal \u00e4r delbart med tv\u00e5 om och endast om dess sista siffra \u00e4r delbar med tv\u00e5, och att ett tal \u00e4r delbart med fem om och endast om dess sista siffra \u00e4r delbar med fem. V\u00e4rf\u00f6r g\u00e4ller d\u00e5 detta?<\/p>\n

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.<\/p>\n

Eftersom 10 \\equiv 0 (mod 2) och 10 \\equiv 0 (mod 5), g\u00e4ller allts\u00e5 \u00e4ven att 10^{m} \\equiv 0^{m} = 0 (mod 2) och (mod 5) f\u00f6r alla positiva m, allts\u00e5 f\u00e5r vi att<\/p>\n

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).<\/p>\n

Delbarheten beror allts\u00e5 endast p\u00e5 sista siffran.<\/p>\n

Ett lite mindre trivialt, men \u00e4nd\u00e5 v\u00e4lbekant resultat \u00e4r att ett tal \u00e4r delbart med tre om och endast om dess siffersumma \u00e4r delbar med tre: Eftersom 10 \\equiv 1 (mod 3), \u00e4r \u00e4ven 10^{m} \\equiv 1^{m} = 1 (mod 3), och d\u00e4rmed f\u00f6ljer<\/p>\n

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),<\/p>\n

Exempel: 4<\/em>32 \u00e4r delbart med tre, eftersom 432 \\equiv 4 + 3 + 2 = 9 = 3*3 \\equiv 0 (mod 3).<\/p>\n

F\u00f6r stora tal kan metoden anv\u00e4ndas flera g\u00e5nger, dvs. om siffersumman blir s\u00e5 stor att man inte direkt ser om den \u00e4r delbar med tre, kan man ber\u00e4kna siffersummans siffersumma och kontrollera om den \u00e4r delbar med tre.<\/p>\n

Vi m\u00e4rker ocks\u00e5 att eftersom 10 \\equiv 1 (mod 9), kan vi anv\u00e4nda samma metod f\u00f6r att best\u00e4mma delbarhet med nio.<\/p>\n

Fler delbarhetsresultat<\/h2>\n

Till n\u00e4st unders\u00f6ker vi delbarhet med 11. Eftersom 10 = 11 – 1, g\u00e4ller 10 \\equiv -1 (mod 11). D\u00e4rmed \u00e4r 10^{m} \\equiv (-1)^{m} = 1 (mod 11) om m \u00e4r j\u00e4mnt och\u00a010^{m} \\equiv (-1)^{m} = -1 (mod 11) om m \u00e4r udda. D\u00e5 g\u00e4ller allts\u00e5 f\u00f6r talet k att<\/p>\n

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),<\/p>\n

var tecknet p\u00e5 a_{n} beror p\u00e5 om n \u00e4r udda eller j\u00e4mnt.<\/p>\n

Exempel:<\/em> 11 \\mid 7623, eftersom 7623 \\equiv -7 + 6 - 2 + 3 = 0 (mod 11).<\/p>\n

Exempel:<\/em> 11 \\mid 52415, eftersom 52415 \\equiv 5 - 2 + 4 - 1 + 5 = 11 \\equiv 0 (mod 11).<\/p>\n

Exempel: <\/em>11 \\nmid 11372, eftersom 11372 \\equiv 1 - 1 + 3 - 7 + 2 = -2 \\not\\equiv 0 (mod 11).<\/p>\n

Vi kan allts\u00e5 best\u00e4mma delbarheten genom att multiplicera siffrorna i talet med antingen talet 1 eller -1 och sedan summera dem.<\/p>\n

Sekvensen f\u00f6r vilket tal vi skall multiplicera med vilken siffra \u00e4r f\u00f6r talet 11 allts\u00e5 (ifall vi b\u00f6rjar fr\u00e5n den minst betydande siffran) 1, -1, 1, -1 osv.<\/p>\n

Fr\u00e5n v\u00e5ra tidigare resultat f\u00e5r vi \u00e4ven sekvenserna f\u00f6r f\u00f6ljande tal:<\/p>\n