Cardinalities of Residue Classes In Modular Multiplication Groups.

For any given $n$, let

$$R(n):=\{k: (k,10n)=1, \ k<10n\},$$

e.g. the set of numbers relatively prime to $10n$. For example $R(2)=\{1,3,7,9,11,13,17,19\}$.

It's easy to see that the units digit of each element in $R(n)$ is in $\{1,3,7,9\}$. Therefore we can write $R(n)$ as a disjoint union of $R_i(n)$, where

$$R_i(n) = \{k: (k,10n)=1,\ k<10n,\ k\equiv i\pmod{10}\}, \ i\in\{1,3,7,9\}.$$

For example:

$$R(2) = R_1(2)\cup R_3(2)\cup R_7(2)\cup R_9(2)= \{1,11\}\cup \{3,13\}\cup\{7,17\}\cup\{9,19\}.$$.

Conjecture: For all $k$: $|R_i(k)|=|R_j(k)|$ for all $i,j$ in $\{1,3,5,7\}$. In other words, the size of each class of residues is equal. In the above example, $|R_i(2)|=2$. I've verified this numerically for $n<1000$

I'm trying to find a relatively low-brow proof of this conjecture, preferably, one that doesn't involve classification of finite abelian groups, or in this case Modulo Multiplication Groups. It's not hard to show that $|R_1(k)|=|R_9(k)|$ and $|R_3(k)|=|R_7(k)|$ by via the bijection $x\rightarrow 10k-x$ which preserves coprimedness. However, I'm completely baffled by how to show $|R_1(n)|=|R_3(n)|$ and $|R_1(n)|=|R_7(n)|$ without delving into a myriad of special cases that depend on the factorization of $n$.

Solution 1:

Your problem is equivalent to identify the cardinality of a fiber of an element of the image of the obvious group morphism $\pi: (\mathbb{Z}/10n)^\times\to (\mathbb{Z}/10)^\times$.

Since we have a group morphism, each fiber has same cardinality, which is the cardinality of $\ker(\pi)$. Clearly, this morphism is surjective, so we have $\varphi(10n)=\varphi(10)\vert\ker(\varphi)\vert$ (by the first isomorphism theorem).

Hence each $R_i(n)$ has cardinality $\dfrac{\varphi(10n)}{4}$. This is consistent with your result for $n=2$.

Remark. To prove that each fiber of a surjective group morphism has same cardinality equal to $\vert \ker(f)\vert$, we may invoke the first isomorphism theorem, but we may also argue directly as follows: let $f:G\to G'$ be a surjective group morphism. Let $g'_0\in G'$. Then $g'_0=\varphi(g_0)$ for some $g\in G$. Now for all $g\in G$, $\varphi(g)=g'_0=\varphi(g_0)\iff gg_0^{-}\in\ker(f)\iff g\in g_0\ker(f)$. So $f^{-1}(\{g'_0\})=g_0\ker(f)$ and we are done.

Note that if $r=\vert G'\vert$, since translates of $\ker(f)$ form a partition of $G$, we have $\vert\ker(\varphi)\vert=\dfrac{\vert G\vert}{\vert G'\vert}$.