Find base of exponentiation

Question

Given the two primes $23$ and $11$, find all integers $\alpha$ such that $\alpha^{11} \equiv 1 \mod 23$.

How to compute this? What to use?

Answer 1

By Euler's Criterion:

$$\alpha^{11}\equiv \left(\frac{\alpha}{23}\right)\pmod{23}$$

The set of all solutions to $\alpha^{11}\equiv 1\pmod{23}$ is $1^2,2^2,\ldots,11^2\pmod{23}$, i.e.

$$\alpha\in\{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}\pmod{23}$$

Answer 2

We are looking for elements of order $11$ in the group $U_{23}$ of integers coprime to $23$ under multiplication. Since $23$ is prime, the group has $22$ elements. Because of this, any integer satisfies $x^{22} = 1 \pmod{23}$. Then the squares $x^2 \in U_{23}$ will all be non-trivial solutions $\left(x^2\right)^{11} = x^{22} \equiv 1$.

Answer 3

As $\phi(23)=22$

and if ord$_{23}\alpha=a, a|22\implies a=1,2,11,22$

Now $2^2\equiv4,2^5\equiv9\implies2^{11}=2(9)^2\equiv1\implies$ord$_{23}2=11$

We know, ord$_ma=d,$ ord$_m(a^k)=\frac{d}{(d,k)}$ (Proof @Page#95)

So, ord$_{23}(2^k)=\dfrac{11}{(11,k)}$

$\implies$ord$_{23}(2^k)=\dfrac{11}{(11,k)}=11$ for $1\le k\le10$

and there will be exactly $\phi(11)=10\ \alpha$s such that ord$_{23}\alpha=11$