There are m gcd ( m , x ) distinct elements in the set { a x ( mod m ) : a ∈ { 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 ϕ function to prove it?And can we also use some counting principle here to give an exact answer?

Question

There are             m              gcd        (        m        ,        x        )             distinct elements in the set   {  a  x    (  mod    m  )  :  a  ∈  {  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&#039;s phi function so that we can simply use properties of   ϕ function to prove it?And can we also use some counting principle here to give an exact answer?

panterafan101wx · Accepted Answer

The number of elements in that set is the additive order of   x  mod  m, which as you have observed is             m              gcd        (        m        ,        x        )            . This formula is a consequence of   lcm  ⁡  (  x  ,  m  )  =                    x        m                    gcd        (        m        ,        x        )            .Indeed, we want to know when the sequence   a  x  mod  m starts repeating. So find the first a such that   a  x  ≡  0  mod  m. This is the same as asking for the first a such that ax is a multiple of m. In other words,   a  x  =  lcm  ⁡  (  x  ,  m  ).

trapskrumcu · Accepted Answer

HINT          m         |       n    x       ⟺       m         |       n    x  ,    n    m       ⟺       m         |       (  n    x  ,    n    m  )    =    n    (  x  ,  m  )       ⟺                 m              (        x        ,        m        )                           |             nTherefore,     m  o  d     m  ,   we conclude that x has order               m              (        x        ,        m        )

Answered question

Answer & Explanation

New Questions in High school probability