0
$\begingroup$

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.

  • 0
    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$.2012-08-25

1 Answers 1

0

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