Number of solutions for linear modular equations given GCD

Question

We are currently investigating a problem involving number theory, an area outside our field of expertise.

Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as equivalent if there exists an integer $a$ such that $$ \{j',k' \} = \{ aj \bmod n, \pm ak \bmod n \}.$$

Now, assume $\gcd⁡(n,j,k)=1$, and given values $\gcd(n,j)$ and $\gcd(n,k)$. We are specifically interested in exploring non-equivalent solutions $(k,j)$ within the range $1 \leq j \leq k < \frac{n}{2}$. Our suspicion is that there are no more than $n$ non-equivalent such pairs, but we are facing challenges in proving it.

We would appreciate any assistance, insights, or proofs regarding the conjecture.

Answer 1

Suppose $\gcd(n,j) = a, \gcd(n, k) = b$, with $\gcd(a, b) = 1$. We want to count $|(a \mathbb{Z}_{n / a}^{\times} \times b \mathbb{Z}_{n / b}^{\times}) / (\mathbb{Z}_n^\times \times \mathbb{Z}_2)|$, where each group elements acts by multiplying both values by its first component, and negating the second one based on its second component. The multiplication by $a$ and $b$ isn't relevant, so we can just count $|(\mathbb{Z}_{n / a}^{\times} \times \mathbb{Z}_{n / b}^{\times}) / (\mathbb{Z}_n^\times \times \mathbb{Z}_2)|$. We will use Burnside's lemma. For an element $x \in \mathbb{Z}_{n / a}^{\times} \times \mathbb{Z}_{n / b}^{\times}$, let's count the elements $(k, z) \in \mathbb{Z}_n^\times \times \mathbb{Z}_2$ which keep it fixed. We need $k \equiv 1 \pmod {\frac na}$ to keep the first element fixed. If $z = 0$, we also need $k \equiv 1 \pmod {\frac nb}$, and because $\gcd(a, b) = 1$ we have $\mathrm{lcm}(\frac na, \frac nb) = n$, so by the CRT we have $k = 1$, so that's one solution. If $z = 1$ we need $k \equiv -1 \pmod {\frac nb}$, which is only possible if $1 \equiv -1 \pmod {\gcd(\frac na, \frac nb)}$. We have $\gcd(\frac na, \frac nb) = \frac n{ab}$, and this only possible if $\frac{n}{ab}$ is $1$ or $2$.

Therefore, if $\frac{n}{ab} \leq 2$ we have $|(\mathbb{Z}_{n / a}^{\times} \times \mathbb{Z}_{n / b}^{\times}) / (\mathbb{Z}_n^\times \times \mathbb{Z}_2)| = \frac{\varphi(\frac na) \varphi(\frac nb)}{\varphi(n)} \leq \varphi(\frac n b) \leq n$, otherwise $|(\mathbb{Z}_{n / a}^{\times} \times \mathbb{Z}_{n / b}^{\times}) / (\mathbb{Z}_n^\times \times \mathbb{Z}_2)| = \frac{\varphi(\frac na) \varphi(\frac nb)}{2 \varphi(n)} \leq \frac{\varphi(\frac na) \varphi(\frac nb)}{\varphi(n)} \leq n$.