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?


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


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.