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

Lämna ett svar

Din e-postadress kommer inte publiceras. Obligatoriska fält är märkta *