moduliräkning (på högskola)

Om du t ex tittar på tvåpotenserna 2, 4, 8, 16, 32, 64 o s v så blir deras rester när du delar med 7 i tur och ordning 2, 4, 1, 2, 4, 1 - siffran 5, exempelvis, dyker aldrig upp bland resterna. Heltalet 2 har alltså inte egenskapen att alla rester dyker upp bland dess potenser. Vilka heltal fungerar?

Tanken här är att du ska nöta in räkneregler för kongruenser.

Du ska undersöka vilka heltal, g, mellan 0 och 6, som upphöjt till k ger samtliga siffror mellan 1 och 6 (m) för $g^k \equiv m (\mod 7)$

Om du testar g=2 (dvs $2^1,2^2,2^3...$) kommer du få en följd 2,4,1,2,4,1,2,4,1 osv.. Du kommer upptäcka att du aldrig landa på 3, 5 eller 6.

Om du däremot testar 3 eller 5... Går det att formalisera?

Så, they were right. Det är roligt när man har fattat problemet.

Vi testar alltså alla tal mindre än 7 upphöjd i alla potenser mindre än 7.

$$\begin{gathered} 0^{1...6}\to nej \\ {1}^{1...6}\to nej \\ {2}^{1...6}\to nej, som uttret av er två \\ {3}^{1...6} \\ {3}^1{\equiv }_{7 }3 \\ {3}^2{\equiv }_{7 }2 \\ {3}^3{\equiv }_{7 }{3}^2*3=2*3{\equiv }_{7 }6 \\ {3}^4{\equiv }_{7 }{\left(3^2\right)}^2{\equiv }_{7 }{\left(2\right)}^2{\equiv }_{7 }4 \\ {3}^5{\equiv }_{7 }{3}^2*3^3{\equiv }_{7 }6*2{\equiv }_{7 }5 \\ {3}^6\equiv {\left(3^3\right)}^2{\equiv }_{7 }{\left(6\right)}^2{\equiv }_{7 }{1}^2=1 \end{gathered}$$

Med 4:or har vi resterna

$$\begin{gathered} 4^1\equiv 3 \left(mod7\right) \\ {4}^2\equiv 2 \left(mod7\right) \\ {4}^3\equiv 4^2*4 \left(mod7\right)\equiv 2*4\equiv 1 \\ {4}^4\equiv {\left(4^2\right)}^2\left(mod7\right)\equiv (2{)}^2\equiv 4 \\ {4}^5\equiv 4^2*4^3(mod7)\equiv 2*1\equiv 2 körd för vi redan har en tvåa \end{gathered}$$

$$\begin{gathered} 5^1\equiv 5 (mod 7) \\ {5}^2\equiv 4 \\ {5}^3\equiv 4*5\equiv 6 \\ {5}^4\equiv {\left(5^2\right)}^2\equiv 4^2\equiv 2 \\ {5}^5\equiv 5*5^4\equiv 5*2\equiv 3 \\ {5}^6\equiv {\left(5^2\right)}^3\equiv 4^3\equiv 1 \end{gathered}$$

Så 5:an fungerar.

$$\begin{gathered} 6\equiv 6 \left(mod7\right) \\ {6}^2\equiv 1 \\ {6}^3\equiv 6 \\ {6}^4\equiv {\left(6^2\right)}^2\equiv 1^2=1 körd \end{gathered}$$

Min teori: empirisk baserad kan man konstatera om ettan dyker för tidigt är vår följd förstörd?