Let's say I have a function $f(x) = a x + 1$, which is evaluated on a finite ring of integer numbers. It might be used as a hash function for example, but there are other applications. If applied multiple times to some value it will eventually repeat. Sometimes we need to compose this function many more times then there are values in the set. If the function is composed $k$ times and evaluated at $0$ it results in a sum of geometric series. So the actual question is what is the period of geometric series sums in modular arithmetic. $$f^k_m(a) = \dfrac{a^k-1}{a-1} \mod m$$ So the series is as follows: $$[f^0_m(a), f^1_m(a),f^2_m(a),\dots]$$ For each value of $a$ and $m$ it has some period $p(a,m)$, which is what I want to find. Here are some examples: $$ p(1,7)=7$$ $$[0,1,2,3,4,5,6,0,1,2,3,\dots] $$ $$ p(3,7)=6$$ $$[0,1,4,6,5,2,0,1,4,6,5,\dots] $$ $$ p(6,7)=2$$ $$[0,1,0,1,0,1,0,1,0,1,0,\dots] $$ For $m=7$ period equals $m$ only for $a=1$. Well, $a=1$ is a trivial case, something much more interesting happens when you try some other numbers. If I peek $m=2^{20}$ - the actual case where I faced the problem and try different $a$
Here are some examples: $$p(9,2^{20})=1048576~,$$ $$p(15,2^{20})=131072~,$$ $$p(25,2^{20})=1048576~,$$ $$p(31,2^{20})=65536~,$$ $$p(33,2^{20})=1048576~,$$ $$p(35,2^{20})=524288~,$$ $$p(41,2^{20})=1048576~.$$
All of which are powers of $2$.
It is worth noting that those picked values of $a$ have common factors with $m-1$.
Indeed $2^{20}-1=3 \cdot 5^2 \cdot 11 \cdot 31 \cdot 41$
What is the efficient way of calculating $p(a,m)$?
EDIT: Read the wiki, which partially answers a more general question. https://en.wikipedia.org/wiki/Linear_congruential_generator $p(a,m)=m$ if and only if:
1) $(a-1)$ is divisible by all prime factors of $m$
2) $(a-1)$ is divisible by $4$ if $m$ is divisible by $4$
It seems $p(a,m)=1$ if $a$ and $m$ are not coprimes - the sequence converges to a value. (Is that true?)
So the remaining question is values of $p(a,m)$ that are neither $m$ nor $1$. The $m$ does not have to be a power of $2$ - I am interested in all $m$'s.