# 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?

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

• 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

• Math expert for every subject
• Pay only if we can solve it

panterafan101wx
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
HINT
Therefore, we conclude that x has order $\phantom{\rule{mediummathspace}{0ex}}\frac{\mathrm{m}}{\left(\mathrm{x},\mathrm{m}\right)}$