# There are m/(gcd(m,x)) distinct elements in the set {ax(modm):a in {0,...,m−1}} I have only known these by using a computer to generate the number of distinct elements. But I am not sure how to prove this conjecture. And is there any way that we can connect this problem to Euler's phi function so that we can simply use properties of phi function to prove it? And can we also use some counting principle here to give an exact answer?

tamnicufl 2022-09-27 Answered
There are $\frac{m}{gcd\left(m,x\right)}$ distinct elements in the set $\left\{ax\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}m\right):a\in \left\{0,...,m-1\right\}\right\}$
I have only known these by using a computer to generate the number of distinct elements. But I am not sure how to prove this conjecture.
And is there any way that we can connect this problem to Euler's phi function so that we can simply use properties of $\varphi$ function to prove it?
And can we also use some counting principle here to give an exact answer?
You can still ask an expert for help

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it

## Answers (2)

panterafan101wx
Answered 2022-09-28 Author has 6 answers
The number of elements in that set is the additive order of $xmodm$, which as you have observed is $\frac{m}{gcd\left(m,x\right)}$. This formula is a consequence of $\mathrm{lcm}\left(x,m\right)=\frac{xm}{gcd\left(m,x\right)}$.

Indeed, we want to know when the sequence $axmodm$ starts repeating. So find the first a such that $ax\equiv 0modm$. This is the same as asking for the first a such that ax is a multiple of m. In other words, $ax=\mathrm{lcm}\left(x,m\right)$.
###### Did you like this example?
trapskrumcu
Answered 2022-09-29 Author has 2 answers
HINT
Therefore, we conclude that x has order $\phantom{\rule{mediummathspace}{0ex}}\frac{\mathrm{m}}{\left(\mathrm{x},\mathrm{m}\right)}$
###### Did you like this example?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it