Finding all solutions of $x^{11}\equiv 1\bmod23,$

Question

I am asked to find all solutions of 1) $$x^2\equiv 1\bmod23$$

and to find all solutions of 2) $$x^{11}\equiv 1\bmod23,$$ justifying my work.

I think 1) is $1$ and $22$ since if $p$ is an odd prime then $1$ has two distinct square roots modulo $p$, namely $1$ and $p-1$. However I am having difficulty with 2). I've noticed $1^{11}$, $2^{11}$, $3^{11}$ all give $1$ modulo $23$ when typed into the calculator so it may be possible to do it this way but I'm wondering if there is a better method as the numbers will get too big for this to work?

Answer 1

Since $2^{11}\equiv 1$, we know, for each $n$, that $$(2^n)^{11}\equiv(2^{11})^n\equiv 1$$ Thus, since the order of $2$ must be a divisor of $11$, and it is not $1$, we know the order is $11$ so that $2^n$ cycles through $11$ different numbers for $n\in\{0,1,\cdots,10\}$. Thus, the solutions are $2^0,2^1,\cdots ,2^{10}$.

Also note that these are all the solutions, since $23$ is prime so that a polynomial of degree $k$ has at most $k$ zeroes.

Answer 2

If $a$ is a primitive root $\pmod{23},$

using discrete logarithm, $11$ind$_ax\equiv0\pmod{\phi(23)}\iff$ind$_ax\equiv0\pmod2$

So, $x\equiv a^{2k}$ where $0\le2k\le22$

Now $2^{11}\equiv1\pmod{23}\implies2$ is not a primitive root $\pmod{23}$

and $5^2\equiv2\pmod{23}\not\equiv1\implies5^{11}=5(5^2)^5\equiv5\cdot2^5\equiv-1$

$\implies5$ is a primitive root $\pmod{23}$

Answer 3

Harry, i don't think that x^2≡1 (mod p) has as a general solution 1 and p-1 but simply 1 and -1 and all the numbers congruent to 1 and -1 (mod p). So to state 1 and 22 is not wrong but is not completely correct in my view