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

1 Answer 1

Reset to default
3
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.