1
$\begingroup$

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_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 Answers 1

1

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