It is well known that the number of elements in the reduced residue system for a given primorial $p_k\#$ is divisible by $p_k - 1$.

Does it follow that if you divide the elements of a reduced residue class into distinct classes modulo $p_k$, that each class modulo $p_k$ has the same number of element [excluding the class $x \equiv 0 \pmod {p_k}$].

So, let me give an example of what I am talking about for $p_5$.

For $5\#$, the reduced residue system is: $\left\{1,7,11,13,17,19,23,29\right\}$

The 4 classes modulo $5$ have $\frac{8}{5-1} = 2$ elements each:

$$C_1 = 1,11$$ $$C_2 = 7,17$$ $$C_3 = 13,23$$ $$C_4 = 19,29$$

My question: Is this always the case for all primes?


1 Answer 1


Yes. Let us denote the reduced residue system $\pmod{p_k \#}$ with $R_k$.

When $k=1$, this is trivially true.

Consider $k \geq 2$. For each $x \in R_k$, we must necessarily have $x \equiv y \pmod{p_{k-1} \#}$, for some $y \in R_{k-1}$. On the other hand, for each $y \in R_{k-1}$, each of $y, y+p_{k-1} \#, y+2p_{k-1} \#, \ldots ,y+(p_k-1)p_{k-1} \#$ is relatively prime to $p_{k-1} \#$, and together they form a complete set of residues $\pmod{p_k}$. Thus this contributes exactly $(p_k-1)$ terms to $R_k$; one in each non-zero residue class $\pmod{p_k}$. Therefore $R_k$ has $(p_k-1)|R_{k-1}|$ terms, and exactly $|R_{k-1}|$ terms in each non-zero residue class $\pmod{p_k}$.

We now see that $|R_k|=\prod_{i=1}^{k}{(p_i-1)}$ and there are $\prod_{i=1}^{k-1}{(p_i-1)}$ terms of $R_k$ corresponding to each non-zero residue $\pmod{p_k}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .