Math 788F: The Theory of Irreducible Polynomials
Students in Math 788F may obtain further electronic help by
contacting me by email at filaseta@math.sc.edu .
Problem (1.1): Be careful with your write-up. The contrapositive of "if f(x+a) is irreducible, then f(x) is irreducible" is NOT "if f(x) is reducible, then f(x+a) is reducible". Keep in mind that "reducible" is almost but not the same as "not irreducible".
Problem (1.7): Assume the result is not true and take a counterexample with deg g minimal. Divide f(x) by g(x) to get r(x). Show r(x) is identically 0 by showing that otherwise you can get a counterexample with smaller degree than g.
Problem (1.8): Use Calculus to show that f(x) and f'(x) have a common root. Use gcd(f(x),f'(x)) to get a non-constant polynomial of degree < deg f which divides f(x).
Problem (1.11)(a): There are h(x) and r(x) for which f(x) = g(x) h(x) + r(x) with r(x) identically 0 or deg r < deg g. Multiply through by a positive integer, say A, to deal with polynomials in Z[x]. Then the hypothesis in the problem implies that for infinitely many integers m, we have g(m)|(A*r(m)) so that |g(m)| <= A*|r(m)|. In other words, |r(m)/g(m)| >= 1/A for m with |m| arbitrarily large. Why does this imply r(x) is identically 0?
(b): I can even think of examples with g(x) a constant.
Problem (2.2)(i): If f(x) is Eisenstein with respect to p, then you may use, as we showed in class, that f(x) = a_n (x-c)^n (mod p) for some integer c. Justify that a_n is not zero modulo p and that c = a (mod p). We know f(x+b) is in Eisenstein form with respect to p for some integer b. Deduce (with an explanation) that p|f(b) and b = a (mod p). Follow an argument in the explanation of the algorithm in this chapter to prove f(x+a) is in Eisenstein form with respect to p. This justifies the "only if" part of the problem.
(ii): Use part (i).
(iii): Use that f(x) = a_n (x-a)^n (mod p) from part (i) to show f(x) = a_n (x-a)^n + p g(x) for some g(x) in Z[x]. You will probably want to use that if k is an integer, then so is k(k-1)...(k-m+1)/m! (this requires an explanation; think in terms of binomial coefficients).
Problem (2.4): Define h(x) and a by g(x) = h(x) + a where h(x) is in Z[x] with h(0) = 0. Let k be the minimal positive integer for which p does not divide the coefficient of x^k in h(x). Explain why such a k exists. Suppose f(x+a) = sum of b_j x^j (for j from 0 to n). Then f(g(x)) = sum of b_j h(x)^j. Explain why p divides b_0 and p^2 does not. Assuming p divides each of b_0, b_1, ..., b_(t-1), and not b_t, show that the coefficient of x^(kt) in f(g(x)) is not divisible by p (some work may be needed here). Explain why this does what you want.
Problem (2.7)(i)&(ii): If you translate f(x) appropriately, then the determinant defining R(f,f') will have many columns where each entry in the columns is divisible by p. You may want to use the formal definition of a determinant (see a linear algebra book) to establish the desired results.
Problem (2.9)(a)&(b): Use Newton polygons.
Problem (3.1): This is an easy consequence of a result in this chapter. Yes, you may use that there exist infinitely many primes.
Problem (3.2): Recall Problem (1.2) and use a result from Chapter 3.
Problem (3.6): Use Lemma 2 of Theorem 8 to determine the number of roots of f(x^2) outside the circle {z complex : |z| = 1}. Justify that f(x^2) has no real roots. Use that if alpha is any complex root of a polynomial w(x) with integer (or real) coefficients, then the conjugate of alpha is also a root of w(x).
Problem (3.12): In the case that deg f > 0, let z be a complex number such that |z - 10| <= 1. Either z is in the upper half of the complex plane or the lower half. Show that the imaginary part of f(z) is non-zero by considering the imaginary part of z^k for 0 <= k <= 31. (Looking at the proof of Theorem 15 may help.)
Problem (3.13): If f(x) = g(x)h(x), what can you say about the constant terms of g(x) and h(x)? What does this imply about one of g(10) and h(10)? If you got these answers right, the rest of the solution follows from what we did for the proofs of the lemma to Theorem 15 and Theorem 15 itself. (You might want to ask yourself, "How in the proof of the lemma did we use that |f(10)| is a prime or one?" And you may also want to ask, "Where in the proof of Theorem 15 didn't we use that f(10) is a prime?")
Problem (3.17): One way is to use Theorem 9 (it may help to take the a_j large). Apply the Intermediate Value Theorem (from Calculus).
Problem (3.21): Let A denote the maximum value of |s| where s is in S. I get N = (4A)^2 easily, but better is possible (i.e., smaller N is possible). If there is only one s in S such that f(m) = s holds for some integer m, then you should see what to do. Now, suppose there are two such s. Let s_1 be one of them and fix a_1 so that f(a_1) = s_1. Then f(x) = (x-a_1) g(x) + s_1 for some g(x) with integer coefficients. Suppose a_2 is such that f(a_2) is in S - {s_1}. Using an argument similar to that used in the proof of the lemma to Theorem 13, show that there are at most 4A different possibilities for a_2. Why must there also be at most 4A different possibilities for a_1? If you get much less than 4A different possibilities for a_1, that's fine (but the bound 4A should be easier to get). Why does N = (4A)^2 do what's needed?
Problem (3.23): Try the proof given for Theorem 8 here. Either f(x) has a root alpha such that |alpha| = 1 or it doesn't. In the latter case, one of the inequalities displayed in the proof of Theorem 8 can certainly be made a strict inequality. In the former case, take z_1 = a_0 in the hint already given in the problem and look at when equality holds in the first inequality displayed in the proof of Theorem 8. Be careful here; do not assume that a_1 is non-zero. Somehow make use instead of the fact that the coefficients of both z^n and z^(n-1) are non-zero.
Problem (4.1) (a): We used that ap-1 = 1 (mod p) if p does not divide a, and this is all I really want you to use in way of background material (besides theorems from class). Show that non-zero squares are roots of x(p-1)/2-1 modulo p, that there are (p-1)/2 of them, and argue that the remaining non-zero numbers modulo p must be roots of x(p-1)/2+1.
(b): Use part (a).
(c): If -1 is a square modulo p, then you should be able to figure out how x4+1 factors. If 2 is a square modulo p, then consider (x2-ax+1)(x2+ax+1) modulo p where a2 = 2 modulo p. If -2 is a square modulo p, then do something similar.
Problem (4.4): Use that f(x) = a g(x) (mod p) implies f(x) - a g(x) = p w(x) for some polynomial w(x) in Z[x]. Also, note that there is a b such that ab = 1 (mod p) so that b f(x) = g(x) (mod p).
Problem (4.7): Use the first part of the hint for (4.4) with a = 1.
Problem (6.1): If f(x) is monic and reducible in Z[x], then f(x) = g(x)h(x) where each of g(x) and h(x) are monic polynomials in Z[x] having degree at least 1. The main point is that they are monic.
Problem (6.6): Consider the polynomials irreducible modulo p where you should pick an explicit prime p.
Problem (6.7): If thinking of a likely factor of P_n(x) is hard, try thinking of a likely root.
Problem (7.5): Use that for f(x) in Z[x] and for p a prime, one has f(x^p) = f(x)^p mod p. Apply this fact more than once.
Problem (7.11) (a): Suppose p_j is the probability of the first die coming face up on j and that q_j is the probability of the second die coming face up on j. What information is given by the coefficients when one expands the product (p_1 + p_2 x + ... + p_6 x^5) * (q_1 + q_2 x + ... + q_6 x^5)?
(b): What do you know about the roots of polynomials having odd degree and real coefficients?
Problem (7.13): Use a previous homework problem.
Problem (7.14): Calculate phi(200). If p is not 2 or 5, use that p^f = 1 (mod 200) if and only if p^f = 1 (mod 8) and p^f = 1 (mod 25). You want to show that the f in Theorem 31 must be <= 20. You should be able to show in fact that p^(20) = 1 (mod 200) for every prime p not 2 or 5 (but this does not mean f = 20 for every such prime).