# Relationship between different sequences generated through modulo arithmetic.

I am unsure the formal mathematical terminology/notation for dealing with sequences generated from integer modulo arithmetic. So first off, could someone recommend a book that focuses on the sequences generated from arithmetic operations on finite sets of integers? I bought an elementary number theory book and an abstract algebra book but neither ever discussed sequences.

Now the more explicit question. Consider: $$f \left[ n \right] = a n \left( \text{mod} \; N \right) \\ g\left[n\right] = b n \left( \text{mod} \; N \right)$$ where $a,b \in \mathbb{Z}$, $n \in \{0, 1, 2, \ldots \}$, $N \in \{2, 3, 4, \ldots\}$ and $a \left( \text{mod} \; N \right)$ is the remainder of $a / N$. I want to prove that sometimes the sequence $g[n]$ "generated" (may not be correct term) by a choice for $b$ is a "permutation" (may not be correct term) of the sequence $f[n]$ generated by $a$ if $N$ is the same both. I also want to show that the new permutation can be generated by $$g \left[ n \right] = f \left[ k n \right]$$ for some $k \in \mathbb{Z}$ whenever such a permutation exists. I have a suspicion that if $a$ and $b$ are relatively prime to $N$ then such a permutation exists from what little I know of congruence relations, but I can also think of cases where $a$ is relatively prime to $N$ and $b$ is not that this still works.

-
If $b$ is not relatively prime to $N$, then there will be periodicity with period $\lt N$. If $a$ is relatively prime to $N$ then the period will be $N$. So there seems to be no clear sense in which one sequence is a permutation of the other. –  André Nicolas Aug 25 '12 at 16:11
What I was thinking was something along the lines $f[n] = n (\text{mod} \; 8)$ and $g[n] = 2n ( \text{mod} \; 8)$. Then $f[n] = $0, 1, 2, 3, 4, 5, 6, 7$$ and $g[n] = $0, 2, 4, 6$$, but $f[2n] = $0, 2, 4, 6$$. Again, permutation might be the wrong word. –  dcdo Aug 25 '12 at 16:36
About references, for a while if you are investigating such sequences, the ordinary tools of modular arithmetic should be enough. You are right about what happens when $a$ and $b$ are relatively prime to $N$. Each of the sequences has period $N$, and goes in some order through the numbers $0$ to $N-1$. –  André Nicolas Aug 25 '12 at 16:45

As stated in the comments, if $a$ and $b$ are coprime to $N$, then each of the sequences has period $N$. In this case $g[n]=f[kn]$ with $k=a^{-1}b$, where $a^{-1}$ is the multiplicative inverse of $a\pmod N$. This also works if only $a$ is coprime to $N$ (but in this case $g[n]$ has a shorter period).
More generally, if $d:=\gcd(a,N)\mid b$, then with $a'=a/d$, $b'=b/d$ and $N'=N/d$ we have $g[n]=f[kn]$ with $k=a'^{-1}b'$, where the multiplicative inverse is taken $\bmod{N'}$.
If $d\nmid b$, then $g[n]$ takes values that $f[n]$ doesn't take, so there can be no $k$ with $g[n]=f[kn]$.