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


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

  • $\begingroup$ Excellent, I did suspect something like this but wasn't sure. Thank you. Now to see if I can use this in some way.... $\endgroup$ – Valtteri May 26 '14 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.