Polynomial conguence proof by GE Andrews

**Nivla** · August 25th 2009, 11:58 AM

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 ?

**Opalg** · August 26th 2009, 01:26 AM

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_i$ s 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.

**Nivla** · August 26th 2009, 11:48 AM

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.

**Opalg** · August 26th 2009, 12:15 PM

Originally Posted by Nivla

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.

Originally Posted by Nivla

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).)

Originally Posted by Nivla

Finally, I wonder how I can write mathematical symbols as nicely as you. How is it done? Thanks again for your reply.

LaTeX!

Thread: Polynomial conguence proof by GE Andrews

LinkBack

Thread Tools

Display

Polynomial conguence proof by GE Andrews

Similar Math Help Forum Discussions

Polynomial Proof

Polynomial proof

Conguence has :3168 solutions !!!! ????

polynomial mod. proof

Polynomial proof help.

Search Tags