# Summation of Modulo Sequences

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.

-

## 1 Answer

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

-

Thanks for the answer. – dcdo Sep 15 '12 at 12:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8751539587974548, "perplexity_flag": "head"}