## MaBloWriMo 7: s via omega

Yesterday, I challenged you to prove that

$s_m = \omega^{2^m} + \overline{\omega}^{2^m} \pmod{M_n}$

where $\omega = 2 + \sqrt{3}$, $\overline{\omega} = 2 - \sqrt{3}$, and the $s_m$ are defined by $s_0 = 4$ and $s_n = (s_{n-1}^2 - 2) \bmod M_n$.

The proof is by induction on $m$. The base case $m = 0$ is just arithmetic:

$\omega^{2^0} + \overline{\omega}^{2^0} = \omega^1 + \overline{\omega}^1 = (2 + \sqrt 3) + (2 - \sqrt 3) = 4 = s_0.$

Now suppose that we already know the statement holds for some particular $m \geq 0$; we must show that it also holds for $m+1$. The proof is not too hard, but we have to handle the stacked exponents with care! (Note also that all the following equalities are really taken $\pmod M_n$, which is OK since addition, subtraction, and multiplication are all compatible with taking remainders.)

$\begin{array}{rcl} s_m^2 &=& \left(\omega^{2^m} + \overline{\omega}^{2^m}\right)^2 \\[5pt] &=& \left(\omega^{2^m}\right)^2 + 2\omega^{2^m} \overline{\omega}^{2^m} + \left(\overline{\omega}^{2^m}\right)^2 \\[5pt] &=& \omega^{2^{m+1}} + 2(\omega \overline{\omega})^{2^m} + \overline{\omega}^{2^{m+1}} \\[5pt] &=& \omega^{2^{m+1}} + \overline{\omega}^{2^{m+1}} + 2\end{array}$

(The last step is because we know from yesterday that $\omega \overline{\omega} = 1$.) So $\omega^{2^{m+1}} + \overline{\omega}^{2^{m+1}} = s_m^2 - 2 = s_{m+1} \pmod M_n$, which is what we wanted to show.

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, arithmetic, iteration, modular arithmetic, number theory and tagged , , , , , , , . Bookmark the permalink.

### 11 Responses to MaBloWriMo 7: s via omega

1. Here it is proved not only the equality mod M_n, but it is also proved the equality in general. Am I right?

• Brent says:

Well, we defined the s_n in terms of mod M_n in the first place. I will write more about this today.

2. sinuheancelmo says:

Hendrix College is a University or a high-school? What can we study there, high-school subjects or universitary careers?

• Brent says:

The terminology can be confusing since it is used very differently depending on what country you are in. Hendrix is definitely not a high school, it is a 4-year school that a student would attend after completing high school. It is not a university though, the difference being that it is relatively small and does not offer graduate degrees like a master’s degree or PhD.

• sinuheancelmo says:

3. sinuheancelmo says:

So, here are studied professional careers, but with a duration of 4 years. What careers are studied here, for instance?

• Brent says:

I suggest you just go poke around https://www.hendrix.edu/ , I think you will be able to find answers to your questions much more quickly that way than I would be able to answer them. For example there is a list of the academic programs here: https://www.hendrix.edu/academics/majorsandminors/

• sinuheancelmo says:

Thank you!