Den fina tråden om modulär aritmetik

Förtydligande: Alla mina kortlekar har ett jämnt antal kort. (Mina "perfekta blandningar" är inte helt väldefinierade för kortlekar med udda antal kort.)

Insåg att jag gjort ett litet fel, ändrade min post. Blev det bättre nu?

Lånar tråden lite; vill dela med mig av ett (i min mening) ganska intressant problem, som jag stötte på ganska nyligen. Problemet är nog svårare än alla de som har EulerBoy postade. Och vid en första anblick har det ingenting med med modulär aritmetik att göra, men det är just därför jag tycker att problemet hör hemma även i en introduktion till ämnet, ty problemet visar (och jag hoppas att ni kommer hålla med) att modulär aritmetik är ett kraftfullt verktyg, som kan vara väldigt användbart även i något mer "vardagliga" situationer.

Nåja, uppgiften:

Säg att jag har en vanlig kortlek om 52 kort. Jag kallar följande sekvens av operationer en perfekt blandning:

1. Dela leken på mitten. Tag övre halvan (26 kort) av leken i höger hand, och nedre halvan i vänster hand. Håll dem med framsidan på korten nedåt.
   
2. Gör en vanlig riffelblandning; börja med att släppa ned kortet längst ner i delen du har i vänster hand på bordet, sedan kortet längst ner i höger hand, och så vidare, ett kort i taget, tills händerna är tomma.
   
   (Efter detta kommer t.ex. det kort som ursprungligen var underst i leken fortfarande vara underst, kortet som låg näst underst kommer nu vara tredje kort underifrån, kortet som låg överst ligger fortfarande överst, kortet som var 26:e kort uppifrån kommer ligga näst underst, och så vidare)

Nu till frågan:

a) Visa att om man genomför 8 "perfekta blandningar" efter varandra, så kommer korten komma tillbaka till sin ordningen de hade innan blandningarna.

b) Vad skulle det motsvarande siffra vara (det minsta antal blandningar man gör innan kortleken går tillbaka till sin ursprungliga ordning) om man istället gjorde "perfekta blandningar version 2", där man istället i steg 2) började med att släppa ner ett kort från höger hand?

c) Om man har en kortlek med jokrar, 54 kort, och gör perfekta blandningar (inte "version 2")?

d) Finns det en kortleksstorlek för vilken leken återgår till sin ursprungliga ordning efter 1279 perfekta blandningar, och inte före? I så fall, vilken?

e) (Bonus) Varför valde jag 1279 i inlägget innan? Finn alla kortleksstorlekar som gör att leken går tillbaka till sin ursprungliga ordning efter 1279 perfekta blandningar.

Lycka till!

Om ni ber snällt så ger jag gärna lite hints (via PM), men inte förrän ni fått tid att tänka lite.

(Not: a), b) och c) går förstås att lösa om man bara har antingen väldigt mycket tålamod eller lite programmeringskunskap och en vanlig dator, men det är alltså inte meningen; utan en "bättre" lösningsmetod (och minst en sådan använder modulär aritmetik) så kommer ni inte klara d) och e).)

"Vad blir den positiva resten då 2^2010 delas med 15?"

Notera att 16 = 2^4 och att 16 == 1 mod 15. Så vi försöker skriva vårt 2^(2010) som (2^4)^a * 2^b för lämpliga a,b. Notera att 2010 = 4*502 + 2 ger att 2^(2010) = (2^4)^(502)*2^2, men 2^4 == 1 så 2^(2010) == 1^(502)*2^2 == 4 mod 15. Så resten är alltså 4.

4k^2 + 4k är jämt delbart med 8 för alla heltal k. Alltså är resten alltid 1 för alla udda heltal a.