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.

About Brent

Associate 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?

  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.

  3. Pingback: MaBloWriMo 8: definition of s and mod | The Math Less Traveled

  4. sinuheancelmo says:

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

  5. Pingback: MaBloWriMo 21: the order of omega, part I | The Math Less Traveled

Comments are closed.