0
$\begingroup$

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?

  • 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'$2011-12-07

3 Answers 3

1

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

3

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

1

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

  • 1
    @John.Mathew, see my edited answer. The comment by Joel Cohen is also about this.2011-12-07