1
$\begingroup$

In general, is there a way to compute the number of reduced residue classes $\pmod n$ of a certain order?

For example, say $n=385=5\times7\times11$. Then $$ (\mathbb Z/385\mathbb Z)^\times\cong(\mathbb Z/5\mathbb Z)^\times\times (\mathbb Z/7\mathbb Z)^\times\times (\mathbb Z/11\mathbb Z)^\times. $$ In $(\mathbb Z/5\mathbb Z)^\times$ there are $1,1,2$ elements of orders $1,2,4$.

In $(\mathbb Z/7\mathbb Z)^\times$ there are $1,1,2,2$ elements of orders $1,2,3,6$.

In $(\mathbb Z/11\mathbb Z)^\times$ there are $1,1,4,4$ elements of orders $1,2,5,10$.

Then, if I wanted to see how many elements of order $4$ (say) there were in $(\mathbb Z/385\mathbb Z)^\times$, I can 'brute' force and check all the triples $(a\pmod5,b\pmod7,c\pmod{11})$ for which $\text{lcm}(\text{ord}_5a,\text{ord}_7b,\text{ord}_{11}c)=4$ and conclude that there are $8$ elements of order $4$.

Is there a faster method/theorem to compute this? And if there isn't, what about for $\lambda(385)=60$, the maximum order? Is there a way to compute how many elements there are of order $60$?

$\endgroup$
0
$\begingroup$

I am not entirely sure about the first part. The "nice" thing is that you can just focus on the orders and then calculate how many elements of a given order there are. Since the group of units mod $p$ is cyclic, the number of elements of order $n$ is equal to the number of solutions of the equation

$$ kn \equiv 0 \pmod{p-1}$$

such that $k m \neq 0 \pmod{p-1}$ for any $m < n$.

For the last part, note that you want to calculate the number of generators for each prime. The number of generators $\mod p$ is equal to $\phi (\phi(p)) = \phi(p-1)$. Hence, if $n$ is a square-free product of primes then

$$\lambda (n) = \prod _{p \mid n} \phi(p-1)$$

Note the square-free condition ensures that the $\mod p$ groups are cyclic. Otherwise, it gets a bit messy and I haven't given it much thought.

$\endgroup$
0
0
$\begingroup$

Actually, it is well known that if $n=\prod_{i=1}^{t}p_i^{\alpha_i}$ ,

then $\phi(n)=n\prod_{i=1}^{t}(1-\frac{1}{p_i})$

$\endgroup$

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.