2
$\begingroup$

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.).

$\endgroup$
  • $\begingroup$ I get $C_{\!\large\circ}(11)= 64$, $C_{\!\large\circ}(13)= 78$, $C_{\!\large\circ}(17)= 172$ $\endgroup$ – Joffan Oct 29 '17 at 15:56
  • $\begingroup$ @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. $\endgroup$ – PM 2Ring Oct 29 '17 at 16:18
  • $\begingroup$ @PM2Ring Why doesn't it start $10,9,7,3,6,1,2,4,8,5$? $\endgroup$ – Joffan Oct 29 '17 at 16:56
  • $\begingroup$ 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 $\endgroup$ – Joffan Oct 29 '17 at 17:05
  • $\begingroup$ @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$. $\endgroup$ – Aurelio Oct 29 '17 at 17:32
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.