SF1662

Här tänker vi publicera ett o annat, gärna/mest matteproblem

i kursen ingår begreppen total ordning och partiell ordning.
Tills vidare råder här total oordning.

en del är lånat från http://www.facebook.com/matte.promenader

KINESISKA RESTSATSEN
En gång för länge sen fanns en farbror som hette Sun Tzu – ja, det fanns fler, det fanns en som skrev om krigskonst, och en som skrev om matematik bla. Vi är nu intresserade av mattegubben och han fanns 3-5 århundraden eKr. Vad handlar då denna om? Vi tänker oss att vi håller oss i heltalens värld. Antag nu att vi har ett okänt tal men vet vilken rest vi få när vi delar med olika tal. Hur ska vi få reda på talet? Vi får ta ett exempel för att illustrera. Säg att vi dela med 5, 7 och 11. Det är viktigt att talen ej har gemensamma faktorer, alltså väljer vi primtal. Låt oss anta att resterna blir 2,3,4. Knepet består nu i att skapa ett sånt tal som vi söker på ett naturligt sätt. Det kan vi göra om vi tänker oss att det består av 3 delar som plussas ihop, eller lika många som talen vi dela med. Varje del består av ett tal som ger rätt rest när man delar med ett av talen, men 0 när man delar med de andra. Säg att vi ska bestämma 5-delen. Vi vill ha 0 när vi dela med 7 och 11, så talet bör vare en multipel av 77. Det råkar även ge resten 2 när vi dela med 5. Bravo! Nästa del, 7:ans, blir en multipel av 5*11=55. Här blir resten 6, så vi få leta lite till och vi finner att 4*55=220 ger rätt rest. Det sista talet bör vara en multipel av 5*7=35. Resten här blir 2, men om vi dubblar få vi 70, och nu blir det rätt rest. Vi få nu tillsammans 77+220+70=367. Finns det fler lösningar? Jomenvisst. Om vi gångrar ihop 5*7*11 få vi 385 och detta tal ger 0 i rest när vi dela med våra tal. Vi inser att vi få samma rester när vi lägga till en multipel av detta tal till vår lösning. Vi har tydligen hittat den minsta positiva lösningen med vår metod, men det är inte alltid man gör det och det är inte alltid man vill ha det heller. Vi kan skriva 367+n*385. Vi inser även att om vi vill använda samma tal för att lösa samma typ av problem kan vi räkna ut standardtal som ger resten 1 för alla. I vårt fall skulle vi få 3*77=231 ger rest 1 när vi dela med 5. 55*6=330 ger rest 1 när vi dela med 7, och 70*3=210 ger resten 1 när vi dela med 11. I vårt problem skulle vi då få 2*231+3*330+4*210=2292 som ger ett tal med de sökta egenskaperna. Nu var ju det lite stort, men vi kan ju dra av multiplar av 385. 2292=5*385+367. Känns bekant, eller hur? Efter den här lilla övningen som givit oss en inblick i den kinesiska tankesmedjan, kan vi tänka oss hur det gick till i det gamla Kina. Överkinesen får för sig att ett utomordentligt komplext och gruvligt problem ska lösas. Det kräver många delmoment och många siffror. Han rusar sta till sina parallellkineser och ger samma problem till sin mod 17, 19, 23 osv -kines. De sätter alla igång o räknar, men med betydligt mindre tal och därför betydligt snabbare och är snart klara, varpå de som barnen på ett dagis skriker ”färdig” och visar resultatet för överki(ne)sen som sammanfattar det hela till ett totalresultat. Idag är de små kineserna ersatta av parallella kretsar- tillverkade i Kina.

Nu kommer problemet: Åke Lundin har varit på samkväm med bla Mikael Persbrandt, prinsessan Madelaine, Jan Guillo, Lena Ph, Petra Mede samt några övriga kändisar, aliens, vampyrer och 08-or. Det var livat, för livat faktiskt. När han vaknar nästa morgon inser han att han blivit sextrakasserad ett antal gånger. Då han pga posttraumatisk stress inte kan räkna längre än till 5 – sex är blockerat- tillkallas det kända supersnillet Sherlock B Holmes ( B står för Bengt) att leda utredningen. Det visar sig att det var ett udda antal trakassöser, och om man delar dem i grupper om 3 blir resten 2, vilket även är fallet om man delar dem i grupper om 5. Dessutom är antalet ett primtal som ligger mellan 20 och 100. Kan Du hjälpa Bengt?

Bakgrund: Tâm förklarade på lektion 2 hur man löser uppgift nr 1. En sadistisk mattelärare passerar en frysande och hungrig hemlös på knä i snön på stadens gator efter Fredrik Reinfeldt, Anders Borg och Gunilla Carlsson som ej bevärdigat henne med en blick. Matteläraren lovar stackaren 500:- om hon lyckas lösa problemet inom en kvart, sålunda framställandes sig själv som både god och pedagogisk, men säker på att han kommer att komma undan utan att offra en krona. Översköljd av tårar och förvirrad och med samma ångest som en teknolog på en tenta befinner hon sig där, när den store filantropen, människovännen, supermannen och välgöraren Åke Lundin passerar. Han klappar henne ömt på huvudet och frågar hur det är fatt. Hon förklarar sin situation och Åke är inte sen att ge henne en mycket enklare och elegantare lösning än den hans vidrige kollega kan leverera(Åke är hårdare mot de hårda- ett gammalt ordspråk i djungeln) . Dessutom får hon ytterligare 1000 kronor av denne ytterst vänlige och förträfflige gode man. När Du nu torkat tårarna efter denna rörande och uppbyggliga berättelse kan Du nedan läsa lite om de praktiska detaljerna bakom allt. Kan vara bra att kunna- man vet aldrig när man kan bli hemlös i välfärdslandet Sverige!

ENKLA INVERSER

På en mattelektion ges följande tal: 16x=26(mod42). Vi kan tolka detta som 16x+42y=26, och detta i sin tur leder till det förenklade 8x+21y=13 eller 8x=13(mod21). Det här känner vi igen som en diofantisk ekvation som kan lösas mha euklides algoritm och en del jobb med densamma. Det finns ett alternativt sätt att tänka.
Titta på denna uppställning.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 =n
1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1 =10^n(mod17)

Antag nu att vi vill lösa ett liknande problem som ovanstående. Säg 5x=7(mod17). Om det var vanliga tal skulle vi naturligtvis dela med 5 för att få fram x. Ett annat sätt att uttrycka samma sak är att säga att vi gångrar med inversen för 5. Finns det inverser i vårt modulära system? Ja visst 17 finns det! Vi kan notera att varje tal i modulen kan skrivas som en potens av 10 (som kallas för generator). För att gångra 2 tal är det bara att lägga ihop potenserna, precis som med vanliga logaritmer. Vi noterar även att 10 upphöjt i 16 är 1- vilket fö är ett exempel på Fermats lilla sats. Om vi ska lösa problemet ovan borde vi alltså börja med att skriva x=7*5^(-1)(mod17). Så vad är inversen till 5? Vi kollar i tabellens undre rad och ser att ovan 5 står en 7:a. Det motsvarar alltså potensen för 10. För att komma fram till 16 behöver vi lägga till 9, och i tabellen ser vi nedan 9 en 7:a. Det stämmer! 7*5=35=1(mod17). Alltså 7*5x=x=7*7(mod17)=15(mod17). Nu kan Du ta itu med det första problemet. Du kan ju ta hjälp av följande:
>>> for i in range(13):
… print(i,2**i%21),

(0, 1) (1, 2) (2, 4) (3, 8) (4, 16) (5, 11) (6, 1) (7, 2) (8, 4) (9, 8) (10, 16) (11, 11) (12, 1)
>>>

Vi har här kört med 2 som generator och modulen är naturligtvis 21. Vi ser att vi är tillbaka till 1 redan vid 12:e potensen. Alltså har inte alla tal mellan 0 och 21 invers, närmare bestämt de som har gemensamma faktorer med 21. Det är den mer allmänna varianten av Fermats lilla. Men 8 har det! Glöm inte att kolla svaret!
LYCKA TILL!

Åke Lundin och den kända bloggaren och kulturskribenten Tanja Bergkvist är ute i skogen och plockar svamp. Närmare bestämt genustrumpetsvamp. (Den kan faktiskt anrättas, om man bara förväller den ordentligt, och kokar bort det farliga genusgiftet som dessutom har en vidrig bismak.) När de kommer hem finner de att om de var och en gångrar sin födelsedag med den antal svampar de plockat och lägger ihop, så fås den vackra diofantiska ekvationen 3x+7y=666. Som synes har de båda sjävklart födelsedag på dagar med lyckotal. Dessutom har de båda plockat det antal som ger minsta möjliga skillnad mellan resp antal. Hur många svampar ha de plockat tillsammans?

Kombinatorik

På klubben sitter grabbarna o språkar. Ryktet har gått att en babbe tagit sig ett etniskt svenskt namn, Larsson. Man är (järn)rörande eniga om det olämpliga i detta, särskilt som hon dessutom fått en ministerpost. (Rolighetsminister i republiken Gotland). Man provar att ringa på telefon, men Babben har börjat med telofonsex och hör inte vad de säger. Man beslutar sig för att göra ett hembesök. Man klär på sig ytterkläderna enligt dagens mode som har bytt ut spanskrör mot järnrör. De 12 apostlarna har att välja mellan 5 rör storlek XL, 4 rör L, och 3 rör M. Uppgift1:På hur många sätt kan dessa fördelas?
Pojkarna får 7ts av en av deras mammor och ringer på dörren hos Babben. Dessvärre har hon satt sin telefon i vibratorläge, samtidigt som hela hennes fan club ringer upp henne. Hon ligger alltså och sprattlar som en epileptisk duracellkanin och kan inte gå och öppna. Besvikna konstaterar pojkarna att det inte blir nåt ikväll. Mamman har farit sin kos, så de får gå hem. Dessbättre är det inte så långt. Man ska helt enkelt gå 4 huslängder i nord-sydlig rikting och 7 huslängder i öst-västlig riktning i ett rektangulärt gatunät. Nu uppstår en diskussion om vilken väg man ska ta.Uppgift 2: På hur många sätt kan man välja färdväg?
Bild: Kombinatorik På klubben sitter grabbarna o språkar. Ryktet har gått att en babbe tagit sig ett etniskt svenskt namn, Larsson. Man är (järn)rörande eniga om det olämpliga i detta, särskilt som hon dessutom fått en ministerpost. (Rolighetsminister i republiken Gotland). Man provar att ringa på telefon, men Babben har börjat med telofonsex och hör inte vad de säger. Man beslutar sig för att göra ett hembesök. Man klär på sig ytterkläderna enligt dagens mode som har bytt ut spanskrör mot järnrör. De 12 apostlarna har att välja mellan 5 rör storlek XL, 4 rör L, och 3 rör M. Uppgift1:På hur många sätt kan dessa fördelas? Pojkarna får 7ts av en av deras mammor och ringer på dörren hos Babben. Dessvärre har hon satt sin telefon i vibratorläge, samtidigt som hela hennes fan club ringer upp henne. Hon ligger alltså och sprattlar som en epileptisk duracellkanin och kan inte gå och öppna. Besvikna konstaterar pojkarna att det inte blir nåt ikväll. Mamman har farit sin kos, så de får gå hem. Dessbättre är det inte så långt. Man ska helt enkelt gå 4 huslängder i nord-sydlig rikting och 7 huslängder i öst-västlig riktning i ett rektangulärt gatunät. Nu uppstår en diskussion om vilken väg man ska ta.Uppgift 2: På hur många sätt kan man välja färdväg?

KOMBINATORIK

De 3 lärarna Åke, Bengt och Tâm har fått KTH’s hederspris för utsöktaste undervisning som består av 20 kakor att dela på.
Uppgift 1: På hur många sätt kan detta göras?
Uppgift 2: På hur många sätt kan detta göras om ej alla kakor behöver gå åt?
( Detta kan ha flera orsaker- Åke vägrar äta kakor med kött i, Bengt är allmänt blyg och försynt, och Tâm är liten i maten-hans mamma gör mycket godare mat än den som äts av neandertalarna i nordliga regioner)
Ledning: Introducera kakmonstret Erik som slukar allt som andra ej hunnit rädda undan.

En tid senare ska de 3 matematikerna Åke, Bengt och Tâm återigen dela på ett gäng kakor, denna gång 27 st. Men det är ej vilka kakor som helst. De har växt på det fina kakträdet som växer i en kruka på institutionen och vars frön Tâm (s mamma) tagit med sig från Vietnamnam. De har varje dag vattnat plantan ömsint och gött den genom att kissa vid dess fot. De har tom givit de enskilda frukterna=kakorna egna individuelle namn, ömsint och orginellt valda bland de 27 första naturliga talen så att ingen har samma som de andra.
Uppgift 3: På hur många sätt kan dessa fördelas mellan dem?
Uppgift 4: På hur många sätt kan dessa fördelas mellan dem om inte alla kakor behöver gå åt?
(Tänk på det stackars hungriga kakmonstret!) Ledning: Istället för att räkna själv kan du låta en stirlingmotor göra jobbet åt dig:

http://austinmohr.com/home/?page_id=431

Bon appetit!
Bild: KOMBINATORIK De 3 lärarna Åke, Bengt och Tâm har fått KTH’s hederspris för utsöktaste undervisning som består av 20 kakor att dela på. Uppgift 1: På hur många sätt kan detta göras? Uppgift 2: På hur många sätt kan detta göras om ej alla kakor behöver gå åt? ( Detta kan ha flera orsaker- Åke vägrar äta kakor med kött i, Bengt är allmänt blyg och försynt, och Tâm är liten i maten-hans mamma gör mycket godare mat än den som äts av neandertalarna i nordliga regioner) Ledning: Introducera kakmonstret Erik som slukar allt som andra ej hunnit rädda undan. En tid senare ska de 3 matematikerna Åke, Bengt och Tâm återigen dela på ett gäng kakor, denna gång 27 st. Men det är ej vilka kakor som helst. De har växt på det fina kakträdet som växer i en kruka på institutionen och vars frön Tâm (s mamma) tagit med sig från Vietnamnam. De har varje dag vattnat plantan ömsint och gött den genom att kissa vid dess fot. De har tom givit de enskilda frukterna=kakorna egna individuelle namn, ömsint och orginellt valda bland de 27 första naturliga talen så att ingen har samma som de andra. Uppgift 3: På hur många sätt kan dessa fördelas mellan dem? Uppgift 4: På hur många sätt kan dessa fördelas mellan dem om inte alla kakor behöver gå åt? (Tänk på det stackars hungriga kakmonstret!) Ledning: Istället för att räkna själv kan du låta en stirlingmotor göra jobbet åt dig: http://austinmohr.com/home/?page_id=431
Du kan även använda Walpha skriv bara stirling2 (a,b) i fönstret.
Bon appetit!

ex08

Övn 8 kommentarer.

1. När det gäller att fylla i tabellen görs detta enkelt. Det första man gör är att kolla in vilket element som är enhet. Man ser direkt att i raden för a så står c under c, dvs den landar på sig själv. Alltså är a enhet.  Resten är enkelt nog. Vi vet att en grupp tabell är en latinsk kvadrat, dvs en tabell där varje element förekommer exakt en gång i varje rad o kolumn. Det blir som att lösa ett sudokupussel och lika roligt.

a) Att gruppen är abelsk innebär att den är kommutativ. Det ser man lätt i tabellen. Om den är abelsk måste ju tabellen var symmetrisk kring diagonalen så att korsningen mellan rad x o kol y ger samma svar som mellan y o x.

b) Tja, det var ju a det…

c)Titta i tabellen- kolla var resultatet a står -de element som korsas där är varandras inverser.

d) Ordningen för ett element h bestäms av det n som gör h^n=a(enhetselement). Det är bara att prova på för varje element genom att via tabellen gångra det m senaste resultat tills man landar på a.

e) Här är det bara att använda tabellen. Parenteser behövs ej, då ett av exiomen säger att operationen ska vara associativ.

2. Givet en grupp med 1,a,b,c där 1:an är enhet.

Så följer ett gäng uppgifter som i sin tur har till uppgift att vänja oss vid att manipulera symboler enligt vissa givna spelregler. Ofta vet vi inte riktigt hur vi ska börja, ovana som vi är, men det är bara att leka på tills man ser hur man ska få fram svaret.

a)  Vi får veta att det finns  x så att  ax²=b och x³=1 och vår uppgift är att finna dessa x. Genom att gångra den första relationen med x från höger få vi a=bx. Detta ger direkt x=b^(-1)*a

b) Nu gäller  (xax)³=bx och x²a=(xa)^(-1). Den andra relationen kan gångras med xa från höger vilket ger x²axa=1. Det ger x*(ax)²=1 -aha en invers till x! Vi skriver ut relation 1: xaxxaxxax=bx. Gångra från höger m ax o få xaxxaxxaxax=bxax. Det vi förkorta till xaxxax=bxax mha vår nyfunna invers. Vi kör en gång till och får xaxxaxax=bxaxax. Ännu enklare-xax=b. Varför ändra en vinnande stil? xaxax=bax eller 1=bax. Men detta ger ju x=(ba)^(-1)=a^(-1)*b^(-1)

c) Visa att bac=a^(-1)=>cab=a^(-1). Den första relationen ger baca=abac=1. Vi få bacab=b.  cab=(ba)^(-1)*b=a^(-1)*b^(-1)*b=a^(-1)

d) Visa (abc)^(-1)=abc=>(bca)^(-1)=bca. aabcabc=1,abcabca=a,bcabca=1 och de va de.

e) Visa a³=1=> a har kvadratrot.  a=a*a³=a⁴. Dett ger att a² duger gott.

f) Visa b²ab=a^(-1) => a har kubikrot. Gångra m a o sen b från höger. b²abab=b. babab=1. Det ger bababa=a=(ba)³.

3. U(Z8),.)= 1,3,5,7  och motsv Z14 =1,3,5,9,11,13

Z8:Vi kolla första 3an. 3,9=1-3,1,3,1 nähä. 5an då: 5,1,5,1—7,1,7,1 inte heller.

Z14: 3,9,13,11,5,1,3,….. jojomen. Vi har hittat en generator iaf.

4. Z13 utom 0:an är cyklisk, o alla generatorer är önskade.

vi kollar : 1,2,3,4,5,6,7,8,9,10,11,12.

1,2,4,8,3,6,12,11,9,5,10,7,1…den va OK notera att 12 även är -1, o därefter följer samma rad med omvänt tecken.

1,3,9,1,3 nä… en period på 3, delar 12

1,4,3,12,9,10,1,… Redan efter 12 ana vi ugglor i mossen, eftersom det motsvarar -1 och efter lika många element är vi på (-1)²=1.

1,5, 12,8,1… samma sak här, 12 är minus ett och varnar tidigt

1,6,10,8,9,2,12, nu kan vi det här, 12:an signalerar hälften av perioden o den räcker

7:an är 13-6, 6 ha vi provat. Vi kommer att få som för 6, de jämna potenserna blir samma, di udda blir lite annorlunda. Vi få i princip en spegling av det vi gjort i fortsättningen.
6.100 pers m olika namn får glutta i lika många numrerade lådor, och i var och en ligger namnet på en av personerna. Alla namn är med, ett namn i var låda. Var och en får titta i 50 lådor, och om var och en lyckas hitta sitt namn får de massor av pengar, annars inga. De får ej tala med varandra efter titten. Hur ska de bära sig åt?
Ser lite okul ut att börja med. Att titta på måfå borde ge chansen 0,5 för var och en, och 0,5^100 är ju ej så mycket…

Knepet är enkelt om man läst om permutationer. Vi kan ju tilldela vart namn ett nummer och i så fall är upplägget en typisk permutation. Vi vet att dessa kan skrivas på cyklisk form. Antag nu att du börjar med den lådan som har samma nr som ditt namn och sen går till den låda som har numret som motsvarar namnet i lådan osv. Om nu cykeln du hamnat i är mindre än 50 så är du ju hemma. Så vad det handlar om är sannolikheten för att en godtyckligt vald permutation har cykler som är mindre än 50. Den är betydligt större. Läs gärna mer här
http://gurmeet.net/puzzles/100-prisoners-and-100-boxes/

4 matematiker kliver in på en bar. Bartendern frågar: Vill alla ha öl?

Den första säger: ”Jag vet inte”

Den andra säger: ”Jag vet inte”

Den tredje säger: ”Jag vet inte”

Den fjärde säger: ”Ja”

Om du tycker det här var lika roligt som en matematiker har du förmodligen en diagnos.

Du kan titta här http://www.dsm5.org eller här http://thcc.or.th/ICD-10TM/1/kf00.htm

ex09

Ö9

1. Vi ska titta på (U(Z64),.) och visa att g^32=1. Det här är fundamentalt-och enkelt! Till att börja med kan vi se att antalet element, dvs grpn:s ordning är 32, det är ju helt enkelt de element som är udda. Uppenbarligen ha vi g^ordning=1. Vi ha ju tidigare tittat på ordning av olika element och sett att denna alltid går jämnt upp i gruppens ordning. Vad beror det på? Ja, om vi se på ett element och det potenser så genererar de en undergrupp och enligt käre gamle laplace så är ordningen till en undergrp alltid en delare till hela grpns ordning. Men ordning är ju definierat som den potens som ger g^o=1. Gör vi om detta fler ggr så blir det fler 1:or…

Vi kan även kasta en tanke till Fermat och hans lilla sats. Den återkommer senare i kursen och säger i princip att a^p-a är jämnt delbart med p om p är primtal. Vi kan även skriva detta som a^(p-1)=1modp. Men i grpn U(Z(p),.) finns ju just p-1 element.

3. Lite som uppg 1, ett enkelt tal och laplace i bekgrunden. (Hoppsan, stavade fel, det var faktiskt inte meningen, men kan ju va bra för den som vill skriva ebrev till bengt) . 2 delgrupper till  G har ordning 39 och 40 och vi vill veta minsta möjliga ordning för G =|G|.  Vi vet ju att 39 o 40 är delare till |G| och minsta tal blir då mgm(39,40) vilket naturligtvis är produkten av dessa tal enär de äro relativt prima.

4.  Ha! Laplace igen! Det här bxörjar ju bli larvigt, nog är CL-studenterna klüftigare än så! Vi ska se att en tabell ej kan füllas i så att det blir en grptabell. Lätt inses att de fyra rutor som fyllts i i övre vänstra kanten är en grp. Då måste det va en undergrp m ordn 2. Men tabellen är ju 9*9  o inte f-n går 2 jämnt upp i 9! Rena grundskolan…

6.Vi ha f=x⁵+(5/3)x⁴+(10/3)x³+(4/3)x²+(1/2)x. Dessutom t=x²+x+1/2. Vi ska skriva f på formen f=b2t²+b1t+b0. De olika b-na är polynom. Formuleringen ser lite konstig ut till vi inser att de här är ju samma som vi gjorde i början av kursen, när vi skrev talen i olika baser. Här ha vi basen t och de olika b-na blir koefficienter, tydligen polynom m graden 1 eftersom t har grad 2. Vi gör nu på samma sätt som när vi skrev tal i nya baser, dvs dela o ta rester efter hand. (Notera att problemet givits i basen 1,x,x²,x³,….) 
Vi få x⁵+(5/3)x⁴+(10/3)x³+(4/3)x²+(1/2)x=Vi få x⁵+(5/3)x⁴+(10/3)x³+(4/3)x²+(1/2)x=(x²+x+1/2)(x³+(2/3)x²+(13/6)x-7/6)+(7/12)(1+i)
mha Wα. (Räkna gärna för hand)

nästa steg blir  (x³+(2/3)x²+(13/6)x-7/6)=(x²+x+1/2)(x-1/3)+2x-1

Nu är det lätt, den första resten är ju b0 o den andra är b1

=>f=(x+1)*(7/12)+t*(2x-1)+(x-1/3)*t²

7. Gaussiska heltal är lite underrepresenterat i boken, det finns på nätet så klart, men tja, det blir ju lite småplottrigt… Uppgiften går ut på att faktorisera  2+i, 3+i, 4+i,5,7,4+3i,15,7-i,8+i. Vi kör lite efterhand, så få principerna klarna. (2+i) går ej bra-är primtal. 3+i är en annan sak- vi gångrar m konjugat och får (3+i)(3-i)=10=2*5=(1+i)(1-i)(2+i)(2-i). Aha! Nu kan vi arrangera om lite o få (1+i)(2-i)=3+i. Vi se nu varför det ej gick m 2+i -det konjugatet ger ju bara ett primtal. Nästa är 4+i. Men detta konjugat ger 17, o de va 17- primtal mao. 5=(2+i)(2-i). 7 nä. Vi kan ana en regel här- ett vanligt primtal som är =1 mod4 går bra att yxa upp, men ej ett som är =3mod4. Det beror ju på att varje kvadrat mod 4 antingen blir 1 el 0. När vi kör konjugat blir det summa 2 st 0,1,2 möjligt. Så det blir bara 1:an kvar.
Vi ångar på:7-i: Konjugat  (7-i)(7+i)=50=2*5*5=(1+i)(1-i)(2+i)²(2-i)² . Vi få pillra lite, helt klart. (2+i)²=3+4i. (2-i)²=3-4i. (3+4i)(1-i)=7+i, ( 3+4i)(1+i)=-1+7i, (3-4i) (1+i)=7-i      äntligen rätt!! Så återstår 8+i o vi få (8+i)(8-i)=65=5*13=(2+i)(2-i)(3+2i)(3-2i). Nu se vi att (2+i)(3-2i)=8+i.

8 Vi ska bestämma sgd(21+37i,26+12i) för gaussiska tal och sen hitta en linkomb a o b så att a(21+37i)+b(26+12i)=densamma.  Åh, här kommer PTSD från kursens tidiga skede åter, och inte nog med det! Förut hade vi vanliga tal, nu kommer di där kônstige gaussiske. Men det är bara att ta ett djupt andetag o börja. Vi få väl börja med euklides. Det blir lite annorlunda här. Du minns kanske att man delade o tog rester, och var man riktigt fiffig kunde man istället för att ta en stor positiv rest ta en liten en och då få snabbare o enklare räkningar.  Här ha vi inte 2 riktningar, + o -. utan vi kan spreta som vi vill i planet o det är uppenbarligen dax att ta till fiffighetsprincipen o köra den rakt av.  Först kolla vi vilket av talen som är störst, och där använda vi normen som är summan av kvadraterna på real och imaginärdel. Det är uppenbart det första talet, eftersom 372 kommer att stjäla showen från alla andra. Nu prova vi. (21+37i)/(26+12i)=(97+71i)/82. (ja,ja j har väl fubbat lite m Walpha, annars vet du hur man gör-man förlängar med konjugatet så att nämnaren blir reell) . Vårt svar ser inte så bekvämt ut, men 97 0 71 är ej alltför olika, så vi kan väl höfta till med (1+i).

21+37i=(1+i)(26+12i)+(7-i); (26+12i)/(7-i)=(17+11i)/5. Nu kan vi se att 17+11i ligger i samma grannskap som 18+12i, så vi kan väl prova med 3+2i.

26+12i=(7-i)(3+2i)+(3+i); (7-i)/(3+i)=2-i.  Ingen rest! Vårt svar blir 3+i.

Nästa var den där ekvationen. Vi har tydligen 3+i=(26+12i)-(7-i)(3+2i)=(26+12i)-(3+2i)[(21+37i)-(1+i)(26+12i)]=-(3+2i)(21+37i)+(26+12i)(1+(3+2i)(1+i)) vilket ger a o b.

ex10

KRYPTERING

Ett problem vid kryptering är att de vanliga metoderna bygger på en hemlig nyckel som bara avsändare och mottagare vet om. Problemet är utbyte av nycket- hur ska det göras på ett enkelt och säkert sätt? Ett sätt redovisas här- det bygger på att man kan lämna ut en krypteringsnyckel utan att för den skull avslöja hur meddelandet ska dekrypteras. Mycket användbart i vår tid.
Låt oss börja från början. Fermats lilla sats. Den säger att a^p=a mod p om p är primtal. (a är naturligtvis ej multipel av p). Den kan även skrivas a^(p-1)=1 mod p. Den står visad i boken, intressant exempel på induktion över a, men vi kan inse det mycket enklare. Vi ha ju redan sett att g^n=1 där n är ordningen för en grupp. Men om vi räknar modulo p och men ggr (0 får ej vara med) så är ju ordningen (p-1) och saken är klar.( Eftersom a^0=1, så inser vi att a^n=a^(n+p) mod p.)
Exempel 2⁵=32=2 mod 2
Det här går att generalisera så att vi få en formel som gäller när vi ej ha primtal. Det är nu Euler som får ge namn åt densamma: a^φ(n) =1 mod n. För φ gäller φ(nm)=φ(n)φ(m). (Läs wikipedia Euler’s totient or phi function). Observera även att φ(n) är antalet tal som är relativt prima n, dvs samma som |U(Zn)| som vi stött på tidigare. Antag att vi ha n=pq där p o q är primtal. Då få vi φ(n) =(p-1)(q-1). Exempel: Tag n=15=3*5. Det ger φ(n) =(3-1)(5-1)=2*4=8. Kolla 3⁸=81*81=6*6=1 mod 15. Stämmer! Vad ska nu allt detta va bra för? Jo, krypteringen går till så här. Man anger – i detta fall- talet 15 och ett annat tal e som tex kan va 3. Man säger åt avsändaren att ta meddelandet a och ta det upphöjt i e mod n, dvs a^e mod n. Detta är då det krypterade meddelandet. Säg nu att meddelandet är 7. Vi tar 7³ mod 15 och får 49*7=4*7=13. Nästa steg blir av dekryptera. Eftersom vi vet faktoriseringen, dvs φ(n) kan vi klura ut ett hemligt tal d, som är gjort så att e*d=φ(n)*k+1. Vi kommer ju då att få tillbaka meddelandet i klartext, eftersom det blir 1 för alla multiplar av φ(n). Vi har alltså att lösa problemet ed=n*φ(n)+1. Det här är ju en diofantisk ekvation typ ex-fy=1 där vi är intressaerade av x och e o f är kända. Går mha metoderna i början av kursen o görs sålunda i exemplet i boken. Eftersom e o d är varandras inverser kan vi fubba lite o skriva inverse 3 mod 15 i wolframalpha. I vårt ex ha vi 3*d=8*k+1, och det var ju ej svårt att se att d=3 duger fett bra. Ok, vi provar igen då. Vi ska ta det krypterade meddelandet upphöjt i d, dvs 13^3=(-2)^3=-8=7 mod 15. Det funkade!
Vi ta då ett avslutande exempel. En nyvorden farfar får veta att barnbarnet har längden 51 cm. Dessutom brukar ju barn väga ca 3 kg. Farfar publicerar nu nyckeln n=51 och e=3. Dessutom finns en kodlista : 2=det blev en flicka, 3=det blev en hen, 4=det blev en pöjk, 5=vikt 3570g, 6=vikt 3190, 7=vikt 3290, 8=faderns känslor är all over the place, osv. Eftersom farfar vill va lite diskret men ej kan hålla sig skickar han ut meddelandena 13 och 37. Knäck farfars krypto och ring Aftonblodet!

GRUPPVERKAN: Stabilisatorn är Banan är  Burnsides lemma: antal banor =

Även |G|=|Gx|*|Gix| Lite krångel m formlerna o bloggverktyget. Gix beyder G m x som index. 

Det är inte bara ni som grunnar….http://math.stackexchange.com/questions/165184/burnsides-lemma

Nu till övningen:

1. Vi ska kolla gruppen för en oktaeder. Vi kan lika gärna titta på en kub eftersom de år likvärda. En kub har 6 sidor, var och en kan vara nederst. Den kan sedan roteras runt i 4 olika positioner, och det ger svaret 6*4=24. Vi ska nu söka storleken för stabilisator och banan för dels hörn och dels mittpunkt på yta. (Jag vill ha en stor banan). Tag en punkt först. Här kan vi snurra i 4 olika lägen. Det är 4 olika g-operationer och vi är kvar där vi är. Det måste va stabilisatorn.  Alltså svar 4. Mha produktformeln få vi bananornas tal till 6. Vid närmare eftertanke så blir det så även om vi tar grunddefinitionen. Det finns ju 6 olika hörn som vi kan komma till mha gruppoperationer. När det gäller mittytorna så ha vi 8 st, o det blir bantalet (min banan!) och gångerformel ger 3 för stabilisatorn.

2. Nu tar Pelles bekymmer. Han hade kvadratiska brickor och 3 färger (rgb) och frågan var hur många väsentligt olika kombon som kan fås. Om vi låter plattan  ligga still få vi uppenbarligen  3⁴=81 varianter. Men vi kan ju vrida plattjäveln, och då kommer en del att bli samma.  Om vi kalla vridningarna för g0,g1,g2 och g3 (varje vridning är 90⁰ till moturs tex) och tänker efter hur många som blir samma efter resp vridning få vi för g0: 81, g1:3 (det är di med bara en färg) och för g2: 3² -varje hörn hamnar ju mitt emot sig självt, så det blir ju di som har motsatta hörn likfärgade, och det kan ju göras på 3*3 olika sätt. g3:samma som g1. dvs 3. Nu Burnar vi lite: 1/4(81+3+9+3)=24. Det verkar ju va svaret på a. Om vi vänder på tingesten är det ju tji skillnad om baksidan är likadan, om ej blir det dubbelt upp. C-frågan handlar om k färger. vi behöver ju bara upprepa snacket o får 1/4( k⁴+k+k²+k).

3.Detta är ett problem som suger… 6 sugrör i en tetraeder, o d blir Burnside igen såklart. Den här gången blire lite mer att vrida o vända. Om vi tänker efter så har en tetraeder ( vad kommer det ordet ifrån förresten?- är det för för att man osar 4 ggr så många eder som vanligt?) 4 olika sidor som vi kan sätta i botten. Dessutom har man för var och en av dessa 3 olika lägen om vi snurrar kring mitten på bottenplattan.  Det blir 12 olika element i vår lilla grupp. (Lite som Jesu lärjungar) Vi kan ju notera dessa me dubbelindex, typ Gsr. -(sida, rotation) . Nu kollar vi : Om vi ha G00 så är det uppenbart k⁶ olika. Om vi ha G0r där r>0 så gäller att di andra sidorne än botten ska ha samma färg inbördes, och vi få 6² olika för var o en av dem, dvs 2*6².  Titta vi nu på G1r så gäller i princip samma- botten har sin färg och di andra 3 har samma inbördes, vilket ger 3*k². Detsamma borde ju gälla för G2r och G3r och vi får då om vi summera 1/12(k⁶+2k²+3*k²+3*k²+3*k²)=1/12(k⁶+11k²)

4. Hemligt-vi ska köra m krypto som har  n=77.

a. Vi ska förklara varför det ej går bra m e=45. Hm. Vi kanske ska knäcka lite chiffer först. Vi ser att 77=7*11. För att göra vår phi-funktion så ska vi gångra (7-1) med (11-1) vilket blir 6*10=60. Om vi kollar på 45 så gäller det alltså att finna d så att 45e=60k+1. Njä, det går ju inte, e och phi måste vara relativt prima o det är de ganska flagrant inte. b. Nu väljer vi e=13 (primtal, de bruka ju var relativt prima m rätt mye) . Vi ska då välja ett bra d. Jaha, 13d=60k+1. Det kan vi lösa mha euklides algoritm (se boken för exempel) den som blir trött av att bara tänka tanken kan ju stega fram 60 år gången tills det blir träff- kan ju ej ta mer än 60 varv. Allra enklast o fubbigast blir att skriva in  ” inverse 13 mod 60″ i wa. Vi får 37.

c. Vi ska kryptera a=3. Jaha. 3^13=38 mod 77. Jaja, fuskade m wa. Om vi ska typ handräkna få vi 3²=9. 3⁴=81=4. 3⁸=16. 3^(8+4+1)=16*4*3=192=38 mod 77.

d. Dekryptera a=2. Tja, dekryptering gör vi mha d och det ha vi konstaterat är 37. Det handlar om 3^37 mod 77=51 om vi fuskar m gamle Wolfram. (Det är snubben man gärna sitter bredvid på tentan. Varför ska KTH va så krångligt förresten- det står ju alltid Inga hjälpmedel – wolframalpha borde döpas om till Inga så var saken klar). Ska vi handräkna få vi pss som ovan 2²=4, 2⁴=16, 2⁸=256=25. 2^16=625=9. 2^32=81=4. Vi få nu 2^( 32+4+1)=4*16*2=16*2=128=51 -oj, stämde ju!

5. Mera hemligt- Du har väl mörka glasögon? n=265 och e=37.  Vi ska dekryptera b=2. Vi kollar faktorerna till 265=5*53. Phi=4*52=208. Vi ska alltså hitta d så att 37d=208k+1.  Lös ekv mod 37, dvs 0=-14k+1 mod 37. Eller 37m=-14k+1, tag mod 14, dvs 9m=1 mod 10, m=9, 333=-14k+1,k=-11. 37d=-11*212+1=-2331. d=-63=212-63=149. Detta svar få vi även av wofflan om vi skriver in ”inverse 37 mod 208″=>45 chez lui. Nu är vi nära… nåja, det som återstår är 2^149 mod 265. Vi skaffar först ett fusksvar  2^45 mod 265=>147. Så räkna vi på :2²=4, 2⁴=16,2⁸=256=-9, 2^16=81, 2^32=6561=201=-64  stöööön. Så få vi då till sist 2^(32+8+4+1)=-64*-9*16*2=576*32=46*32=39²-7²=1521-49=1472=5*265+147.

6. n=1333 =31*43 (Vem skvallrar?) e=143. Oj, va ere här? Det är bara slavgöra o sånt ha vi redan gjort ovan. Vi ska kryptera 718, 719 vilket är ”lätt” gjort mha offentlig nyckel, men sen ska vi dekryptera o kolla därtill. OK då, fast kanske inte alla räkningar i detalj. Vi gå te betjänten wofflan och skriver ”718^143 mod 1333” vilket ger 707. Sen ”719^143 mod 1333” och får 615. Sen vare dekryptera: 1333=31*4707^467 mod 13333 =>phi=30*42=1260. Hitta d så e*d =143d=1260k+1. Fråga wofflan igen: ”inverse 143 mod 1260” vilket ger 467. Jaha. Då kolla vi då:  ”707^467 mod 1333” ger 718- fantastiskt! Resten fixar Du nog själv. Det kan ju va lite fuskigt att köra så där m wofflan, men det ger ju snabbare o tydligare överblick över processen. Dessutom kan vi konstatera efter allt vårt lidande att Bengt knappast kan ge uppgifter av den digniteten på en KS med den begränsade tiden som finns där.

7. Här ska vi kolla 63 mha fermat-test. Fermats lilla säger ju att a^(p-1)=1 mod p om p är primtal.  Om p ej är primtal så gäller det oftast ej. Men det finns tal som är så jävla elaka att likheten gäller för alla a trots att de ej är primtal. Det kallas för carmichaeltal o finns att läsa om på nätet. Vi kan alltså ej va säkra på att p är primtal även om vi kollar för många a, däremot kan vi vara säkra på att a ej är primtal om likheten ej gäller.  Men nu till talet. tag a=2 tex o kör: ”2^62 mod 63” ger en 4. Alltså är 63 ej primtal. Om vi fått en 1:a hade vi fått prova med ett annat a.

8. 43^139702 mod 101. Det var det. Ser ju lite krångligt ut om vi ej ha wofflan att luta oss mot. Men 101 är primtal vilket ger phi=100, och det betyder att 43^139700=1 mod 101. Det betyder att det är bara 43² =1849 kvar. Det var ju inte så svårt. 18*101=1818 så vi bör få 31. Allt detta är i princip möjlig huvudräkning.

 grf

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s