What's the explanation for this congruence? I was studying a proof of the Lucas-Lehmer primality test and I am sort of confused about a step in it. 
Denote by $S_n$ the sequence $S_n = S_{n-1}^2 -2$, $S_1 = 4$. If $\omega = 2 + \sqrt{3}, \bar{\omega} = 2 - \sqrt{3}$, then it's easy to show that 
$$ \omega^{2^{m-1}} + \bar{\omega}^{2^{m-1}} = S_m.$$
Now, if $q$ is a prime factor of $2^{p}-1$, and if $2^{p}-1 \mid S_{p-1}$, then $$\omega^{2^{p-1}} = ({\omega^{2^{p-2}}})^2 \equiv({\omega^{2^{p-2}}})(-{\bar{\omega}^{2^{p-2}}})= -(\omega\bar{\omega})^{2^{p-2}} \equiv -1 \ (\text{mod } q) ,$$ where in the second step we have used $q\mid S_{p-1} = \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}}$ and in the last step we've used $\omega \bar{\omega} = 1$. So $\omega^{2^{p-1}} + 1$ is an integer, but  since the squaring operation can't rid us of the $\sqrt{3}$ term, I am not able to see how this is possible? I'm probably making some silly error and would appreciate it if someone pointed it out.
 A: It turns out that you can do the computation over $\mathbb R$ without using the fact that $\omega=2+\sqrt{3}$.  All you need is is that you have two numbers, say $a$ and $b$, that add to $4$ and multiply to $1$. $a+b=4$ gets you $S_1$, and for the induction step,  if $S_n=a^{2^{n-1}}+b^{2^{n-1}}$, you will have 
$$S_n^2-2=(a^{2^{n-1}}+b^{2^{n-1}})^2-2=a^{2^{n}}+2(a^{2^{n-1}}b^{2^{n-1}})+b^{2^{n}}-2,$$
but 
$$2(a^{2^{n-1}}b^{2^{n-1}})=2(ab)^{2^{n-1}}=2,$$
and so the $2$s cancel out.
If you had an $a$ and a $b$ that satisfied these two properties mod $q$, then you could compute $S_n \pmod q$ just using $a$ and $b$ because you would still satisfy the defining recurrence (except mod $q$).  Or if you had $a$ and $b$ in some ring that contained $\mathbb Z/q\mathbb Z$.
This generalizes somewhat.  Often times, if you have a recurrence relation whose solution is always an integer, it's not uncommon that you can find a closed form expression of the form $\sum \alpha_i \beta_i^n$ where the $\beta_i$ are the roots of some irreducible, monic polynomial and if $\sigma$ is a Galois automorphism sending $\beta_i$ to $\beta_j$, then $\sigma(\alpha_i)=\alpha_j$.  For example, with the Fibonacci numbers, there is the closed form expression
$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2} \right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2} \right)^n$$
and the $\mathbb Q$-automorphism of $\mathbb Q[\sqrt{5}]$ swapping $\sqrt{5}$ with $-\sqrt{5}$ just swaps the two terms (which gives an immediate proof that the expression is at least rational, although more work is required to see that it is an integer).  If you are working in a field containing $\mathbb F_q$ which also contains a square root of $5$, you can form a similar expression and show that it satisfies the same recurrence relation as the Fibonacci numbers do, except mod $q$.  This allows you to deduce things about the period of the Fibonacci sequence mod $q$, for example.
A: 
where in the second step we have used $q\mid S_{p-1} = \omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}}$ and in the last step we've used $\omega \bar{\omega} = 1$. So $\omega^{2^{p-1}} + 1$ is an integer,

That doesn't imply it's $\in \Bbb Z$ since the congruence you derived is $\bmod \color{#c00}{\omega^{2^{\large  p-2}}}q\Bbb Z,\,$ not $\bmod q\Bbb Z$, i.e. 
$$ \omega^{\large 2^{p-2}}\!\! + \bar{\omega}^{\large  2^{p-2}}\!\! = qk\,\Rightarrow\, \omega^{\large  2^{p-2}} \!\omega^{\large  2^{p-2}}\!\! = \omega^{\large  2^{p-2}}(qk-\bar{\omega}^{2^{\large  p-2}})\equiv- (\omega\bar\omega)^{2^{\large  p-2}}\!\!\!\pmod{\!\color{#c00}{\omega^{2^{\large  p-2}}}q\Bbb Z}\qquad $$
A: $\omega$ cannot be considered an element of $\mathbb F_q$. Rather, it must be considered as part of a field extension $\mathbb F_q(\omega)$ where $\omega^2-4\omega+1\equiv0$, the minimal polynomial of $\omega$ in $\mathbb R$.
Once this interpretation is adopted, the obtained congruence $\omega^{2^{p-1}}\equiv-1\bmod q$ makes sense. For example, let $p=7$ and $q=127$. Then $\omega^{2^{p-1}}\equiv\omega^{64}\equiv-1\bmod127$.
