Jim Belk University of Glasgow

Homework 11

Due Date: Friday, May 6

  1. Let \(\mathbb{F}\) be a field, and let \(p(x)\) and \(q(x)\) be relatively prime polynomials over \(\mathbb{F}\). Prove that for every pair of polynomials \(a(x),b(x)\in \mathbb{F}[x]\), there exists a polynomial \(c(x)\in\mathbb{F}[x]\) so that for all \(f(x) \in \mathbb{F}[x]\), \[ f(x) \,\equiv\, c(x)\;\bigl(\mathrm{mod}\;p(x)\,q(x)\bigr) \] if and only if \[ f(x) \,\equiv\, a(x)\;\bigl(\mathrm{mod}\;p(x)\bigr)\qquad\text{and}\qquad f(x) \,\equiv\, b(x)\;\bigl(\mathrm{mod}\;q(x)\bigr). \]
  2. Define a sequence \(\{s_n\}\) of integers recursively by \(s_1=4\) and \[ s_n\,=\, s_{n-1}^2 - 2 \] for \(n\geq 2\). The goal of this problem is to prove the following theorem.

    Theorem. Let \(p>2\) be prime. If \(s_{p-1} \equiv 0\;(\mathrm{mod}\;2^p-1)\), then \(2^p-1\) is prime.

    This is known as the Lucas-Lehmer primality test for Mersenne primes.

    1. Prove that for every prime \(q\), there exists a field \(\mathbb{F}\) with \(q^2\) elements such that \(3\) has a square root in \(\mathbb{F}\).
    2. Let \(\mathbb{F}\) be a field, let \(r\) be a square root of \(3\) in \(\mathbb{F}\), and let \(\omega = 2+r\). Prove that \[ s_n \,=\, \omega^{2^{n-1}} + \omega^{-2^{n-1}} \] in \(\mathbb{F}\) for each \(n \in \mathbb{N}\).
    3. Let \(\mathbb{F}\) be a field of characteristic \(q>2\), let \(\omega\in\mathbb{F}\), and let \(n\) be a positive integer. Prove that \(\omega\) has order \(2^n\) in \(\mathbb{F}\) if and only if \(\omega^{2^{n-1}}=-1\).
    4. Prove the theorem. (Hint: Consider the smallest prime \(q\) that divides \(2^p-1\).)
    1. Write a function LucasLehmerTest that takes a prime \(p\) as input and checks whether \(p\) passes the test described in question 2.
    2. Find all primes less than 1000 that pass the test.
    3. Exactly one of the following numbers is prime. \[ 2^{\large 44483}-1,\qquad 2^{\large 44491}-1,\qquad 2^{\large 44497}-1. \] Use your LucasLehmerTest function to determine which one.