3
$\begingroup$

I was working on this problem and found a solution that involved sequences generated by modular exponentiation with an incrementing exponent:

$$x_{m,b,i} = b^{i} \mod m$$

For example, in modular base 10:

  • $0^1 \equiv 0$, $0^2\equiv 0$, $0^3\equiv 0$, …
  • $1^1 \equiv 1$, $1^2\equiv 1$, $1^3\equiv 1$, …
  • $2^1 \equiv 2$, $2^2\equiv 4$, $2^3\equiv 8$, $2^4\equiv 6$, $2^5\equiv 2$, $2^6\equiv 4$, $2^7\equiv 8$, $2^6\equiv 6$, …
  • $3^1\equiv 3$, $3^2\equiv 9$, $3^3\equiv 7$, $3^4\equiv 1$, $3^5\equiv 3$, $3^6\equiv 9$, $3^7\equiv 7$, $3^6\equiv 1$, …
  • $4^1 \equiv 4$, $4^2\equiv 6$, $4^3\equiv 4$, $4^4\equiv 6$, …
  • $5^1 \equiv 5$, $5^2\equiv 5$, $5^3\equiv 5$, …
  • $6^1 \equiv 6$, $6^2\equiv 6$, $5^3\equiv 6$, …
  • $7^1\equiv 7$, $7^2\equiv 9$, $7^3\equiv 3$, $7^4\equiv 1$, $7^5\equiv 7$, $7^6\equiv 9$, $3^7\equiv 3$, $7^6\equiv 1$, …
  • $8^1 \equiv 8$, $8^2\equiv 4$, $8^3\equiv 2$, $8^4\equiv 6$, $8^5 \equiv 8$, $8^6\equiv 4$, $8^7\equiv 2$, $8^8\equiv 6$, …
  • $9^1 \equiv 9$, $9^2\equiv 1$, $9^3\equiv 9$, $9^4\equiv 1$, …

This property of forming cycles is quite nice, and can be proven trivially to happen in all sequences for every exponential base and every modular base (every element depends only on the previous one, and using the pigeon hole principle we can exhaust the congruence classes until an element is produced that appeared before).

But these cycles do not always start at the beginning of the sequences. Exceptional examples I found:

  • $x_{b,m,0} = b^0 \mod m \equiv 1$ for all sequences
  • $x_{2,4} = 1, 2, 0, 0, 0$…
  • $x_{3,9} = 1, 3, 0, 0, 0$…
  • $x_{2,8} = 1, 2, 4, 0, 0$…

Now my question: What's special about these bases? How long are those irregular beginnings? Do they ever prepend a cycle of more than one element?

I did some research and modular multiplicative inverses seem to be related, as all my examples did not have one. I also found modular multiplicative groups (Wolfram article) which seem to describe the cycles, but I didn't completely understand them and didn't notice anything about to the sequence beginnings.

$\endgroup$
2
$\begingroup$

Your examples of $x_{2,4},x_{3,9},x_{2,8}$ sequences are cases where $b$ is a power of $m$, and will therefore eventually produce zeros when you take a sufficiently large power of $m$, but will not initially when $1 \le m\lt b$

You can go further than this: if $m$ and $b$ have the same distinct prime factors then the same sort of thing will happen, for example $12=2^2\times 3^1$ and $54=2^1\times 3^3$ so they both have the distinct prime factors $2$ and $3$, while $12^1\equiv 12 \pmod{54}$, $12^2\equiv 36 \pmod{54}$, and $12^i\equiv 0 \pmod{54}$ for $i \ge 3$

On the neater patterns you spotted, some are related to Fermat's little theorem $$a^p \equiv a \pmod{p}$$ for prime $p$ and $1\le a \lt p$ and to its generalisation, Euler's theorem $$a^{\varphi (n)} \equiv 1 \pmod{n}$$ for $a$ coprime to $n$ where $\varphi (n)$ is Euler's totient function

$\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.