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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I came across through simulation that multiplying and adding certain modulo sequences yield equal results. Consider the following two sequences \begin{align} g_0[k] &= \sum_{n=0}^{N-1} \left< a n \right>_N \left< k n \right>_N \\ g_1[k] &= \sum_{n=0}^{N-1} \left< b n \right>_N \left< k n \right>_N \end{align} where $a, b \in \mathbb{Z}$, $\left<a\right>_N = a \pmod N$and $\text{GCD}(a,N) = \text{GCD}(b,N) = 1$. It appears that there exist $k_0, k_1 \in \mathbb{Z}$ such that \begin{align} g_0[k_1 k] &= g_1[k] \\ g_1[k_0 k] &= g_0[k] \end{align}

Outside of running several computer simulations that seem to indicate that such integers might always exist for arbitrary $a$ and $b$ with $\text{GCD}(a,N) = \text{GCD}(b,N)$, I cannot find out how to 1) determine under what conditions this holds and 2) figure out the value of $k_0$ and $k_1$ directly.

share|cite|improve this question
up vote 1 down vote accepted

Let $Z_N=\{0,1,\cdots,N-1\}$. Each integer $a$ creates a function on this set, given by multiplying by $a$ and subsequently reducing modulo $N$ (so the result lies in $Z_N$). Call such a map $\varphi_a$. Then $\varphi_a$ is a bijection if and only if $\gcd(a,N)=1$. By Bezout's identity, there are $x,y$ such that $ax+yn=1$ if $a$ is coprime to $N$, in which case $\varphi_a$ has an inverse map $\varphi_x$. And if $(a,N)>1$, then $\varphi_a$ sends both the elements $0\ne N/\gcd(a,N)\in Z_N$ and $0\in Z_N$ to $0$ and hence is not injective.

Therefore when $\gcd(a,N)=1=\gcd(b,N)$, and if $a'$ and $b'$ are inverses of $a,b$ mod $N$ resp., then

$$\sum_{n\in Z_N}\varphi_a(n)\varphi_k(n)=\sum_{m\in Z_N}m\varphi_k(\varphi_{a'}(m))=\sum_{\ell\in Z_N}\varphi_b(\ell)\varphi_k(\varphi_{a'}(\varphi_b(\ell)))=\sum_{\ell\in Z_N}\varphi_b(\ell)\varphi_{ka'b}(\ell).$$

We make the substitutions $m=\varphi_a(n)=\varphi_b(\ell)$. Thus $k_0=a'b$ and similarly $k_1=ab'$, which are only unique modulo $N$.

share|cite|improve this answer
Thanks for the answer. – dcdo Sep 15 '12 at 12:18

Your Answer


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.