MATH 261 Exam 2, Fall 2018

Math 261 — Exam 2 November 7, 2018 The use of notes and books is NOT allowed. Exercise 1: Polynomials mod 691 (30 pts) In this exercise, you may freely use the fact that 691 is prime. Consider the polynomials f(x) = x4 +4x3 +4x2 −5x−12 and g(x) = x2 +3x+4 in (Z/691Z)[x]. 1. (5 pts) Check that g(x) | f(x), and find a polynomial h(x) such that f(x) = g(x)h(x). 2. (5 pts) State the law of quadratic reciprocity. 3. (16 pts) Use Legendre symbols to prove that neither g(x) nor h(x) have any roots in Z/691Z. 4. (4 pts) What is the complete factorization of f(x) in (Z/691Z)[x]? Make sure to justify that your factors are irreducible. Exercise 2: The P´epin test (30 pts) In the 17th century, the French mathematician Pierre de Fermat studied the numbers Fn = 22n + 1, where n ∈ N. The purpose of this exercise is to establish a criterion to test whether Fn is prime. In the rest of the exercise, we fix n ∈ N. 1. (4 pts) Prove that Fn ≡ −1 (mod 3) and that Fn ≡ 1 (mod 4). 2. (4 pts) Let p ∈ N be a prime such that p ≡ 1 (mod 4). Prove that �3 p � = �p 3 � . 3. (7 pts) Use the previous questions to prove that if Fn is prime, then 3(Fn−1)/2 ≡ −1 (mod Fn). 4. (15 pts) Conversely, prove that if 3(Fn−1)/2 ≡ −1 (mod Fn), then Fn is prime. Hint: Square both sides. What is Fn − 1, and what does this tell you about the multiplicative order of 3 mod Fn? 1 Exercise 3: The Solovay-Strassen test (40 pts) In this exercise, we fix an odd integer N ⩾ 3, not necessarily prime. Let N = r� i=1 pvi i be its factorization, where the pi are distinct primes. We define the Jacobi symbol by the formula � x N � = r� i=1 � x pi �vi ∈ Z for all x ∈ Z, where � x pi � is the usual Legendre symbol defined in class. In particular, if N is prime, then � x N � = � x N � . 1. In this question, we investigate some basic properties of the symbol � x N � . The sub-questions of this question are independent from each other. (a) (3pts) Prove that if x ≡ y (mod N), then � x N � = � y N � . (b) (6 pts) Prove that � x N � ̸= 0 ⇐⇒ x is invertible mod N. (c) (3 pts) Prove that � xy N � = � x N � � y N � . We now introduce the function S : (Z/NZ)× −→ (Z/NZ)× x �−→ � x N � x N−1 2 . 2. (10 pts) Prove that if N is prime, then S(x) = 1 for all x ∈ (Z/NZ)×. 3. The goal of this question is to prove that conversely, if N is not prime, then S(x) is not always 1. In order to make things easier, we will suppose that N is composite and squarefree, that is to say that N = p1p2 · · · pr with the pi distinct primes and r ⩾ 2. We define M = N/p1 = p2 · · · pr. (a) (10 pts) Prove that there exists a t ∈ Z such that � t p1 � = −1 and that t ≡ 1 (mod M). Hint: CRT. (b) (8 pts) Prove that if t is as in the previous question, then S(t) ̸= 1. Hint: Compute S(t) mod M. END 2