Question about Lagrange's and factor theorem Find all solutions $x^{12} \equiv 1 \pmod{13}$. Hint: the computation of high powers is better accomplished by using binary expansion of the exponent.
Approach: This time I don't have a clear approach. 1 is clearly a solution, so maybe I should tru using the factor theorem by saying there exists a polynomial $g(x)$ such that $x^{12}-1=(x-1)g(x) \equiv 0 \pmod{12}$ and see how it goes from there. How do I start ?. The topics related to that problem are factor theorem and lagrange's theorem.
 A: Hint: show that if $a$ is a solution, then so are $a^2,a^3,\dots,a^{12}$. Then 
compute $2^r$ for all $r$, $1\le r\le12$. 
A: This problem has little things to do with Lagrange's theorem and factor theorem.
First, one can paraphrase the Lagrange's theorem:

If p is a prime, then either all coefficient of $f(x)$ is a multiplier of p or the number of in-congruent solution to $f(x)$ is at most deg $f(x)$.

From this theorem, one can draw a conclusion that:
The number of in-congruent solution to $x^{12}-1$ is at most 12.
But it tells one literally nothing because the low bound of numbers of in-congruent solution in this case is unknown. Even if one has already known the low bound, it may give an inequality which can be confined to find the solutions unless the low bound equals to the upper bound. (i.e. The number of in-congruent solution to $x^{12}-1$ is at least 12.)
Second, one can state the factor theorem:

$f(x)$ has a polynomial factor $(x-x_1)$ if and only if $x_1$ is a root of $f(x)$.

Using this theorem, one can factorize the $f(x)$. However, it doesn't give any apparent clue for finding roots.
So, how to solve the problem?
Notice that $12 = 13-1$ and $13$ is a prime. 
One can recall Fermat's little theorem :

For all $a$ cannot divide $13$, then $a^{12} \pmod {13}.$ 

Therefore the solution is $\{n|n \neq  0\pmod {13}\}$
