Delbarhet, del 2

I artikeln Matematikhörnan: Delbarhet definierades delbarhetssekvenser för naturliga tal. Delbarhetssekvensen för det naturliga talet $n$ består av talen $10^i\:(mod \: n)$ , där $i \in \mathbb{N}_{0}$ . I nedanstående tabell ser vi början av delbarhetssekvenserna för några tal:

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…

I föregående artikel märkte vi att alla av dessa sekvenser kommer att upprepa sig i något skede. För talen 2 och 5 beror detta på att något av talen är noll, och därmed kommer alla därpåföljande tal att vara noll, ty ifall $10^k \equiv 0 \:(mod \: n)$ , så är även $10^{k+m} \equiv 10^k10^m \equiv 0\:(mod \: n)$ .

De övriga sekvenserna i tabellen innehåller talet 1 på något annat index än 0. Då upprepas sekvensen, eftersom om $10^k \equiv 0\:(mod \: n)$ , så gäller $10^{k+m} \equiv 10^k10^m \equiv 10^m \:(mod \: n)$ .

Alltså, ifall en sekvens innehåller talet 0 eller 1 på något annat index än 0, kommer sekvensen att upprepas.

Sekvenser som innehåller talet 0

För att delbarhetssekvensen för talet $n \in \mathbb{N}$ skall innehålla talet 0, måste det för något $k \in \mathbb{N}$ gälla att

$10^k \equiv 0 \:(mod \: n)$ , dvs. $n \mid 10^k$ .

Eftersom $10 = 2*5$ , kan detta gälla endast ifall talet $n$ innehåller endast primtalsfaktorerna 2 och 5, dvs. om

$n=2^a5^b$ , där $a,b \in \mathbb{N}$ .

Ifall $n$ kan skrivas i ovanstående form, och vi betecknar $k=max(\{a,b\})$ , gäller $10^k \equiv 0\:(mod \: n)$ .

Sekvenser som innehåller talet 1

I vilka fall kan vi då vara säkra på att ett tal har en delbarhetssekvens som på något index olika noll har talet 1? Antag att $p \in \mathbb{P}$ är ett primtal. Ifall $p$ ej är talet 2 eller 5, kommer $p$ inte att dela talet $10^k$ för något $k \in \mathbb{N}$ , alltså är $10^k \not\equiv 0\:(mod \: p)$ för alla $k \in \mathbb{N}$ .

Som bekant bildar modulo-operationen $(mod \: p)$ ringen $\mathbb{Z}_{p}$ . Eftersom $10^k \not\equiv 0\:(mod \: p)$ om p inte är primtalet 2 eller 5, gäller det att $10^k \in \mathbb{Z}_{p} \char`\\ \{0\}$ . Dessutom vet vi att om (och endast om) $p$ är ett primtal, är ringen $\mathbb{Z}_{p}$ en kropp, alltså har alla tal förutom noll en multiplikativ invers. Detta är ekvivalent med att $\mathbb{Z}_{p} \char`\\ \{0\}$ bildar en grupp med multiplikationsoperationen.

Delbarhetssekvensen består per definition av talen $10^i\:(mod \: n)$ , där $i \in \mathbb{N}_{0}$ . I fallet där $p$ är ett primtal olika 2 och 5, innehålls alla tal i sekvensen alltså i den delgrupp av $\mathbb{Z}_{p} \char`\\ \{0\}$ som talet $10$ (eller närmare sagt dess ekvivalensklass) genererar. Eftersom gruppen $\mathbb{Z}_{p} \char`\\ \{0\}$ är ändlig, kommer även den genererade delgruppen att vara ändlig. Därmed existerar det ett $k \in \mathbb{N}$ för vilket $10^k \equiv 1 \:(mod \: p)$ .

Talen i sekvensen kommer alltså att upprepas efter ett visst index k. Närmare sagt, eftersom $10^k \equiv 1 \equiv 10^0 \:(mod \: p)$ , sä gäller

$latex \begin{array}{ll}
10^{k+1} \equiv 10^k10^1 \equiv 10^1\\
10^{k+2} \equiv 10^k10^2 \equiv 10^2\\
…\\
10^{k+k-1} \equiv 10^k10^{k-1} \equiv 10^{k-1}\\
\end{array}$ (mod p)

Sekvensen består alltså av cykler med längden k. Eftersom elementen i cykeln bildar en delgrupp av $\mathbb{Z}_{p} \char`\\ \{0\}$ , och gruppen $\mathbb{Z}_{p} \char`\\ \{0\}$ har p-1 element, vet vi enligt Lagranges sats att cykelns längd delar talet p-1. Vi ser också att eftersom $10^0 \equiv 1 \:(mod \: p)$ , kommer cykeln att starta från det första talet (alltså talet $10^0$ ) i sekvensen. Sekvensen har alltså ingen s.k. svans före cykeln.

Alltså alla primtal utom 2 och 5 har ett index olika noll på vilket delbarhetssekvensen har värdet 1. Naturligtvis kan även icke-primtal ha talet 1 i sin sekvens; i tabellen ovan ser vi att detta gäller för talet 9.

Övriga fall

Vi kan vara säkra på att delbarhetssekvensen för talet $n$ (icke-trivialt) innehåller talet 1 endast om $n$ är ett primtal. Därmed kunde man förvänta sig att det existerar tal vars delbarhetssekvens innehåller varken talet 0 eller talet 1. Det visar sig att detta gäller för talet 6. Låt oss alltså undersöka dess delbarhetssekvens:

För talet 10 gäller det att

$10 \equiv 4 \equiv -2 \:(mod \: 6)$ ,

och därmed ser vi att

$10^2 \equiv 10*10 \equiv -2*(-2) \equiv 4 \equiv -2 \:(mod \: 6)$ .

Av detta följer naturligtvis direkt att

$10^k \equiv 10^{k-1} \equiv \cdots \equiv 10 \equiv -2 \:(mod \: 6)$ .

Alltså är delbarhetssekvensen för talet 6 1,-2,-2,-2,… och sekvensen upprepar sig själv, fastän den inte icke-trivialt innehåller talet 0 eller 1.

Vad kan vi då säga om delbarhetssekvensen för talet $n$ som ej är ett primtal och har andra primtalsfaktorer än 2 och 5? Som vi redan tidigare konstaterat, bildar modulo-operationen $(mod \: n)$ ringen $\mathbb{Z}_{n}$ . Ringen är nu inte en kropp, eftersom vi antog att $n$ inte är ett primtal. Vi vet dock ändå att ifall vi multiplicerar två tal i ringen, kommer resultatet även att befinna sig i ringen.

Vi har alltså endast n stycken olika möjliga multiplikationsresultat. Därmed om vi beräknar talen $10^m \:(mod \: n)$ , där $m \in \mathbb{N}$ , måste vi i något skede stöta på ett tal som förekommit tidigare i sekvensen. Vi vet även att detta händer senast, då $m=n$ , eftersom vi inte kan ha $n+1$ olika tal i ringen. Alltså, vi hittar ett tal $m$ och ett annat tal $k < m$ för vilka

$10^m \equiv 10^k \:(mod \: n)$ .

Av detta följer naturligtvis att

$latex \begin{array}{ll}
10^{m+1} \equiv 10^m10^1 \equiv 10^k10^1 \equiv 10^{k+1}\\
10^{m+2} \equiv 10^m10^2 \equiv 10^k10^2 \equiv 10^{k+2}\\
…\\
10^{m+(m-k)-1} \equiv 10^{k+(m-k)-1} \equiv 10^{m-1}\\
10^{m+(m-k)} \equiv 10^{k+(m-k)} \equiv 10^k\\
\end{array}$ (mod n),

alltså går sekvensen efter talet $10^k$ in i en cykel med längden $m-k$ . Till skillnad från sekvenserna för primtal, kan denna sekvens ha en s.k. svans i början förrän cykeln börjar. Detta beror på att talet 1 inte nödvändigtvis förekommer i sekvensen förutom i början.

Öppna frågor

Talen 3 och 9 har exakt likadan delbarhetssekvens; den består endast av ettor. Finns det andra talpar som har exakt likadan delbarhetssekvens? Om det finns, kan vi hitta något samband för tal som har likadan delbarhetssekvens?

Finns det något samband mellan primtalsutvecklingen och delbarhetssekvensen för tal?

Kan vi på något vettigt sett gruppera icke-primtal i olika grupper, t.ex. enligt längden på cykeln?

Litteratur

Allmän algebra:

Jokke Häsä, Johanna Rämö: Johdatus abstraktiin algebraan, Gaudeamus, 2012.
Tauno Metsänkylä, Marjatta Näätänen: Algebra, Limes, 2005.

Nyttiga wikipedia-länkar:

Group
Ring
Finite field (ändlig kropp)

Lagrange’s theorem
Fundamental theorem of arithmetic

Spektraklet

Sekvenser som innehåller talet 0

Sekvenser som innehåller talet 1

Övriga fall

Öppna frågor

Litteratur

Lämna ett svar Avbryt svar

Spektrum rfs medlemstidning