Results 1 to 4 of 4

Math Help - Polynomial conguence proof by GE Andrews

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    12
    Awards
    1

    Polynomial conguence proof by GE Andrews

    I shall appreciate views on the proof by GE Andrews in his "Number Theory" (Dover 1971) for Theorem 5-5: A polynomial with int coeff of degree n, whose leading coefficient is not divisible by the prime p, has at most n solutions modulo p.

    First, I find Prof Andrew's book a fine introduction to the subject.

    The proof is an indirect one and proceeds by mathematical induction on the degree n. After demonstration the cases for n=0,1, Andrews considers the polynomial f(x) of degree k with leading coefficiant, a, not divisible by p. The induction hypothesis is applied to polynomials of degree less than k. He constructs the polynomial g(x) from f(x) by subracting from f(x) the product, a * Pi(x - w). The w are solutions of f(x) = 0 (modp), of which there are posited k+1, contrary to the theorem - since f(x) is of deg k. The {w} of the product are any k of the k + 1 solutions modulo p. The difference between f(x) and the product, g(x), is of degree less than k. However g(x) has k solutions modulo p, as one may see! Thus, for g(x) the induction hypothesis has a false conclusion and, consequently, the antecedent of the hypothesis must be false as a matter of logic.

    Herein lies my difficulty: the antecedent is a conjunction. Its denial can be had by the falsity of either conjunct. One conjunct is that its leading term is not divisible by p. That could be true or false. There is no specification of its divisibility. Only if it is not divisible by p are we forced to find that the other conjunct is false: that g(x)=0 (modp) for every x. Is the argument that since there is no specification as to the leading term of g(x) the conclusion must be that g(x) = 0 (modp) for every x ? That seems tenuous to me.

    Also, I am not sure what the falsity of that conjunct really must mean. One could say that g(x) is identically 0, in which case g(x) = 0 (modp) is satisfied by every x.

    Where am I missing the point, please ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    I think you can resolve this problem by making the construction a bit more explicit. Suppose that f(x) = a_0x^k + a_1x^{k-1} +\ldots\,(terms of lower degree). Suppose also that the equation f(x) = 0 (mod p) has solutions x=w_i\ (1\leqslant i\leqslant k+1) (mod p). Then we form the polynomial g(x) = f(x) - \textstyle a_0\prod_{i=1}^k(x-w_i), which has leading term \textstyle \Bigl(a_1 - a_0\sum_{i=1}^kw_i\Bigr)x^{k-1}.

    As I understand it, your difficulty with George Andrews's proof stems from the fact that the coefficient \textstyle a_1 - a_0\sum_{i=1}^kw_i of the leading term in the polynomial g(x) might be divisible by p, in which case the inductive proof fails to achieve its aim. That looks like a very valid objection to me. But one can easily get round it by exchanging one of the w_is with w_{k+1} so as to change the value of the product in that leading coefficient, which will then no longer be a multiple of p. That will remove the undesired element of the conjunction from the inductive hypothesis, so that the proof can be successfully completed.
    Last edited by Opalg; August 26th 2009 at 12:58 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    12
    Awards
    1
    Yes, thanks for the imaginative reply, which seems correct. I believe rather than the product symbol in the coefficient of the leading term of g(x) you mean a sum over the k chosen solutions. If that happens to equal the sum of the algebraic roots of f(x), then the next term would have to be examined, and so on. In fact, all the coefficients of descending powers of x would probably then vanish and g(x) would be identically 0(modp). In the case where the leading term did not vanish but was didvisible by p, substitution of the k+1 th solution - as you wrote - would remove the divisibility.

    In the latter case, g(x) is a polynomial would be false. What could it then do but have any integer for a solution? I ask the question, but I am not sure I am right. I don't really understand what the falsity of that important part of the antecedent means. Could you explain that a bit?

    Finally, I wonder how I can write mathematical symbols as nicely as you. How is it done? Thanks again for your reply.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Nivla View Post
    I believe rather than the product symbol in the coefficient of the leading term of g(x) you mean a sum over the k chosen solutions.
    Yes, of course I should have written sum rather than product. I have edited it to put that right.

    Quote Originally Posted by Nivla View Post
    If that happens to equal the sum of the algebraic roots of f(x), then the next term would have to be examined, and so on. In fact, all the coefficients of descending powers of x would probably then vanish and g(x) would be identically 0(modp). In the case where the leading term did not vanish but was divisible by p, substitution of the k+1 th solution - as you wrote - would remove the divisibility.
    No, that should not be necessary. The point is that there is a "spare" w. The product \textstyle\prod_{i=1}^k(x-w_i) only uses k of them. The remaining one, w_{k+1}, does not appear in the formula for g(x). So if the leading coefficient \textstyle a_0 - a_1\sum_{i=1}^kw_i in g(x) happens to be zero, we can substitute w_{k+1} for w_k say, and that coefficient will then change to something nonzero. (It cannot still be zero, because that would imply that a_0w_k = a_0w_{k+1}. But a_0 is not equal to zero (mod p), so it has an inverse (mod p), and that implies that w_k=w_{k+1}\!\!\!\pmod p, which is not true because the w's are supposed to be distinct roots of f(x) (mod p).)

    Quote Originally Posted by Nivla View Post
    Finally, I wonder how I can write mathematical symbols as nicely as you. How is it done? Thanks again for your reply.
    LaTeX!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Polynomial Proof
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: November 4th 2010, 03:38 AM
  2. Polynomial proof
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 13th 2010, 08:26 PM
  3. Conguence has :3168 solutions !!!! ????
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 29th 2009, 01:48 AM
  4. polynomial mod. proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 16th 2008, 03:22 PM
  5. Polynomial proof help.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 15th 2008, 05:36 AM

Search Tags


/mathhelpforum @mathhelpforum