Why do the cyclotomic cosets have the same size?

Question

So I have this problem: when $p=2$ and $n=2^m-1$ show that $|C_1|=|C_3|=m$ where $m\geq 3$.

$C_s=\{s,ps,p^2s,\dots p^{m_s-1}\}$ is the cyclotomic coset.

I know that the size of the coset is $m_s$ which is the smallest positive integer such that $p^{m_s}*s\equiv s$ modulo $p^m-1$.

I get that for $C_1$ that $2^{m_{s_1}}\equiv 1$ mod $n$ and for $C_3$ that $3*2^{m_{s3}}\equiv 3$ mod $n$. How do I prove that $m_{s1}=m{s_3}=m$?

Answer 1

To answer why $|C_1| = m$, note that if:

$2^k \equiv 1$ (mod $2^m - 1$), we must have $k > m-1$, and it is easy to see that:

$2^m = (2^m - 1) + 1$, so $m$ is the least such (positive) integer $m_1$ such that:

$2^{m_1}\ast 1 \equiv 1$ (mod $2^m - 1$) (with $s = 1$).

It should also be clear that:

$3(2^m) = 3(2^m -1 + 1) = 3(2^m - 1) + 3$, so $m_3 \leq m$.

Now $3(2^{m-2}) < 2^m$, so $3(2^{m-2}) \leq 2^m - 1$, which shows that $m_3 > m-2$.

Finally, note that $3(2^{m-1}) = (2 + 1)(2^{m-1}) = 2^m - 1 + 2^{m-1} + 1$, that is:

$3(2^{m-1}) \equiv 2^{m-1} + 1$ (mod $2^m - 1$), and NOT equivalent to $3$, so $m_3 = m$, as well.

EDIT: There is one "hole" in this argument, the case where $m = 2$. In this case, $C_3 = C_0$, and of course the coset is simply $\{0\}$.

Answer 2

The number of elements in the cyclotomic coset $C_s$ can be found by expressing $s$ in base-$2$ notation as $\mathbf x = (x_{m-1}, x_{m-2}, \ldots, x_1, x_0), x_i \in \{0,1\}$ and then finding the period of $\mathbf x$ under cyclic shifts. It is straightforward to figure out that $00\cdots 01$ and $00\cdots 11$ both have period $m$; it takes $m$ cyclic shifts to get back to where we started from. Hence, $C_1$ and $C_3$ each have $m$ elements.

As noted by David Wheeler, when $m=2$, the argument above breaks down. Note that $11$ has period $1$ while $01$ has period $2$.