Group of numbers in residue number system of first $n$ primes

80 Views Asked by At

Denote $$\Pi_n = \Pi_{i=1}^n p_i$$ ie. the product of the first $n$ primes.

Assume we have a number $m$. Denote $$L(m) = k \iff \Pi_{k-1} < m \le \Pi_{k}.$$

Assume also $L(1)=1.$

Now, if $L(m) = k,$ we can represent $m$ as a vector of $k$ numbers. Denote such representation as $$R(m) = \{a_1, a_2, a_3 \dots a_k \},$$ where $m \equiv a_i \mod p_i.$

We can also, if needed, represent a number $m$ with $L(m)=k$ as a vector of length $n, \ k \le n$ by simply increasing the number of modulos calculated. Denote this as $R(m,n).$

Define set $\pi_n = \{R(m,n) \ | \ L(m)\le n \wedge \gcd(m,\Pi_{n}) = 1 \}.$

The cardinality of these sets can be easily calculated: $$|\pi_n| = \varphi(\Pi_n).$$

To demonstrate this, consider $\pi_3.$ It has $\varphi(2*3*5) = 1*2*4 = 8 $ elements. They are $$\{1, 1, 1\}, \{1, 1, 2\}, \{1, 1, 3\}, \{1, 1, 4\}, \{1, 2, 1\}, \{1, 2, 2\}, \{1, 2, 3\}, \{1, 2, 4\}.$$

Define product of (a binary relation between) elements of $\pi_n$. If $a,b \in \pi_n$, $a = \{a_1 \dots a_n\}$ and $b = \{b_1 \dots b_n\}$, then $$a*b = c = \{c_1, c_2 \dots c_n\},$$ where $a_i b_i \equiv c_i \mod p_i.$

For example, in $\pi_3$: $\{1, 1, 4\}*\{1, 2, 3\} = \{1,2,2\}.$

The set $\pi_n$ together with the multiplication $*$ forms a group. This is easily seen, as multiplying two elements from $\pi_n$, the result has gcd with $\Pi_n$ of one, and the length is preserved. Multiplication is assosiative. The identity element is $R(1,n)$. Inverse element can be calculated by noticing that for all elements $a \in \pi_i$, every member of $a$, $a_i$ has a multiplicative inverse $a_i^{-1}$, $$ a_i a_i^{-1} \equiv 1 \mod p_i.$$ This group is also clearly Abelian, as multiplication is commutative.

My question is, what group $(\pi_n, *)$ is?

I can with some certainty say that $(\pi_n, *)$ is not cyclic. At least $(\pi_3, *)$ is not. I made the Cayley table and calculated the orders of each element. Based on this, I believe $(\pi_3, *)$ is actually direct product of $\mathbb Z 4$ and $\mathbb Z 2.$

1

There are 1 best solutions below

1
On BEST ANSWER

It's just the group of units $(\Bbb Z/\Pi_n\Bbb Z)^\times$. This follows from the Chinese Remainder Theorem.

Note that unit groups are completely classified - see the Wikipedia article. In particular,

$$\pi_n=U(\Pi_n)\cong \prod_{i=1}^n \Bbb Z/(p_i-1)\Bbb Z.$$