How many solutions does $x^{50} \equiv 1 \mod 181$ have?

Question

How many solutions does $x^{50} \equiv 1 \mod 181$ have?

I know that $\varphi(181)$ is $180$ so $x^{180} \equiv 1$ for all $x$ as $181$ is a prime. I'm not sure how to go forth from here

Answer 1

I will give you the basic idea of the proof below. Note, however, that this is far from being a formally correct and complete proof, you need to add structure, references to theorems from your lecture, proofs for the claims in there, etc.

First, factor $180 = 2^2*3^2*5$. For an element $x$ to satisfy $x^{50} = 1$, it should thus have order $2$, $5$ or $10$. Luckily for you, this is equivalent to $x^{10} = 1$ and thus we have already simplified the problem. This second equation can have at most $10$ solutions (as $181$ is prime). So let $\alpha$ be an element of order $180$, that is $\alpha^{180} = 1$ and $\alpha^n \neq 1$ for all $1 \leq n \leq 179$. Then $\alpha^{18\cdot k}$ for $k = 0,1,2,\ldots, 9$ are the $10$ different solutions to the equation.

Answer 2

The group of units modulo $181$ is cyclic, and has order $180$. So let $\omega$ be a generator. A solution $x=\omega^k$ $(0\le k<180)$, by definition, satisfies the equation $$\omega^{50k}=1\iff50k\equiv 0\mod 180\iff5k\equiv 0\mod 18.$$ As $5$ and $18$ are coprime, $5$ is a unit modulo $18$, so that it amounts to $\;k\equiv 0\mod18$. Ten values of $k$ satisfy this congruence in the interval $[0,180)$.

Answer 3

We have $x^{50} \equiv 1$ iff $x^{10} = x^{\gcd(50,180)} \equiv 1$.
Since the group of units mod $181$ is cyclic, there are exactly $10$ solutions.