Intersective Polynomials and Hensel’sLemmabyAndrea May HydeB.Sc. Hons., The University of British Columbia, 2012A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)April 23 2014c© Andrea May Hyde, 2014AbstractAn intersective polynomial is a polynomial with integer coefficients that has no rationalroots, but has a root modulo every integer greater than 1. These polynomials have beendifficult to find using traditional methods. In this thesis, we employ elementary methods,namely Hensel’s Lemma and the Chinese remainder theorem, to allow us to create threenew infinite families of intersective polynomials.In order to create a candidate intersective polynomial, we employ methods from Ga-lois theory. We multiply together carefully chosen polynomials that define subfields of asplitting field to create our candidate. We chose the subfields by first finding the n-cover,a collection of n proper subgroups, of the Galois group and identifying the correspondingsubfields. We multiply the minimal polynomials of the subfields of the chosen splittingfields together to create the candidate intersective polynomial.From our method of creating candidates we can see that intersective polynomials haveat least two irreducible factors. In order to prove that these polynomials have a root moduloevery integer greater than 1, we examine each factor modulo certain prime numbers anddetermine which sets of primes admit solutions for each factor. We then use Hensel’sLemma to lift those solutions to infinitely high powers of the particular primes. Finally,we combine the solutions modulo prime powers by using the Chinese remainder theoremto show that the polynomial has solutions modulo every integer greater than 1.Through the method outlined above, we have created three infinite families of intersec-tive polynomials: (x3 − n)(x2 + 3) when the prime factors of n are of the form 3k + 1 andn ≡ 1 (mod 9); (x2 − a)(x2 − b)(x2 − a1b1) when at least one of a, b, a1b1 is congruent to1 modulo 8 and for every odd prime p at least one of the Legendre symbols(ap),(bp),(a1b1p)has the value +1; and (xq − n)(xq−1 + xq−2 + · · ·+ x+ 1) when the prime factorsof n are kq + 1 and n ≡ 1 (mod q2) for an odd prime q.In the last chapter, we treat some special cases of intersective polynomials which willbe considered in detail in future work.iiPrefaceChapter 5.1 will appear in American Mathematical Monthly in 2014. It was acceptedon April 3, 2013, and was co-written by Paul D. Lee and Blair K. Spearman. It appearshere with permission from the co-authors and AMM.Chapter 5.2 appeared in International Mathematical Forum, Vol. 8, 2013, no. 25-28,p 1225-1232. It was accepted on June 16, 2013 and was co-written by Blair K. Spear-man. It appears here with permission of the co-author and under the Creative CommonsAttribution License.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Elementary Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Algebraic Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3 Group Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4 Galois Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Chapter 2: Hensel’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Chapter 3: Galois Theory and the Construction of Intersective Polynomials 16Chapter 4: Cyclotomic Polynomials . . . . . . . . . . . . . . . . . . . . . . . . 20Chapter 5: The Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.1 Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any Integer . . . . . . . . . 235.1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.1.2 The Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Products of Quadratic Polynomials With Roots Modulo Any Integer . . . . 275.2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27ivTABLE OF CONTENTS5.2.2 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285.2.3 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305.3 Polynomials (xq − n)Φq(x) Solvable Modulo Any Integer . . . . . . . . . . . 325.3.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.3.2 The Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Chapter 6: Conclusions and Further Work . . . . . . . . . . . . . . . . . . . 406.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.2 Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.2.1 A Specific Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.2.2 A Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.2.3 An Intersective Polynomial With Galois Group C3 × C3 . . . . . . . 47vList of TablesTable 5.1 Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any Integer . . . . . . 27Table 5.2 Products of Quadratic Polynomials With Roots Modulo Any Integer 32Table 5.3 The Smallest Intersective Polynomials (xq − n) Φq(x) . . . . . . . . . 39viAcknowledgementsI would like to thank Dr Blair Spearman, my supervisor, for his support and helpthroughout my studies. This work would not have been possible with out him. Thank youto Dr Rebecca Tyson for introducing me to the world of research, for being an inspiration,and for offering her guidance and friendship; Drs Qiduan Yang, Javad Tavakoli, and Re-becca Tyson, my committee, for all of their work; Dr Jim Bailey for showing me how to fallin love with math; Dr Richard Hewko for holding my hand in my very shaky first steps; myfellow grad students, Paul Lee, Stephen Brown, and Lindsey Reinholz, for showing me theway and offering their advice and experience for me to follow; Cindy Bourne and everyoneinvolved with the Math and Science Centre for giving me the opportunity to grow as atutor and a leader; my friends for listening to my endless math talk and reminding me toquit talking math and have fun; and last, but not least, my family. They have given me asolid foundation in which to sink my roots in order to stretch my branches far and wide.viiDedicationThis work is dedicated to my Grandparents, Mike and Mary Hyde, and Fred and MayJessee. To Gran and Papa, for teaching me about grace, dignity, and strength, and forgiving me the gift of education; and to Grama and Grandad, for teaching me to love andlaugh, and for giving me the gift of nature. Thank you.viiiChapter 1IntroductionIntersective polynomials are an interesting type of polynomial. They are a counterexample for the Local-Global Principle which states that the existence or non-existenceof solutions in the rational numbers (global solutions) of a diophantine equation can bedetected by studying the solutions modulo p, for all primes p (local solutions). In math-ematics, we generally expect that if we can find a solution to a problem in a small area,we will be able to generalize that solution to the larger area we are studying. Intersectivepolynomials, however, have solutions in every small area, but no solution overall.Definition 1.1 (Intersective Polynomial). Let f(x) be a polynomial with integer coeffi-cients. f(x) is non-trivially intersective if f(x) has no rational roots but f(x) ≡ 0 (mod m)is solvable for all integers m > 1.Intersective polynomials appear to have been given their name in the late 2000’s [? ? ].They have been studied by various people under various names for many years. However,much of the work that has been done relies on Galois theory and algebraic number theoryand can be difficult for readers and students to understand [? ? ]. Our approach isdifferent; we have harnessed the power of Hensel’s Lemma and elementary number theoryto prove the existence of several infinite families of intersective polynomials.Our approach is rooted in elementary number theory, so we begin with some definitionsand basic theories that underlie the more advanced work. A curious reader is encouragedto read [? ? ] or any other elementary number theory text for more detail and any proofsthat have been omitted.1.1 Elementary Number TheoryThe definition of an intersective polynomial includes the statement that they are solv-able modulo m for any integer m larger than 1. Hence any study of intersective polynomialsmust begin with a study of congruences and modular arithmetic.11.1. Elementary Number TheoryDefinition 1.2 (Congruence). If an integer m, not zero, divides the difference a − b, wesay that a is congruent to b modulo m and write a ≡ b (mod m). If a− b is not divisibleby m, we say that a is not congruent to b modulo m, and we write a 6≡ b (mod m) [? ].We can see that if m | a − b then −m | a − b so we can generally assume that m is apositive integer. There are many properties of congruences that are used throughout thisthesis.Theorem 1.3. Let a, b, c, d be integers. Then:1. a ≡ b (mod m), b ≡ a (mod m), and a− b ≡ 0 (mod m) are equivalent statements.2. If a ≡ b (mod m) and b ≡ c (mod m), then a ≡ c (mod m).3. If a ≡ b (mod m) and c ≡ d (mod m), then a+ c ≡ b+ d (mod m).4. If a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m).5. If a ≡ b (mod m) and d | m, d > 0, then a ≡ b (mod d)6. If a ≡ b (mod m), then ac ≡ bc (mod m) for c > 0.7. If a ≡ b (mod m), then there is an integer k such that a = b+ km.The Fundamental Theorem of Arithmetic and its associated lemmas and corollaries arepowerful tools that allow us to break large number into their prime factors and study themin these smaller components.Theorem 1.4 (The Fundamental Theorem of Arithmetic). Every positive integer greaterthan 1 can be written uniquely as a product of primes, with the prime factors in the productwritten in nondecreasing order.Definition 1.5 (Greatest Common Divisor). The greatest common divisor of two integersa and b, which are not both 0, is the largest integer that divides both a and b. We writegcd(a, b) = d.Definition 1.6 (Relatively Prime). If the greatest common divisor of the integers a andb is 1, then a and b are said to be relatively prime. That is, if gcd(a, b) = 1, a and b arerelatively prime. We may also say that a and b are co-prime.21.1. Elementary Number TheoryLemma 1.7. If a, b, and c are positive integers such that gcd(a, b) = 1 and a | bc, thena | c.Lemma 1.8. If p divides a1a2 · · · an, where p is a prime and a1, a2, · · · , an are positiveintegers, then there is an integer i with 1 ≤ i ≤ n such that p | ai.Corollary 1.9. If p | ab for some p prime and a, b ∈ Z, then p | a.Theorem 1.10. The greatest common divisor of the integers a and b, not both 0, is theleast positive integer that is an integer linear combination of a and b.Corollary 1.11. If a and b are relatively prime integers, then there are integers m and nsuch that ma+ nb = 1.Theorem 1.12. Let a, b, and m be integers such that m > 0 and gcd(a,m) = d. If d - b,then ax ≡ b (mod m) has no solutions. If d | b, then ax ≡ b (mod m) has exactly dincongruent solutions modulo m.Definition 1.13 (Modular Inverse). Given an integer a with gcd(a,m) = 1, a solution ofax ≡ 1 (mod m) is called a modular inverse of a modulo m. The modular inverse of a maybe identified as a¯.Theorem 1.14. If a ≡ b (mod m1), a ≡ b (mod m2), . . . , a ≡ b (mod mk), where a, b,m1, . . . ,mkare integers with m1, . . . ,mk positive, thena ≡ b (mod [m1, . . . ,mk]),where [m1, . . . ,mk] is the lowest common multiple of m1, . . . ,mk.The Fundamental Theorem of Arithmetic allows us to break numbers down; the ChineseRemainder Theorem lets us combine them again with a series of congruences.Theorem 1.15 (The Chinese Remainder Theorem). Let m1,m2, · · · ,mr be pairwise rel-atively prime positive integers. Then the system of congruencesx ≡ a1 (mod m1),x ≡ a2 (mod m2),......x ≡ ar (mod mr),31.1. Elementary Number Theoryhas a unique solution modulo M = m1m2 · · ·mr.Proof. First, we construct a solution to the system of congruences. Let Mk = Mmk =m1m2 · · ·mk−1mk+1 · · ·mr. We know that gcd(Mk,mk) = 1 as all of the mi, i = 1, 2, . . . , r,are relatively prime. Hence, by Theorem 1.12 we can find an inverse, yk, of Mk modulomk so that Mkyk ≡ 1 (mod mk). We now form the sumx = a1M1y1 + a2M2y2 + · · ·+ arMryr.The integer x is a simultaneous solution of the r congruences. To demonstrate this, wemust show that x ≡ ak (mod mk) for k = 1, 2, . . . , r. Since mk | Mj whenever j 6= k,we have Mj ≡ 0 (mod mk). Therefore, in the sum for x, all terms except the kth termare congruent to 0 (mod mk). Hence, x ≡ akMkyk ≡ ak (mod mk), since Mkyk ≡ 1(mod mk). We now show that any two solutions are congruent modulo M . Let x0 andx1 both be simultaneous solutions to the system of r congruences. Then, for each k,x0 ≡ x1 ≡ ak (mod mk), so that mk mod (x0 − x1). Using Theorem 1.14, we see thatM | (x0 − x1). Therefore, x0 ≡ x1 (mod M). This show that the simultaneous solution ofthe system of r congruences is unique modulo M .There are times when we need to explore the relationship between prime numbersand composite numbers through congruences. Fermat’s Little Theorem and the Euler PhiFunction provide us with these tools.Theorem 1.16 (Fermat’s Little Theorem). Let p be a prime. If p - a then ap−1 ≡ 1(mod p). For every integer a, ap ≡ a (mod p)Definition 1.17 (Euler’s Phi Function). [? ] Also known as Euler’s Totient function. Letn ∈ Z+. φ(n) is the number of positive integers, not exceeding n, relatively prime to n.There are four main properties of the Euler Phi function that we will employ, eitherdirectly or indirectly1. Let p be prime and a ∈ Z, then φ(pa) = pa − pa−1.2. Let m,n ∈ Z and gcd(m,n) = 1, then φ(mn) = φ(m)φ(n).3. Let n ∈ Z and n > 2, then φ(n) is even.4. Let n ∈ Z, then∑d|n φ(d) = n.41.1. Elementary Number TheoryThe proof of these can be found in [? , pp. 233-244].Theorem 1.18 (Euler’s Generalization of Fermat’s Little Theorem). If gcd(a,m) = 1,then aφ(m) ≡ 1 (mod m).Definition 1.19 (Order Modulo n). Let a and n be relatively prime positive integers.Then, the lease positive integer x such that ax ≡ 1 (mod n) is called the order of a modulon. We denote this by ordna.Theorem 1.20. If a and n are relatively prime integers with n > 0, then the positiveinteger x is a solution of the congruence ax ≡ 1 (mod n) if and only if ordna | x.Corollary 1.21. If a and n are relatively prime integers with n > 0, then ordna | φ(n).One of the key elements of the proofs found in this work is the ability to determinewhether or not a number is a square modulo a given integers. The following definitionsand lemma give us that ability.Definition 1.22 (Quadratic Residue). If m is a positive integer, we say that the integera is a quadratic residue of m if gcd(a,m) = 1 and the congruence x2 ≡ a (mod m) has asolution. If the congruence has no solution, we say that a is a quadratic non-residue of m.Lemma 1.23. Let p be an odd prime and a an integer not divisible by p. Then thecongruence x2 ≡ a (mod p) has either no solutions or exactly two incongruent solutionsmodulo p.Definition 1.24 (Legendre Symbol). Let p be an odd prime and a be an integer notdivisible by p. The Legendre symbol(ap)is defined by(ap)=1 if a is a quadratic residue of p;−1 if a is a quadratic non-residue of p.Legendre Symbols have the following useful properties:Theorem 1.25. Let p be an odd prime and a and b be integers not divisible by p. Theni) if a ≡ b (mod p), then(ap)=(bp).ii)(abp)=(ap)(bp).51.1. Elementary Number Theoryiii)(a2p)= 1.The value of a Legendre Symbol can be calculated directly using Euler’s Criterion(ap)≡ ap−12 (mod p).As a consequence of this criterion, we have two lawsDefinition 1.26 (First Law of Quadratic Reciprocity). If p is an odd prime then(pq)=(qp)if p ≡ 1 (mod 4) or q ≡ 1 (mod 4) (or both);−(qp)if p ≡ q ≡ 3 (mod 4)Definition 1.27 (Second Law of Quadratic Reciprocity). If p is an odd prime then(−1p)=1 if p ≡ 1 (mod 4);−1 if p ≡ −1 (mod 4)As we deepen our study of intersective polynomials we begin to encounter polynomialsof larger degree. Some of the calculations associated with higher degree polynomials aresimplified by using the Binomial Theorem and associated lemmas.Definition 1.28 (Binomial Coefficient). Let m and k be nonnegative integers with k ≤ m.The binomial coefficient(mk)is defined by(mk)=m!k!(m− k)!=m(m− 1) · · · (m− k + 1)k!Theorem 1.29 (Binomial Theorem). Let x and y be variable, and n be a positive integer.Then(x+y)n =(n0)xn+(n1)xn−1y+(n2)xn−2y2+. . .+(nn− 2)x2yn−2+(nn− 1)xyn−1+(nn)yn,or, using summation notation,(x+ y)n =n∑j=0(nj)xn−jyj .61.2. Algebraic Number TheoryLemma 1.30. An integer n ≥ 2 is prime if and only if all of the intermediate binomialcoefficients(n1),(n2), . . . ,( nn−1)are divisible by n.Proof. When p is prime, p divides(pk)=p(p− 1)(p− 2) · · · (p− k + 1)k!∀ 0 < k < pbecause(pk)∈ N and the numerator has a prime factor p but the denominator does not.When n is composite, let p be the smallest prime factor of n and let k = n/p. Then0 < p < n and(np)=n(n− 1)(n− 2) · · · (n− p+ 1)p!=k(n− 1)(n− 2) · · · (n− p+ 1)(p− 1)!6≡ 0 (mod n).Otherwise, the numerator k(n − 1)(n − 2) · · · (n − p + 1) has to be divisible by n = kp.This can only be the case when (n − 1)(n − 2) · · · (n − p + 1) is divisible by p. But n isdivisible by p, so p does not divide n − 1, n − 2, . . . , n − p + 1 and because p is prime, weknow p - (n− 1)(n− 2) · · · (n− p+ 1), so the numerator cannot be divisible by n.In other words, Lemma 1.30 says that p |(pk)∀ 0 < k < p for a prime p.1.2 Algebraic Number TheoryOur work also incorporates parts of algebraic number theory, mainly elements of fieldtheory, which are outlined below. More information and detail can be found in [? ] [? ],or [? ].Definition 1.31 (Algebraic Number). [? ] Let α ∈ C. Then α is algebraic over Q if thereexists a nonzero polynomial p over Q such that p(α) = 0.Definition 1.32 (Minimal Polynomial). [? ] The minimal polynomial of an algebraiccomplex number α is the monic polynomial p(x) in Q[x] of smallest degree such thatp(α) = 0.The reducibility of a polynomial is important because it determines how we find theroots of that polynomial, and whether those roots will be integers, rationals, real, orcomplex numbers.71.2. Algebraic Number TheoryDefinition 1.33 (Irreducible). [? ] A nonzero, nonunit element a of an integral domainD is said to be irreducible if a = bc, where b, c ∈ D, implies that either b or c is a unit .For the purposes of this work, the reader may take irreducible over K to mean thata polynomial cannot be factored into two or more polynomials of smaller degree withcoefficients in K, where K is a field.Lemma 1.34 (Gauss’s Lemma). [? ] Let f be a polynomial over Z that is irreducible overZ. Then f , considered as a polynomial over Q, is also irreducible over Q [? ]There are a variety of methods that can be used to determine the reducibility of apolynomial.Theorem 1.35 (Scho¨nemann’s Irreducibility Criterion). Let f(x) ∈ Z[x] have degree n > 0and assume that there is a prime p and and integer a such thatf(x) = (x− a)n + pF (x), F (x) ∈ Z[x],degF (x) < n.If F (a) 6≡ 0(mod p), then f(x) is irreducible in Q[x] .Theorem 1.36 (Eisenstein’s Criterion). [? ] Let f(x) = anxn + . . .+ a1x+ a0 ∈ Z[x] beany primitive polynomial with integer coefficients and suppose there is a prime p such thati) p does not divide an,ii) p divides ai for i = 0, . . . , n− 1, andiii) p2 does not divide a0.Then f(x) is irreducible over Q.Definition 1.37 (Primitive Polynomial). [? ] A polynomial over Z is said to be primitiveif the greatest common divisor of its coefficients is 1.Careful reading will show that Scho¨nemann’s and Eisenstein’s criteria are equivalent.One of the areas of geometry that has long interested mathematicians is the division ofcircles into equal sized pieces. This question leads us to the next two definitions.81.2. Algebraic Number TheoryDefinition 1.38 (nth Roots of Unity). [? ] An element α of a field is an nth root of unityif αn = 1. It is a primitive nth root of unity if αn = 1 and αm 6= 1 for 0 < m < n. We willuse the notationζn = cos(2pikn)+ i sin(2pikn)= e2piik/n,where gcd(k, n) = 1, to represent the primitive nth root of unity.Definition 1.39 (Cyclotomic Polynomial). [? ] The cyclotomic polynomials, Φn(x) ∈Z[x], are the minimal polynomials for the primitive nth roots of unity whereΦn(x) =∏gcd(k,n)=1(x− e2piik/n)with Φn(x) irreducible over Q for all n ∈ Z, n > 0.For example, the third cyclotomic polynomial, Φ3(x) isΦ3(x) =∏gcd(k,3)=1(x− e2piik/3)= (x− e2pii/3)(x− e4pii/3)= x2 + x+ 1We also require some more abstract definitions about the relationships of families ofnumbers.Definition 1.40 (Integral Domain). [? ] An integral domain is a commutative ring thathas a multiplicative identity but no divisors of zero. An integral domain D is called a fieldif for each a ∈ D, a 6= 0, there exists b ∈ D with ab = 1.For example, Z = {0,±1,±2, . . .} is an integral domain.Definition 1.41 (Ideal). [? ] An ideal I of an integral domain D is a nonempty subsetwhich is closed under addition and scalar multiplication such that ra ∈ I for all r ∈ D anda ∈ I..We see that Z is also an ideal of itself.Definition 1.42 (Proper Ideal). [? ] An ideal I of an integral domain D is called a properideal of D if the generator of I is not equal to 0, 1, or a unit.91.3. Group TheoryThus a proper ideal of an integral domain D is an ideal I such that {0} ⊂ I ⊂ D. Forany positive integer k 6= 1, the set kZ = {0,±k,±2k, . . .} is a proper ideal of Z.Definition 1.43 (Prime Ideal). [? ] A proper ideal P of an integral domain D is called aprime ideal ifa, b ∈ D and ab ∈ P =⇒ a ∈ P or b ∈ P.1.3 Group TheoryGroup theory has its beginnings in the work of Euler, Gauss, Lagrange, Abel, andGalois, amongst others. They studied the way families of numbers related to one another.We draw on group theory in order to understand the Galois theory required to createintersective polynomials.The following definitions can be found in any abstract algebra text book, but theseones are from [? ].Definition 1.44 (Group). A group 〈G, ?〉 is a set G, closed under a binary operation ?,such that the following axioms are satisfied:i) G1: ? is associative.ii) G2: G contains an identity element e.iii) G3: For every element a in G, there exists b in G such that ab = e = ba.Definition 1.45 (Subgroup). If a subset H of a group G is closed under the binaryoperation of G and if H with the induced operation from G itself is a group, then H is asubgroup of G.Note that by this definition, G can be defined as a subgroup of itself. We call G animproper subgroup of G, while all the others are proper subgroups. The identity element{e} is called the trivial subgroup of G.Definition 1.46 (Cyclic Group). Given a group G and an element a in G, if G = {an :n ∈ Z} then a is a generator of G and the group G = 〈a〉 is cyclic.Definition 1.47 (Symmetric Group). Let A be the finite set {1, 2, . . . , n}. The group ofall permutations of A is the symmetric group on n letters, and is denoted by Sn. Note thatSn has n! elements.101.4. Galois TheoryThe symmetric group on three elements, S3, which we encounter later in this work,can be visualized as the rotations and reflections of an equilateral triangle. We see that|S3| = 3! = 6 by the above note, and that S3 = {e, (12), (13), (23), (123), (132)} where thevertices of the triangle are called 1, 2, and 3, so that (12) represents a reflection wherevertices 1 and 2 move, and vertex 3 stays stationary, and (123) and (132) represent thetwo directions of rotation of the triangle.1.4 Galois TheoryGalois theory provides a connection between group theory and field theory. Thereare certain problems in field theory that are easier to solve when viewed as group theoryproblems, and vice-versa. Given the significance of Galois theory, there are many bookswritten on the subject. The main reference that we have used is [? ], but [? ] has alsoprovided useful insight.Definition 1.48 (Field Extension). A field E is an extension field of a field F if F ≤ E.We denote the field extension by stating the initial field and following it with theextension in brackets. For example, the complex numbers C can be represented at the realnumbers with the imaginary numbers as an extension R(i). Most often we will talk aboutextensions to Q.Definition 1.49 (Galois Group). If K is a finite normal extension of a field F , thenG(K/F ) is the Galois group of K over F .Definition 1.50. G(F/K) is the set of field automorphisms of K that fix F . It is a groupunder composition.Definition 1.51 (Finite Normal Extension). A finite extension K over F is a finite normalextension of F if K is a splitting field over F .Definition 1.52 (Normal Extension). If an extension field K of a field F is of finitedimension n as a vector space over F , then K is a finite extension of degree n over F . Weshall let [K : F ] be the degree n of K over F .Definition 1.53 (Splitting Field). If K is a field extension over F , and f is a polynomialover F , then f splits over K if it can be expressed as a product of linear factors f(x) =k(x − α1) · · · (x − αn) where k, α1, . . . , αn ∈ K. The splitting field is the intersection offields over which f splits.111.4. Galois TheoryDefinition 1.54 (Separable). A polynomial f over K is separable if the degree of f isgreater than or equal to 1 and all of the roots have multiplicity 1.Let’s take a simple example to illustrate the definitions.It is possible to find two or more polynomials that share the same field extension. Let’slook at x2 + x+ 1 and x2 + 3. We saw previously that x2 + x+ 1 is the third cyclotomicpolynomial, Φ3(x), and that its roots aree2pi/3 = cos(2pi3)+ i sin(2pi3)= −12+ i√32=−1 + i√32= ωande4pi/3 = cos(4pi3)+ i sin(4pi3)= −12− i√32=−1− i√32= −1− ωClearly these roots, ω and −1− ω, are in the field extension Q(i√3).Next let’s look at the roots of x2 + 3.x2 + 3 = 0 =⇒ x2 = −3 =⇒ x = ±i√3which is also in Q(i√3). Hence these two polynomials share the same field extension.We will now explore the more complicated aspects of intersective polynomials, includingtheir background and formation, and the key lemmas that we use in the proof of the mainresults.12Chapter 2Hensel’s LemmaHensel’s Lemma can be found in many elementary number theory text books. It iscommonly used to find solutions to equations modulo a particular prime. We have takenthis ability and used it to solve equations modulo all primes.Theorem 2.1 (Hensel’s Lemma). [? ] Suppose that f(x) is a polynomial with integralcoefficients. If f(a) ≡ 0(mod pj) andf ′(a) 6≡ 0(mod p), then there is a unique t(mod p)such that f(a+ tpj) ≡ 0(mod pj+1).As stated in [? ], if f(a) ≡ 0 (mod pj), f(b) ≡ 0 (mod pk), j < k, and a ≡ b (mod pj),then we say that b lies above a, or a lifts to b. If f(a) ≡ 0 (mod pj), then the root a iscalled nonsingular if f ′(a) 6≡ 0 (mod p); otherwise it is singular. By Hensel’s Lemma wesee that a nonsingular root a (mod p) lifts to a unique root a2 (mod p2). Since a2 ≡ a(mod p), it follows that f ′(a2) ≡ f ′(a) 6≡ 0 (mod p). By a second application of Hensel’slemma we may lift a2 to form a root a3 of f(x) modulo p3, and so on. In general, we findthat a nonsingular root a modulo p lifts to a unique root aj modulo pj for j = 1, 2, . . .. Wecan see that this sequence is generated by means of the recursionaj+1 = aj − f(aj)f ′(a)where f ′(a) is an integer chosen so that f(aj)f ′(a) ≡ 1 (mod p).For example, solve x2 + x+ 47 ≡ 0 (mod 73).x2 + x+ 47 ≡ 0 (mod 7) has solutions x ≡ 1 (mod 7) and x ≡ 5 (mod 7)(1)2 + 1 + 47 = 49 ≡ 0 (mod 7)(5)2 + 5 + 47 = 77 ≡ 0 (mod 7).Next we take the derivative, f ′(x) = 2x+ 1, and evaluate at each of the roots to determine13Chapter 2. Hensel’s Lemmaif they are nonsingular.f ′(1) = 2(1) + 1 = 3 6≡ 0 (mod 7)f ′(5) = 2(5) + 1 = 11 6≡ 0 (mod 7)Hence 1 and 5 are nonsingular roots modulo 7.Next we consider f ′(1) = 3. We can take f ′(1) = 3 = 5 so that3 · 5 = f ′(1)f ′(1) ≡ 1 (mod 7)and apply the recursion formulaa2 = a1 − f(a1)f ′(a)= 1− 49 · 5.But, as a2 will be considered modulo 72, we can takea2 ≡ a1 − f(a1)f ′(a) (mod 72)≡ 1− 49 · 5 (mod 72)≡ 1 (mod 72).We can evaluate to see that f(a2) = f(a1) so thata3 = 1− 49 · 5 ≡ 99 (mod 73)and x ≡ 99 (mod 73) is a root of x2 + x + 47 ≡ 0 (mod 73). We repeat the process withthe root x ≡ 5 (mod 7) to see that x ≡ 243 (mod 73) is the other root and that there areno others.When a is a singular root we must apply a refined version of Hensel’s Lemma.Theorem 2.2 (Refined Hensel’s Lemma). [? ] Let f(x) be a polynomial with integralcoefficients. Suppose that f(a) ≡ 0(mod pj), that pτ ‖ f ′(a) and that j ≥ 2τ + 1. Ifb ≡ a(mod pj−τ ) then f(b) ≡ f(a)(mod pj) and pτ ‖ f ′(b). Moreover there is a uniquet(mod p) such that f(a+ tpj−τ ) ≡ 0(mod pj+1).As noted in [? ], since the hypotheses of the theorem apply with a replaced by a+tpj−τ14Chapter 2. Hensel’s Lemmaand (mod pj) replaced by (mod pj+1) but with τ unchanged, the lifting may be repeatedand continues indefinitely.Proof. We begin with a Taylor’s expansion of f(b)f(b) = f(a+ tpj−τ ) ≡ f(a) + tpj−τf ′(a) (mod p2j−2τ ).Here the modulus is divisible by pj+1 since 2j − 2τ = j + (j − 2τ) ≥ j + 1. Hencef(a+ tpj−τ ) ≡ f(a) + tpj−τf ′(a) (mod pj+1).Since both terms on the right hand side are divisible by pj , the term on the left side isdivisible by pj . When we divide through by pj we findf(a+ tpj−τ )pj≡f(a)pj+ tpj−τf ′(a)pj(mod p)≡f(a)pj+ tf ′(a)pτ(mod p).The coefficient t is relatively prime to p so there is a unique t (mod p) for which theright side is divisible by p. To conclude, we note that f ′(x) is a polynomial with integercoefficients so thatf ′(a+ tpj−τ ) ≡ f ′(a) (mod pj−τ )for any integer t. But j−τ ≥ τ+1, so this congruence holds (mod pτ+1). Since pτ exactlydivides f ′(a), we conclude that pτ exactly divides f ′(a+ tpj−τ ).15Chapter 3Galois Theory and theConstruction of IntersectivePolynomialsGalois theory is a large and complicated area of study. For the purposes of this work,we limit our explanations to only the parts that are required to understand the creationof intersective polynomials. Here we show how multiplying together carefully chosen poly-nomials that define subfields of a splitting field will give us candidates for intersectivepolynomials.For reference, we provide the Fundamental Theorem of Galois Theory.Theorem 3.1 (The Fundamental Theorem of Galois Theory). [? ] If L:K is a finitenormal field extension inside C, with Galois group G, and if we let F be the set of interme-diate fields, that is, subfields M such that K ⊆M ⊆ L, and let G be the set of all subgroupsH of G, then we define two maps∗ : F → G† : G → Fas follows: If M ∈ F , then M∗ is the group of all M -automorphisms of L. If H ∈ G, thenH† is the fixed field of H. The maps ∗ and † reverse inclusions, that is, M ⊆ M∗† andH ⊆ H∗†. Then:1. The Galois group G has order [L : K].2. The maps ∗ and † are mutual inverses, and set up an order-reversing one-to-onecorrespondence between F and G.16Chapter 3. Galois Theory and the Construction of Intersective Polynomials3. If M is an intermediate field, then[L : M ] = |M∗| [M : K] = |G|/|M∗|.4. An intermediate field M is a normal extension of K if and only if M∗ is a normalsubgroup of G.5. If an intermediate field M is a normal extension of K, then the Galois groups ofM :K is isomorphic to the quotient group G/M∗.It is beyond the scope of this work to prove the Fundamental Theorem of Galois theory.However, we make use of the relationship between the subfields M and the subgroups Hin order to create our candidate intersective polynomials.Proposition 3.2. If f(x) is intersective, then f(x) cannot be irreducible over Q.This was shown by Brandl, Bubbuloni, and Hupp [? ] when they proved that thereexists a prime number p such that f(x) ≡ 0 (mod p) is insolvable. Hence we study poly-nomials that are reducible over Q.We begin by studying polynomials of the form(x3 − n)(x2 + 3)and classifying those that are intersective. The most important factor here is x3−n. Thiscubic has discriminant −27n2 = (−3)(3n)2 which is not a square in Q so we know thatits Galois group is S3, the symmetric group on three elements (see definition 1.47 and thenote following for more detail on S3). S3 has order |S3| = 3! = 6, assuming n is not a cubein Q. If we allow n to be a cube in Q then x3 − n is solvable in Q and the polynomialwill not be intersective. Let the complex roots of x3 − n be θ1, θ2, and θ3. We can draw asubfield diagram for the splitting field of this polynomial as follows:17Chapter 3. Galois Theory and the Construction of Intersective PolynomialsNotice Q(√−3) ⊆ L as the square root of the discriminant is in L.√−27n2 = 3n√−3 ∈ LProposition 3.3. Intersective polynomials are formed by multiplying together polynomialsdefining subfields of the same splitting field.Note that the Galois group of (x3−n)(x2 + 3) is S3 , but the x2 + 3 factor is redundantas far as Galois theory is concerned since the root√−3 is already included in the splittingfield (see section 1.4 for details).Unfortunately we can’t just multiply together any polynomials defining some subfieldsof the splitting field. They must be carefully chosen.Definition 3.4 (n-cover). Let G be a Galois group and let L/Q be a normal extensionwith Galois group G. An n-cover of G is a collection of n proper subgroups, H1, H2,. . . ,Hn, of G such that the union of the Hi, i = 1, . . . , n, and their conjugates equals G, andthe intersection of the Hi, i = 1, . . . , n and their conjugates equals {e}, the identity.If you find an n-cover, H1, H2,. . . ,Hn, of G, then by Galois theory these correspond tosubfieldsK1,K2, . . . ,Kn of L. These are in turn defined by polynomials f1(x), f2(x), . . . , fn(x).Proposition 3.5. If f(x) is intersective thenf(x) = f1(x)f2(x) · · · fn(x)as previously defined.18Chapter 3. Galois Theory and the Construction of Intersective PolynomialsThe normal closure of a cubic field L = Q(n1/3,√−3) has Galois group S3 . Thesubgroup diagram for S3 iswhere {e, (123), (132)} = H1. The subgroups H2 = {e, (12)}, H3 = {e, (13)}, and H4 ={e, (23)} are conjugate and therefore a 2-cover of S3 is {H2, H1}. The subfield correspond-ing to {e, (12)} is defined by x3 − n, and the subfield corresponding to H1 is defined byx2 + 3 so that our candidate polynomial isf(x) = (x3 − n)(x2 + 3).It is important to note that no group is 1-coverable; 2-covers are the minimum, and thatcyclic groups are not n-coverable for any n.Definition 3.6. For each prime ideal ℘ (see definition 1.43) in L/Q, the decompositiongroup isG(℘) = {σ ∈ Gal(L/K) : σ(℘) = ℘}.Proposition 3.7. If you form the intersective candidate as in Proposition 3.5, you stillrequire the decomposition groups to be contained in the cover.It is clear to see that the construction of intersective polynomials is a detailed process.Previous proofs of intersective polynomials have relied on Galois theory and algebraicnumber theory. We avoid the use of algebraic number theory in this thesis through the useof Hensel’s Lemma.19Chapter 4Cyclotomic PolynomialsCyclotomic polynomials are the equations that arise from the division of a circle intoequal sized pieces. Using the unit circle, we can see that the solutions off(x) = xn − 1,the roots of unity, give the locations on the unit circle where the radial divisions must bemade. By joining those points, one can construct a polygon with n sides.The first few cyclotomic polynomials are [? ]Φ1(x) = x− 1Φ2(x) = x+ 1Φ3(x) = x2 + x+ 1Φ4(x) = x2 + 1Cyclotomic polynomials can be found using the equation∏d|nΦd(x) = xn − 1.For example, we derive Φ6(x)∏d|6Φd(x) = x6 − 1⇐⇒ Φ6(x) =x6 − 1Φ3(x)Φ2(x)Φ1(x)⇐⇒ Φ6(x) = x2 − x+ 1Note that the pth cyclotomic polynomial, where p is a prime, will always have the form20Chapter 4. Cyclotomic PolynomialsΦp(x) = xp−1 + xp−2 + · · ·+ x+ 1Cyclotomic polynomials are encountered in courses on abstract algebra, algebraic num-ber theory, and Galois theory. They were studied by Gauss, Eisenstein, Galois, andScho¨nemann, among many others, in the 18th and 19th centuries [? ? ] and continueto be studied by mathematicians today. Cyclotomic polynomials play a role in findingprime factorizations of integers of the form an − 1 [? ]. For example, to find the primefactorization of 511, we note that 511 = 512−1 = 29−1. By letting x = 2 in x9−1 we seex9 − 1 = (x− 1)(x2 + x+ 1)(x6 + x3 + 1)29 − 1 = (21 − 1)(22 + 2 + 1)(26 + 23 + 1)= 7 · 73.Since 73 is prime, we see that 511 has the prime factorization 7 · 73.Tools were simpler back in ancient Greece, but that made them no less interesting.The equivalent ideas of dividing a circle into n equal pieces or or of creating an n-gonusing only a compass and straight edge are one of the classical problems of geometry. Theancient Greeks determined that a circle could be divided into N even parts when N = 3or 5. Because the problem of bisecting an angle was a simple one, Euclid was able toconclude that a circle could be divided into N equal parts if N = 2k ·3m ·5n, where k is anynonnegative integer and m and n are either 0 or 1 [? ]. This meant that triangles, squares,pentagons, and hexagons could be constructed (the reader should see Euclid’s Elements forthe details of the constructions). The 7-sided heptagon, however, could not. Professionaland amateur mathematicians spent the next 2000 years or so trying to divide a circle into7 equal parts. This led many people to either expand or contract their social circles toavoid duels over dessert.In 1796, at the age of 18, Carl Friedrich Gauss proved that the heptadecagon (17-gon)was constructible. In fact, Gauss showed that an N -gon will be constructible if its primefactors are Fermat primes [? ], Fn, so thatN = 2k∏nFn,where the Fermat primes are defined as follows.21Chapter 4. Cyclotomic PolynomialsDefinition 4.1 (Fermat Primes). [? ] Fermat primes are primes of the form 22m+ 1.There are only 5 known: F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65537.This means that there are 25−1 = 31 N -gons that can be constructed using the Fermatprimes alone, and that those can each be divided further by powers of 2 [? ].Theorem 4.2. An n-gon is constructible if and only if φ(n)/2 = 2k for k ∈ N.For exampleφ(17) = 16,φ(17)2= 23so that the 17-gon is constructible butφ(7) = 6,φ(7)2= 6 6= 2kthe 7-gon is not.We will study the roots of certain cyclotomic polynomials modulo powers of primes inChapter 5.22Chapter 5The Main Results5.1 Polynomials (x3 − n)(x2 + 3) Solvable Modulo AnyIntegerSee [? ].5.1.1 BackgroundUp to this point, we have looked at the background required to understand and provethe existence of intersective polynomials. Now we would like to look at some of thesepolynomials in detail.Berend and Bilu prove a theorem which can be used to establish the intersective prop-erty for a given polynomial [? ]. They provide the examplef(x) = (x3 − 19)(x2 + x+ 1).The verification of the intersective property, that is, of confirming thatf(x) ≡ 0(mod m)is solvable for every m > 1, may proceed by showing that for each prime p and positiveinteger j, the congruencef(x) ≡ 0(mod pj)is solvable. General solvability then follows from the Chinese Remainder Theorem. For agiven prime p, one of the factors of f(x) is proven to be solvable mod pj for all positiveintegers j. In this note, we propose to use techniques from an undergraduate number theory235.1. Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any Integercourse to investigate polynomials of the formf(x) = (x3 − n)(x2 + x+ 1),or equivalentlyf(x) = (x3 − n)(x2 + 3),classifying those that are intersective. The equivalence of these two families is due to theeasily established fact that for a given prime p the congruencex2 + x+ 1 ≡ 0(mod pj)is solvable for all positive integers j if and only if the congruencex2 + 3 ≡ 0(mod pj)is solvable for all positive integers j. Berend and Bilu [? ] state that these polynomialshave the least possible degree to be intersective. The explanation of this involves Galoistheory and algebraic number theory. Avoiding these more advanced theories, we make useof results from an undergraduate number theory course, particularly Hensel’s Lemma anda refined version of Hensel’s Lemma. Our method not only establishes the intersectiveproperty for the polynomials we study, but enables a characterization of them, showingthat they form an infinite set. Before we begin, we impose two simple restrictions on thevalue of n in our polynomials (x3−n)(x2+3), the validity of which can easily be establishedby the reader. We assume that n is a positive integer and that n is cubefree. From ourdefinition of intersective, this implies that n 6= 1. Our main theorem is the following.Theorem 5.1. Let n be a cubefree positive integer, not equal to 1. Thenf(x) = (x3 − n)(x2 + 3)is intersective if and only if the prime factors of n are of the form 3k + 1 and n ≡ 1(mod9).Before giving the proof of this theorem, we require one more lemma involving powercongruences.245.1. Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any IntegerLemma 5.2. (see [? , p. 101]) If p is a prime and gcd(a, p) = 1, then the congruencext ≡ a(mod p) has d = gcd(t, p − 1) solutions if a(p−1)/d ≡ 1(mod p), and no solutionsotherwise.We are now ready to prove our theorem.5.1.2 The Main ResultProof. Assume that the prime factors of n are of the form 3k+ 1 and n ≡ 1(mod 9). Let pbe a prime.Case 1: Suppose that p ≡ 1(mod 3). For these primes, −3 is a quadratic residue mod p.To see this, we study cases. Since p ≡ 1 (mod 6), we take p ≡ 1 (mod 4), then(−1p)= 1and(3p)=(p3)=(13)= 1, so(−3p)= 1. If we take p ≡ 3 (mod 4), then(−1p)= −1 and(3p)= −(p3), so(−3p)= (−1)(−1) = 1 (see [? , p440, Exercise 3]). This means that thecongruence x2 + 3 ≡ 0(mod p) is solvable for some integer u which is clearly not divisibleby p. If p | u, then p | u2, but this implies that p | −3 which is clearly not true since thesmallest prime congruent to 1 modulo 3 is 7.Since the derivative of x2 + 3 evaluated at u equals 2u, which is again not divisible byp, we see that u is a nonsingular root and we may apply Hensel’s Lemma to conclude thatx2 + 3 ≡ 0(mod pj) is solvable for all positive integers j.Case 2: Suppose next that p ≡ 2(mod 3). Clearly p - n since n contains only prime factorsof the form 3k + 1.The factor x2 + 3 is insolvable mod p since, by the argument above, −3 is a quadraticnonresidue mod p.Applying Lemma 5.2 to the factor x3 − n, with t = 3, a = n, and noting that d =(3, p− 1) = 1, we see that x3 − n ≡ 0(mod p) is solvable if np−1 ≡ 1(mod p), which is trueby Fermat’s Little Theorem.Thus x3 − n ≡ 0(mod p) is solvable for some integer u.Since p - n, we see that p - u3 and hence p - u.We may apply Hensel’s Lemma, by observing that p - 3u2, the derivative of x3 − nevaluated at u, and conclude that x3−n ≡ 0(mod pj) is solvable for all positive integers j.255.1. Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any IntegerCase 3: Lastly, suppose that p = 3.The factor x2 + 3 has one solution mod 3 (namely x = 0). x2 + 3 ≡ 0 (mod 9) ⇐⇒x2 ≡ 6 (mod 9), but only 1, 4, and 7 are squares modulo 9, so x2 + 3 has no solutions mod32.Therefore, we consider the factor x3−n. Since n ≡ 1 (mod 9) we have n ≡ 1, 10, 19(mod33) which are all cubes modulo 27 so that x3 ≡ n (mod 33) is solvable. For solutions wemay choose x ≡ 1, 4, 7(mod 33), respectively.At the same time, the derivative of x3−n, 3x, evaluated at 1, 4, and 7 equals 3, 12, and21, respectively and is exactly divisible by 3 in all cases.These are singular roots so we apply Refined Hensel’s Lemma with j = 3, τ = 1, andrecalling the remark after Refined Hensel’s Lemma, we conclude that x3 − n ≡ 0(mod 3j)is solvable for all positive integers j.Finally, we employ the Chinese Remainder Theorem. By creating a series of congruencesmodulo the prime power factorization, pj11 pj22 · · · pjrr for p prime and j ∈ Z , of any integerm > 1, we can find a solution to f(x) = (x3−n)(x2 + 3) modulo m for all positive integersm.This establishes the intersective property.Conversely, suppose that (x3− n)(x2 + 3) is intersective with n cubefree and not equalto 1. Let p be a prime.Case 1: First suppose that p ≡ 2(mod 3). For such a prime, x2 + 3 ≡ 0(mod p) is insolv-able since −3 is a quadratic nonresidue mod p as noted earlier. Therefore, we must havex3−n ≡ 0(mod pj) solvable for all positive integers j. It is easy to show that if p divides nthen p must also divide any solution x. We then see that the congruence x3 ≡ n(mod p3)is only solvable if n is divisible by p3, but this is a contradiction since n is cubefree. Hencep - n and n has no prime factors of the form 3k + 2.Case 2: Suppose now that p = 3. Since x2 + 3 ≡ 0(mod 9) is insolvable we must havex3−n ≡ 0(mod 3j) solvable for all positive integers j. By the same arguments as in Case 1,we require 3 - n, for otherwise x3−n ≡ 0(mod 33) is insolvable as n is cubefree. Therefore3 is not a prime factor of n, and thus the prime factors of n must have the form 3k + 1.265.2. Products of Quadratic Polynomials With Roots Modulo Any IntegerTo complete the classification part of our proof, we study the solvability of x3 − n ≡0(mod 32). The nonzero cubes modulo 9 are congruent to 1 and 8. Combining this withthe previously established fact that the prime factors of the positive integer n are of theform 3k + 1, we deduce that n ≡ 1(mod 9) as required.We close by giving some examples of intersective polynomials obtained from our theo-rem.Table 5.1: Polynomials (x3 − n)(x2 + 3) Solvable Modulo Any IntegerFactorization of n Intersective Polynomial37 (x3 − 37)(x2 + 3)7 · 13 (x3 − 91)(x2 + 3)163 (x3 − 163)(x2 + 3)19 · 37 (x3 − 703)(x2 + 3)72 · 61 (x3 − 2989)(x2 + 3)5.2 Products of Quadratic Polynomials With RootsModulo Any Integer(See [? ])5.2.1 BackgroundIntersective polynomials need to have at least two irreducible factors. They may havemore, however. A common example of this phenomenon is the following product of threequadratic polynomials.f(x) = (x2 − 2)(x2 − 17)(x2 − 34).This example or others very similar appear in [? ], [? ], [? ], [? ] and [? ]. We note thatthe three quadratic polynomials in f(x) define quadratic subfields of a bicyclic quartic fieldQ(√2,√17).This type of product is necessary in order to form intersective polynomials. An explanationof this in terms of Galois theory can be found in [? ] or [? ]. In this paper we shall treat the275.2. Products of Quadratic Polynomials With Roots Modulo Any Integergeneral case of these products of quadratic polynomials, which we denote by f(x). Specialfamilies will be considered as corollaries. We shall confirm thatf(x) ≡ 0(mod m)is solvable for every m > 1 by showing that for each prime p and positive integer j, thecongruencef(x) ≡ 0(mod pj)is solvable. General solvability then follows from the Chinese Remainder Theorem. For agiven prime p, one of the factors of f(x) is proven to be solvable mod pj for all positiveintegers j. We state our main theorem next, recalling the Legendre symbol(np)whichtakes the values +1 if n is a quadratic residue modulo p, −1 if n is a quadratic non-residuemodulo p, or 0 if p divides n.5.2.2 Main ResultTheorem 5.3. Let a, b be squarefree integers, not equal to 1 such that ab is not equal tothe square of an integer. Set ` = gcd(a, b) and define a1 and b1 by a = a1` and b = b1`. Setf(x) = (x2 − a)(x2 − b)(x2 − a1b1).Thenf(x) ≡ 0(mod m)is solvable modulo every integer m > 1 if and only if at least one of a, b, a1b1 is congruentto 1 modulo 8 and for every odd prime p at least one of the Legendre symbols(ap),(bp),(a1b1p),has the value +1.We require two additional lemmas to complete this proof.Lemma 5.4. Suppose that p is an odd prime and r is a squarefree integer. Then thecongruencex2 ≡ r(mod pj)285.2. Products of Quadratic Polynomials With Roots Modulo Any Integeris solvable for j = 1, 2, . . . .if and only if(rp)= +1.Proof Since r is squarefree, solvability of the given congruence requires p - r. Specializingto solvability mod p shows that(rp)= +1If(rp)= +1 then the congruencex2 ≡ r(mod p)is solvable with integer solution x = x0. Sincex20 ≡ r(mod p)and p - r we see that p - x0 so that x0 is a nonsingular root of this congruence. Thus wemay employ Proposition 1 to lift this solution to a solution of the congruencex2 ≡ r(mod pj)for j = 1, 2, . . . , completing the proof. Lemma 5.5. Suppose that r is a squarefree integer. Then the congruencex2 ≡ r(mod 2j)is solvable for j = 1, 2, . . . . if and only if r ≡ 1(mod 8).Proof Since r is squarefree, solvability of the given congruence modulo all powers of 2requires r to be odd. Since odd squares are congruent to 1 modulo 8, we have r ≡ 1(mod8). If r ≡ 1(mod 8) then the congruencex2 ≡ r(mod 23)is solvable with solution x = 1. Although x = 1 is a singular root of this congruence, wemay employ Refined Hensel’s Lemma, with j = 3 and τ = 1 and lift this root to a solutionofx2 ≡ r(mod 2j)295.2. Products of Quadratic Polynomials With Roots Modulo Any Integermodulo all powers of 2 as required. We now give the proof of our theorem.Proof Assume that f(x) = (x2−a)(x2− b)(x2−a1b1) ≡ 0(mod m) is solvable for everyinteger m > 1. Then in particular this polynomial congruence is solvable modulo powersof 2 so that at least one of the factors of f(x) is solvable modulo 8. Since a congruence ofthe form x2 ≡ r(mod 8) is solvable only if r ≡ 1(mod 8), Lemma 5.5 establishes the firststatement in our theorem.Next, for any odd prime p, we must have at least one of the factors of f(x), say (x2−r),solvable modulo pj , j = 1, 2, 3, . . . . As r is squarefree we have p - r and thus(rp)= +1 asrequired. This establishes the second statement in our theorem.On the other hand, assuming that p is an odd prime and one of(ap),(bp),(a1b1p)has the value +1, we may use Lemma 5.4 to deduce solvability of a factor of f(x) andhence f(x) modulo pj , j = 1, 2, 3, . . . . Similarly, assuming that the constant term of oneof the factors of f(x) is of the form 8k + 1 we may use Lemma 5.5 to conclude that thisfactor is solvable modulo 2j , j = 1, 2, 3, . . . and conclude that f(x) is solvable modulo 2j ,j = 1, 2, 3, . . . .Solvability modulo m for any positive integer m follows from the Chinese RemainderTheorem. This concludes the proof of our theorem. 5.2.3 CorollariesWe use our theorem to construct three simple families of polynomials, solvable moduloevery positive integer m.Corollary 5.6. Let n be an odd squarefree integer with n 6= 1. Thenf(x) = (x2 − 2)(x2 − n)(x2 − 2n)is solvable modulo m for every positive integer m if and only if the prime factors of n have305.2. Products of Quadratic Polynomials With Roots Modulo Any Integerthe form 8k ± 1 and n ≡ 1(mod 8).Proof If f(x) has a root modulo every positive integer m, then our theorem requiresthat one factor of f(x) have constant term with the form 8k+ 1. Clearly this term must ben. Suppose that p is an odd prime. Our theorem implies that one of the Legendre symbols(2p),(np),(2np)has the value +1. This is automatic if p - n. In this case, we see that if(np)= 1, theconditions are satisfied. If not, then(np)= −1 and(2p)= −1 so that(2np)= 1 by themultiplicativity of the Legendre Symbol. If p | n then from our theorem we deduce that(2p)= 1implying thatp ≡ ±1(mod 8).Reversing the argument clearly shows that f(x) is solvable modulo pj , for all primes p andall positive integers j by lemmas 5.4 & 5.5. General solvability modulo m follows from theChinese Remainder Theorem. The proofs of the next two corollaries are similar to the proof of Corollary 5.6.Corollary 5.7. Let n be a squarefree integer with n 6= ±1. Thenf(x) = (x2 + 1)(x2 − n)(x2 + n)is solvable modulo m for every positive integer if and only if the prime factors of n havethe form 4k + 1 and n ≡ ±1(mod 8).Corollary 5.8. Let n be an odd squarefree integer with n 6= 1. Thenf(x) = (x2 + 2)(x2 − n)(x2 + 2n)is solvable modulo m for every positive integer if and only if the prime factors of n havethe form 8k + 1 or 8k + 3 and n ≡ 1(mod 8).315.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any IntegerWe finish by giving some examples of polynomials obtained from our corollaries.Table 5.2: Products of Quadratic Polynomials With Roots Modulo Any Integern Corollary Polynomial17 5.6 (x2 − 2)(x2 − 17)(x2 − 34)−7 5.6 (x2 − 2)(x2 + 7)(x2 + 14)17 5.7 (x2 + 1)(x2 − 17)(x2 + 17)−41 5.7 (x2 + 1)(x2 + 41)(x2 − 41)17 5.8 (x2 + 2)(x2 − 17)(x2 + 34)33 5.8 (x2 + 2)(x2 − 33)(x2 + 66)5.3 Polynomials (xq − n)Φq(x) Solvable Modulo Any Integer5.3.1 BackgroundIn section 5.1.1, we noted that the factor x2 + x+ 1 could be replaced by x2 + 3 in theintersective polynomial (x3 − n)(x2 + x+ 1). This factor is, however, the third cyclotomicpolynomial. This leads one to wonder whether a generalization of this polynomial wouldbe intersective. In fact, it is, given the right circumstances.Theorem 5.9. The polynomials (xq −n)(xq−1 + xq−2 + · · ·+ x+ 1) are intersective if andonly if the prime factors of n are kq + 1 and n ≡ 1 (mod q2) for an odd prime q.As previously, we require some background lemmas to support our proof.Lemma 5.10. If the prime factors of n have the form 1 +kq for k ∈ Z, and q prime, thenn ≡ 1 (mod q).Proof. Assume that the prime factors of n have the form 1 + kq for k ∈ Z and prime q.Thenn =t∏i=1(1 + kiq)for some integer t. If we expand the product we see that every term is a multiple of q withthe exception of the first term, which equals 1. Letting the above multiple be r, we haven = 1 + rq so n ≡ 1 (mod q).325.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any IntegerDefinition 5.11. Let q be an odd prime. The cyclotomic polynomial Φq(x) is defined tobeΦq(x) = xq−1 + xq−2 + · · ·+ x+ 1.Lemma 5.12. Let q be an odd prime. Then the congruenceΦq(x) ≡ 0 (mod q)is solvable. However the congruenceΦq(x) ≡ 0 (mod q2)is not solvable.Proof. The congruenceΦq(x) ≡ 0 (mod q)is solvable with x = 1. Suppose by way of contradiction that for some integer r, thecongruenceΦq(x) ≡ 0 (mod q2)is solvable with x = r. Then (weakening the congruence)Φq(r) ≡ 0 (mod q).Clearly(r − 1)Φq(r) ≡ 0 (mod q).The left hand side of this equation simplifies torq − 1 ≡ 0 (mod q)which simplifies to(r − 1)q ≡ 0 (mod q)by Lemma 1.30. This is equivalent toq | (r − 1)q335.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any Integerand since q is a prime we obtainq | (r − 1).Thus r = kq + 1 for some integer k. HenceΦq(kq + 1) ≡ 0 (mod q2),orq−1∑j=0(1 + kq)j ≡ 0 (mod q2).We see that1 + (1 + kq) +q−1∑j=2(1 + kq)j ≡ 0 (mod q2).Now by the binomial theorem, for j ≥ 2 we have(1 + kq)j ≡ 1 + kq(j1)(mod q2)or, by expansion and reduction modulo q2,(1 + kq)j ≡ 1 + kqj (mod q2),again by Lemma 1.30. The above sum becomes1 + (1 + kq) +q−1∑j=2(1 + kqj) ≡ 0 (mod q2).Simplifying givesq + kq(1 + 2 + · · ·+ q − 1) ≡ 0 (mod q2),orq + kq(q(q − 1)2)≡ 0 (mod q2)leading toq ≡ 0 (mod q2)345.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any Integerwhich is impossible. ThusΦq(x) ≡ 0 (mod q2)is insolvable.Lemma 5.13. Let p, q be odd primes. Then the congruenceΦq(x) ≡ 0 (mod pj)is solvable for all positive integers j if and only ifp ≡ 1 (mod q).Proof. Suppose thatΦq(x) ≡ 0 (mod pj)is solvable for all positive integers j. By the previous lemma, p 6= q. Suppose that r is aninteger withΦq(r) ≡ 0 (mod p).Since p 6= q we cannot haver ≡ 1 (mod q)(see proof of previous lemma). Next we deduce that(r − 1)Φq(r) ≡ 0 (mod p),so thatrq − 1 ≡ 0 (mod p),orrq ≡ 1 (mod p).We know that the order of r mod p is a divisor of q (a prime) (see Theorem 1.20) so thateitherordpr = 1 or ordpr = q.355.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any IntegerIf ordpr = 1 then r ≡ 1 (mod p) in which caseΦq(r) ≡ q ≡ 0 (mod p).This is impossible as q 6= p. Thusordpr = q.By Corollary 1.21ordpr | φ(p) = p− 1.Thusq | p− 1,givingp ≡ 1 (mod q)as required.Conversely, suppose thatp ≡ 1 (mod q).Let r be a primitive root modulo p. Define the integer x1 by x1 = rp−1q . By Fermat’s LittleTheoremxq1 = 1 (mod p).Furthermore, x1 6≡ 1 (mod p) as r is a primitive root and obviously x1 6≡ 0 (mod p). Sinceq is not divisible by p and x1 6≡ 0 (mod p) we can apply Hensel’s Lemma to deduce theexistence of a sequence of integers xj , j = 2, 3, . . . satisfyingxqj ≡ 1 (mod pj)andxj ≡ xi (mod p).Thus (xj − 1)Φq(xj) ≡ 0 (mod pj) for j = 2, 3, . . .. As xj 6≡ 1 (mod p), gcd(xj−1, p) = 1so that Φq(xj) ≡ 0 (mod pj) as required.365.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any Integer5.3.2 The Main ResultTheorem 5.14. The polynomials (xq − n)(xq−1 + xq−2 + · · · + x + 1) are intersective ifand only if the prime factors of n are of the form kq + 1 and n ≡ 1 (mod q2) for an oddprime q.We start with a Lemma to address the case q = 2.Lemma 5.15. The polynomial (x2 − n)(x+ 1) is not intersective.Proof. The factor x + 1 has a solution in Z, namely x = −1, so (x2 − n)(x + 1) is notintersective.We now present the proof of the main theorem.Proof. Assume that n ≡ 1 (mod q2) for an odd prime q and that the prime factors of nare kq + 1. We will show that f(x) = (xq − n)(xq−1 + xq−2 + · · · + x + 1) is intersective.Let f1(x) = xq − n and f2(x) = xq−1 + xq−2 + · · · + x + 1, and let n = mq2 + 1 for somem ∈ Z.We then wish to show that f1(x)f2(x) is intersective by showing that f1(x)f2(x) ≡ 0(mod pj) is solvable for each prime p and each positive integer j. The intersective propertythen follows from the Chinese Remainder Theorem.We begin with the prime q. If we set x = 1+mq then the binomial theorem and Lemma1.30 show thatf1(1 +mq) =q∑i=0(qi)(mq)i − n ≡ 1 +mq2 − n ≡ 0 (mod q3)Now we apply the refined version of Hensel’s Lemma with j = 3 and τ = 1 and deducethat f1(x) ≡ 0 (mod qj) is solvable for all integers j. Thus f1(x)f2(x) ≡ 0 (mod qj) issolvable for all integers j.Now suppose that p is a prime with p ≡ 1 (mod q). By Lemma 5.13 Φq(x) ≡ 0(mod pj) is solvable for all positive integers j so that f1(x)f2(x) is solvable for all positiveintegers j.Lastly, we consider the case where p is a prime with p 6= q and p 6≡ 1 (mod q). Weapply Lemma 5.2, setting a = n, noting that n contains factors of the form kq + 1 so that375.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any Integergcd(p− 1, q) = 1. We conclude that with t = qxq − n = xt − n ≡ 0 (mod p)is solvable since ap−1d ≡ np−1 ≡ 1 (mod p), by Fermat’s Little Theorem. Applying Hensel’sLemma again we can deduce that xq−n ≡ 0 (mod pj) is solvable for all positive integers j.Thus, by the Chinese Remainder Theorem we have shown that f1(x)f2(x) is intersective.Now we assume that f1(x)f2(x) is intersective. We must show that n has the formkq + 1 and n ≡ 1 (mod q2) for an odd prime q.We begin by showing that q - n. If q | n, then since n is qth power free, xq − n ≡ 0(mod qq) is insolvable. Furthermore, Φq(x) ≡ 0 (mod q2) is insolvable so f1(x)f2(x) couldnot be intersective. Thus q does not divide n.Now suppose that p | n and p 6≡ 1 (mod q). Since Φq(x) ≡ 0 (mod p) is insolvableby Lemma 5.13 and xq − n ≡ 0 (mod pq) is insolvable as n is qth power free, f1(x)f2(x)cannot be intersective. Thus p does not divide n.We can see that n is a product of primes of the form kq + 1. By Lemma 5.10 we maywrite n = tq+1 for some integer t. Since f1(x)f2(x) is intersective and Φq(x) 6≡ 0 (mod q2)for all integers x, xq − n ≡ 0 (mod qj) is solvable for all positive integers j.The solution to xq ≡ 1 (mod q) is x ≡ 1 (mod q). Let x0 be a solutions of xq ≡ 1(mod q3). Since x0 is also a solution of xq ≡ 1 (mod q), we see that x0 ≡ 1 (mod q) wherex0 = 1 + rq for some integer r. Substitution yieldsxq0 − n ≡ (1 + rq)q − n ≡ 0 (mod q3)so that1 + q2r − n ≡ 1 + q2r − (tq + 1) (mod q3)≡ 0 (mod q3)This clearly implies that q | t so that n ≡ 1 (mod q2) as required.385.3. Polynomials (xq − n)Φq(x) Solvable Modulo Any IntegerTable 5.3: The Smallest Intersective Polynomials (xq − n) Φq(x)q n Intersective Polynomial3 19(x3 − 10)Φ3(x)5 101(x5 − 101)Φ5(x)7 197(x7 − 197)Φ7(x)11 727(x11 − 727)Φ11(x)13 677(x13 − 677)Φ13(x)17 3469(x17 − 3479)Φ17(x)39Chapter 6Conclusions and Further Work6.1 ConclusionsIn this work we have described a new method for proving that a given polynomial isintersective and we have found three new families of intersective polynomials. By mul-tiplying together the subfields of splitting fields of polynomials we create out candidateintersective polynomials. These candidates each have at least two irreducible factors. Wedetermine which of these factors is solvable by examining different cases of prime numbersand applying Hensel’s Lemma and the refined version of Hensel’s Lemma. Once we haveseen that at least one of the factors is solvable for each of the cases of prime numbers, weuse the Chinese Remainder Theorem to combine the case and see that the polynomial issolvable for all integers greater than 1, and is therefore an intersective polynomial.As we have seen, intersective polynomials must be created by multiplying together thespecially chosen subfields of the splitting fields of polynomials. The difficulty lies in findingthe larger n-covers. The method that we have described here should work on intersectivepolynomials of larger degree, though we expect that they will require more specializedtheorems and lemmas to account for their size.The approach described in this work is useful because of its accessibility. As most ofthe proof of the theorem comes from undergraduate and early graduate level textbooks,many people will be able to access and understand the material. Perhaps this will lead tothe development of applications for these polynomials.6.2 Further Work6.2.1 A Specific ExampleThere is much still to study in the world of intersective polynomials. For example,polynomials of the form f(x) = (x6 − a)(x2 + b)(x6 + ab) present an interesting challenge.406.2. Further WorkWe have found one example. The polynomialf(x) = (x6 − 73)(x2 + 3)(x6 + 3 · 73)is intersective. We show this by treating five cases of primes, p = 2; p = 3; p ≡ 1(mod 3);p ≡ 2(mod 3) and(73p)= 1; p ≡ 2(mod 3) and(73p)= −1. We use notation for thepolynomial factors of f(x), namelyf1(x) = x6 − 73,f2(x) = x2 + 3,f3(x) = x6 + 3 · 73.Case 1: Suppose that p = 2. The congruencef1(x) ≡ 0(mod 8)is solvable with x = 1. Since 2 ‖ f ′1(1) we may apply the refined version of Hensel’s Lemmawith j = 3 and τ = 1, to see thatf1(x) ≡ 0(mod 2j)is solvable for all positive integers j. Consequentlyf(x) ≡ 0(mod 2j)is solvable for all positive integers j.Case 2: Suppose that p = 3.The congruencef1(x) ≡ 0(mod 27)is solvable with x = 4. Since 2 ‖ f ′1(4) we may apply the refined version of Hensel’s Lemmawith j = 3 and τ = 1, to see thatf1(x) ≡ 0(mod 3j)is solvable for all positive integers j. Consequently416.2. Further Workf(x) ≡ 0(mod 3j)is solvable for all positive integers j.Case 3: Suppose that p ≡ 1(mod 3). The congruencef2(x) ≡ 0(mod p)is solvable for some x = x0 since(−3p)= 1. The solution x0 is clearly not a multiple of pas p 6= 3. Thusf ′2(x0) 6≡ 0(mod p).Hensel’s Lemma now implies thatf2(x) ≡ 0(mod pj)is solvable for all positive integers j, so thatf(x) ≡ 0(mod pj)is solvable for all positive integers j.Case 4: Suppose that p ≡ 2(mod 3) and(73p)= 1. Since p ≡ 2(mod 3), the congru-encey3 ≡ 73(mod p)is solvable for some integer y0. Clearly p - y0 as p 6= 73. We have the following equality ofLegendre symbols (yp)=(y3p)=(73p)= 1.Hence there exists an integer x0 satisfyingx20 ≡ y(mod p),and again we clearly have p - x0. Thus x = x0 is a solution off1(x) ≡ 0(mod p).426.2. Further WorkSincef′1(x0) = 6x50 6≡ 0(mod p)Hensel’s Lemma implies thatf1(x) ≡ 0(mod pj)is solvable for all positive integers j so thatf(x) ≡ 0(mod pj).is solvable for all positive integers j.Case 5: Suppose that p ≡ 2(mod 3) and(73p)= −1. Since p ≡ 2(mod 3), thecongruencey3 ≡ −3 · 73(mod p)is solvable for some integer y0. Clearly p - y0 as p 6= 73. We have the following equality ofLegendre symbols(yp)=(y3p)=(−3 · 73p)=(−3p)(73p)= (−1)(−1) = 1.Hence there exists an integer x0 satisfyingx20 ≡ y(mod p),and again we clearly have p - x0. Thus x = x0 is a solution off3(x) ≡ 0(mod p).Sincef ′3(x0) = 6x50 6≡ 0(mod p)Hensel’s Lemma implies thatf3(x) ≡ 0(mod pj)is solvable for all positive integers j so thatf(x) ≡ 0(mod pj).436.2. Further Workis solvable for all positive integers j. Since the polynomial f(x) has the property that thecongruencef(x) ≡ 0(mod pj).is solvable for all primes p and all positive integers j by the Chinese remainder theorem iffollows that f(x) is intersective.6.2.2 A GeneralizationWe can generalize the previous example into a theorem.Theorem 6.1. Let c be an integer such that every prime factor of c has the form 3k + 1and c ≡ 1(mod 72). Then the polynomialf(x) = (x6 − c)(x2 + 3)(x2 + 3c)is intersective.Proof. For convenience we setf1(x) = x6 − cf2(x) = x2 + 3f3(x) = x2 + 3cWe treat the solvability of f(x) modulo pj for the classes of primesp = 2,p = 3,p ≡ 1(mod 3),p ≡ 2(mod 3) and(cp)= 1,p ≡ 2(mod 3) and(cp)= −1Case 1: Suppose that p = 2. Since c ≡ 1(mod 8), the congruencef1(x) ≡ 0(mod 8)446.2. Further Workis solvable with x = 1. Since 2 ‖ f ′1(1) we may apply the refined version of Hensel’s Lemmawith j = 3 and τ = 1, to see thatf1(x) ≡ 0(mod 2j)is solvable for all positive integers j. Consequentlyf(x) ≡ 0(mod 2j)is solvable for all positive integers j.Case 2: Suppose that p = 3. Since c ≡ 1(mod 9), the congruencef1(x) ≡ 0(mod 27)is solvable with x = 4. Since 2 ‖ f ′1(4) we may apply the refined version of Hensel’s Lemmawith j = 3 and τ = 1, to see thatf1(x) ≡ 0(mod 3j)is solvable for all positive integers j. Consequentlyf(x) ≡ 0(mod 3j)is solvable for all positive integers j.Case 3: Suppose that p ≡ 1(mod 3). The congruencef2(x) ≡ 0(mod p)is solvable for some x = x0 since(−3p)= 1. The solution x0 is clearly not a multiple of pas p 6= 3. Thusf ′2(x0) 6≡ 0(mod p).Hensel’s Lemma now implies thatf2(x) ≡ 0(mod pj)456.2. Further Workis solvable for all positive integers j, so thatf(x) ≡ 0(mod pj)is solvable for all positive integers j.Case 4: Suppose that p ≡ 2(mod 3) and(cp)= 1. Since p ≡ 2(mod 3), the congruencey3 ≡ c(mod p)is solvable for some integer y0. Clearly p - y0 as p - c. We have the following equality ofLegendre symbols (yp)=(y3p)=(cp)= 1.Hence there exists an integer x0 satisfyingx20 ≡ y(mod p),and again we clearly have p - x0. Thus x = x0 is a solution off1(x) ≡ 0(mod p).Sincef′1(x0) = 6x50 6≡ 0(mod p)Hensel’s Lemma implies thatf1(x) ≡ 0(mod pj)is solvable for all positive integers j so thatf(x) ≡ 0(mod pj).is solvable for all positive integers j.Case 5: Suppose that p ≡ 2(mod 3) and(cp)= −1. Since p ≡ 2(mod 3), thecongruencey3 ≡ −3c(mod p)466.2. Further Workis solvable for some integer y0. Clearly p - y0 as p 6= 73. We have the following equality ofLegendre symbols(yp)=(y3p)=(−3cp)=(−3p)(cp)= (−1)(−1) = 1.Hence there exists an integer x0 satisfyingx20 ≡ y(mod p),and again we clearly have p - x0. Thus x = x0 is a solution off3(x) ≡ 0(mod p).Sincef ′3(x0) = 6x50 6≡ 0(mod p)Hensel’s Lemma implies thatf3(x) ≡ 0(mod pj)is solvable for all positive integers j so thatf(x) ≡ 0(mod pj).is solvable for all positive integers j. Since the polynomial f(x) has the property that thecongruencef(x) ≡ 0(mod pj).is solvable for all primes p and all positive integers j by the Chinese remainder theorem iffollows that f(x) is intersective.6.2.3 An Intersective Polynomial With Galois Group C3 × C3Example 6.2. Letf(x) = g1(x)g2(x)g3(x)g4(x)withg1(x) = x3 + 7x2 − 10x+ 1,476.2. Further Workg2(x) = x3 + 8x2 − 11x+ 1,g3(x) = x3 + 86x2 − 89x+ 1,g4(x) = x3 + 47x2 − 1818x+ 5832.Then f(x) intersective. Each factor has Galois group C3 the cyclic group of order 3 and thesplitting field of f(x) has Galois group C3×C3. Note that by the theory of decompositiongroups it suffices to check solvability for the ramified primes [? ]. The discriminant is796 · 976 so we check 79 and 97. A complete treatment of products of 4 cyclic cubicsgiving necessary and sufficient conditions for intersectivity would be a challenging researchproblem.Clearly, there are many intersective polynomials out there to be found and many di-rections in which this work can be taken.48
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Intersective polynomials and Hensel's Lemma
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Intersective polynomials and Hensel's Lemma Hyde, Andrea 2014
pdf
Page Metadata
Item Metadata
Title | Intersective polynomials and Hensel's Lemma |
Creator |
Hyde, Andrea |
Publisher | University of British Columbia |
Date Issued | 2014 |
Description | An intersective polynomial is a polynomial with integer coefficients that has no rational roots, but has a root modulo every integer greater than 1. These polynomials have been difficult to find using traditional methods. In this thesis, we employ elementary methods, namely Hensel’s Lemma and the Chinese remainder theorem, to allow us to create three new infinite families of intersective polynomials. In order to create a candidate intersective polynomial, we employ methods from Galois theory. We multiply together carefully chosen polynomials that define subfields of a splitting field to create our candidate. We chose the subfields by first finding the n-cover, a collection of n proper subgroups, of the Galois group and identifying the corresponding subfields. We multiply the minimal polynomials of the subfields of the chosen splitting fields together to create the candidate intersective polynomial. From our method of creating candidates we can see that intersective polynomials have at least two irreducible factors. In order to prove that these polynomials have a root modulo every integer greater than 1, we examine each factor modulo certain prime numbers and determine which sets of primes admit solutions for each factor. We then use Hensel’s Lemma to lift those solutions to infinitely high powers of the particular primes. Finally, we combine the solutions modulo prime powers by using the Chinese remainder theorem to show that the polynomial has solutions modulo every integer greater than 1. Through the method outlined above, we have created three infinite families of intersective polynomials: (x³ − n)(x² + 3) when the prime factors of n are of the form 3k + 1 and n is congruent to 1 mod 9; (x² − a)(x² − b)(x² − a₁b₁) when at least one of a, b, a₁b₁ is congruent to 1 modulo 8 and one of the Legendre Symbols (a/p), (b/p), (a₁b₁/p) has the value +1; and (x^q −n)(x^(q-¹) +x^q-²+...+ x + 1) when the prime factors of n are kq + 1 and n is congruent to 1 modulo q² for an odd prime q. In the last chapter, we treat some special cases of intersective polynomials which will be considered in detail in future work. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2014-04-24 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivs 2.5 Canada |
DOI | 10.14288/1.0074336 |
URI | http://hdl.handle.net/2429/46574 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Irving K. Barber School of Arts and Sciences (Okanagan) Mathematics, Department of (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2014-05 |
Campus |
UBCO |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2014_spring_hyde_andrea.pdf [ 454.15kB ]
- Metadata
- JSON: 24-1.0074336.json
- JSON-LD: 24-1.0074336-ld.json
- RDF/XML (Pretty): 24-1.0074336-rdf.xml
- RDF/JSON: 24-1.0074336-rdf.json
- Turtle: 24-1.0074336-turtle.txt
- N-Triples: 24-1.0074336-rdf-ntriples.txt
- Original Record: 24-1.0074336-source.json
- Full Text
- 24-1.0074336-fulltext.txt
- Citation
- 24-1.0074336.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0074336/manifest