Let $C_i=\{i\cdot q^j \pmod{q^m-1}\, ||\, j=0,1,\cdots ,m-1\}$. If $\gcd(i,q^m-1)=1$, then $|C_i|=n$.

Question

Let $$ C_i=\{i\cdot q^j \pmod{q^m-1}\, ||\, j=0,1,\cdots ,m-1\}. $$ My question: How to show that if $\gcd(i,q^m-1)=1$, then the cardinality of $C_i$, denoted with $|C_i|$, is equal to $m$.

Thanks for any help.

Answer 1

I'll just flush out the proof.

Suppose $0\le j<k \le m-1$.

If $\gcd (i,q^m-1)=1$: $$i\cdot q^j \equiv i \cdot q^k \pmod {q^m-1} \implies q^j \equiv q^k \pmod {q^m-1}$$

Since $\gcd (q^j,q^m-1)=1$: $$q^j \equiv q^k \pmod {q^m-1} \implies 1 \equiv q^{k-j}\pmod {q^m-1}$$

This implies $(q^m-1) \mid (q^{k-j}-1)$.

Together with $k-j\ne0$, this implies $q^{k-j}-1 > q^m-1 > q^k - 1\ge q^{k-j}-1$, which is a contradiction.

Hence $i \cdot q^j$ are all distinct for $j = 0,1,\dots, m-1$.