Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 0 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.