0

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.

user0410
  • 582
  • Since $C_i$ has at most $m$ distinct elements, we only need to show that for $\gcd (i,q^m-1)=1$, $i\cdot q^i \not \equiv i \cdot q^j \pmod {q^m-1}$ for $0\le i \ne j\le m-1$. – player3236 Sep 12 '20 at 04:58
  • @player3236 Your comment is right. But your comment results in $q^{i-j}=1 \pmod{q^m-1}$ that dose not related to the condition $\gcd(i,q^m-1)=1$. – user0410 Sep 12 '20 at 05:00
  • 1
    No it does not lead to $q^{i-j}=1$. Not if $\gcd(i, q^m-1) >1$. (Also I made a mistake, I shouldn't use $i$ twice.) – player3236 Sep 12 '20 at 05:02
  • @player3236 Is it possible to request you to help me with more details. Thank you. – user0410 Sep 12 '20 at 05:05
  • Take $i = 4, q = 3, m = 2$. Then $C_i = 1$ since $4\cdot 3^0 \equiv 4 \cdot 3^1 \pmod 8$, but obviously $3^0 \not \equiv 3^1 \pmod 8$. – player3236 Sep 12 '20 at 05:10
  • @player3236 In youe example $\gcd(4,3^2-1)\neq 1$. Am I right? – user0410 Sep 12 '20 at 05:13
  • Yes. I was using this for a counterexample to $i \cdot q^i \equiv i\cdot q^j \implies q^{i-j}\equiv 1$. – player3236 Sep 12 '20 at 05:15

1 Answers1

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

player3236
  • 16,413