Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $\dfrac{m}{\gcd(m,x)}$ distinct elements in the set $\{ax \pmod{m}: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?

share|improve this question
    
@JavaMan yes. I've changed it. –  geraldgreen Dec 7 '11 at 22:33
2  
Denote $d = gcd(m,x)$, $m = m'd$ and $x = x'd$. We have $$a x \equiv b x \mod m \Longleftrightarrow m | (b-a) x \Longleftrightarrow m' | (b-a) x' \Longleftrightarrow m' | b-a \Longleftrightarrow a \equiv b \mod m'$$ –  Joel Cohen Dec 7 '11 at 22:37

3 Answers 3

up vote 1 down vote accepted

The number of elements in that set is the additive order of $x \bmod m$, which as you have observed is $\dfrac{m}{\gcd(m,x)}$. This formula is a consequence of $\operatorname{lcm}(x,m)= \dfrac{xm}{\gcd(m,x)}$.

Indeed, we want to know when the sequence $ax \bmod m$ starts repeating. So find the first $a$ such that $ax \equiv 0 \bmod m$. This is the same as asking for the first $a$ such that $ax$ is a multiple of $m$. In other words, $ax=\operatorname{lcm}(x,m)$.

share|improve this answer
    
Could you please give me a link about this in more detail? –  geraldgreen Dec 7 '11 at 22:38
1  
@John.Mathew, see my edited answer. The comment by Joel Cohen is also about this. –  lhf Dec 7 '11 at 22:44

HINT $\rm\ \ m\ |\ n\:x\ \iff\ m\ |\ n\:x,\:n\:m\ \iff\ m\ |\ (n\:x,\:n\:m)\: =\: n\:(x,m)\ \iff\ \dfrac{m}{(x,m)}\ \bigg|\:\ n$

Therefore, $\rm\:mod\ m,\:$ we conclude that $\rm\:x\:$ has order $\rm\:\dfrac{m}{(x,m)}$

share|improve this answer

If $\gcd(x,m) = d > 1$, then the equation $y \equiv ax \pmod{m}$ has $d$ times the solutions of $y \equiv a\frac{x}{d} \equiv \frac{m}{d}$. In other words, we may assume $\gcd(x,m) = 1$.

In this case, we simply observe that $y = ax \pmod{m}$ has a solution for all $a$ since $$y \equiv ax \pmod{m} \iff yx^{-1} \equiv a \pmod{m}.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.