# Thread: Polynomial conguence proof by GE Andrews

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 ?

2. I think you can resolve this problem by making the construction a bit more explicit. Suppose that $\displaystyle 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 $\displaystyle x=w_i\ (1\leqslant i\leqslant k+1)$ (mod p). Then we form the polynomial $\displaystyle g(x) = f(x) - \textstyle a_0\prod_{i=1}^k(x-w_i)$, which has leading term $\displaystyle \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 $\displaystyle \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 $\displaystyle w_i$s with $\displaystyle 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.

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

4. 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 $\displaystyle \textstyle\prod_{i=1}^k(x-w_i)$ only uses k of them. The remaining one, $\displaystyle w_{k+1}$, does not appear in the formula for g(x). So if the leading coefficient $\displaystyle \textstyle a_0 - a_1\sum_{i=1}^kw_i$ in g(x) happens to be zero, we can substitute $\displaystyle w_{k+1}$ for $\displaystyle w_k$ say, and that coefficient will then change to something nonzero. (It cannot still be zero, because that would imply that $\displaystyle a_0w_k = a_0w_{k+1}$. But $\displaystyle a_0$ is not equal to zero (mod p), so it has an inverse (mod p), and that implies that $\displaystyle 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!