2

Equation:

$a^b \mod m$

for subsequent values of $b$ and $a$ produces a cycles.

For example: $m = 3$. We have $a > 1$ and $b > 4$ ($b$ is always large enough).

  • $2^5 \equiv {\color{red}2} \pmod 3$
  • $2^6 \equiv {\color{red}1} \pmod 3$
    • successive power results will give you a cycle (2, 1, 2, 1 ...). We increase $a$ by one.
  • $3^5 \equiv {\color{red}0} \pmod 3$
    • successive power results will give you a cycle (0, 0 ...). We increase $a$ by one.
  • $4^5 \equiv {\color{red}1} \pmod 3$
    • successive power results will give you a cycle (1, 1 ...). We increase $a$ by one.
  • $5^5 \equiv {\color{red}2} \pmod 3$
  • $5^6 \equiv {\color{red}1} \pmod 3$
    • successive power results will give you a cycle (2, 1, 2, 1 ...). We increase $a$ by one.
  • $6^5 \equiv {\color{red}0} \pmod 3$
    • successive power results will give you a cycle (0, 0 ...). We increase $a$ by one.
  • ...

We can see that the cycle (marked in red) is: $(2, 1, 0, 1)$

The cycle size is 4.

Question: Can you prove that the cycle size for any modulo $m$ value will have a specified value? (or some upper limit on this value - but as precise as possible)

I hope I did not make any mistakes (but all is possible).

For example for $m = 16$ cycle size is $31$ (If I did not make a mistake.).

Aurelio
  • 479
  • I get $C_{!\large\circ}(11)= 64$, $C_{!\large\circ}(13)= 78$, $C_{!\large\circ}(17)= 172$ – Joffan Oct 29 '17 at 15:56
  • @Joffan: Here's my 11-cycle: 10, 9, 7, 3, 6, 1, 1, 1, 1, 10, 5, 8, 4, 2, 1, 10, 4, 6, 9, 8, 1, 10, 3, 2, 5, 7, 1, 1, 10, 1, 0, 1. – PM 2Ring Oct 29 '17 at 16:18
  • @PM2Ring Why doesn't it start $10,9,7,3,6,1,2,4,8,5$? – Joffan Oct 29 '17 at 16:56
  • My full compound cycle for $11$: 10, 9, 7, 3, 6, 1, 2, 4, 8, 5, 1, 3, 9, 5, 4, 1, 4, 5, 9, 3, 1, 5, 3, 4, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 4, 6, 9, 8, 1, 7, 5, 2, 3, 10, 3, 2, 5, 7, 1, 8, 9, 6, 4, 1, 9, 4, 3, 5, 10, 1, 0, 1 – Joffan Oct 29 '17 at 17:05
  • @PM 2Ring I was not about to finish at 0 or 1. In the examples it is pure case. For specified $a$ the program must find the "subcycle" - then goes to the next $a$. – Aurelio Oct 29 '17 at 17:32

1 Answers1

2

I agree with your calculation for $m=16$.

The maximum individual cycle length in the values you are looking at is the Carmichael function, $\lambda(n)$ or least universal exponent function. It is related to the Euler totient and is either the same as that or divides it.

Here $\lambda(16)=4$. This cycle length only applies to a small proportion of the number up to $16$, $4$ of the odd numbers. $3$ odd numbers have a cycle length of $2$ and obviuosly $1$ has a cycle length of $1$. All the even numbers return $0$ once they have accumulated enough multiples of $2$ to "saturate" the modulus, so a cycle of length $1$ in your reckoning.

The compound cycle length (to coin a term for your quantity) $C_{\!\large\circ}(m)$ for an arbitrary $m>2$ will certainly be no more than $m\lambda(m)$, and we can reduce that upper limit also since the cycle lengths of $m{-}1, m, m{+}1$ will be $2, 1,1$ and no more than half the values will have the full cycle of $\lambda(m)$, with the others being no more than $\lambda(m)/2$ (since every cycle length must divide $\lambda(m)$). So an upper limit is $C_{\!\large\circ}(m) \le 4+\lambda(m)\left[(m-1)/2 + (m-3)/4\right]= 4+\lambda(m)(3m-5)/4$. For $m=16$, this gives $C_{\!\large\circ}(16)\le 47$ which is obviously too high but not unreasonable.

Joffan
  • 39,627