Re: Polynomials over Z.

On Jun 14, 11:03 am, Chip Eastham <hardm...@xxxxxxxxx> wrote:
On Jun 13, 3:53 pm, Saysero <says...@xxxxxxxxx> wrote:

Let P(n) and Q(n) be polynomials over Z such that deg(P)<=deg(Q) and
Q(n) is not divisible by P(n). How to find all such a in Z such that
Q(a) is divisible by P(a)?
Example: If Q(n)=n^2 and P(n)=n+2 then Q(n) is not divisible by P(n)
however we have P(2)|Q(2).
Thanks in advance.

P.S.
Problem that inspired my question: For what k does (n-1)^2 divide
(n^k-1)?
Solution I have: If (n-1)^2 divides (n^k-1) then (n-1) divides
(n^(k-1)+...+1). Since (n^(k-1)+...
+1)=(n^(k-1)-1+1+n^(k-2)-1+1...-1+1+1)=(n-1)X+k then (n-1) divides k
therefor if k is divisible by (n-1) then (n^k-1) is divisible by
(n-1).
Question: Is the solution correct? Does if an only if hold?

Note that the problem that inspired your question is of
an entirely different character that the question you'd
posed at the opening of the thread:  (n^k-1) is not a
polynomial in k.

One strategy is to try to reduce the main question, about
values of a for which P(a) divides Q(a), by lowering the
degree of Q to below that of P.  Then there will be a
finite interval outside of which |P(a)| > |Q(a)| (and
thus P(a) will not divide Q(a) outside that interval).

Such a strategy will succeed if P(X) is monic (nothing
in your description of the problem guarantees this),
which happened to be true in the example:

P(X) = X + 2, Q(X) = X^2

Rewrite Q(X) = (X - 2)P(X) + 4.  Then P(a) divides Q(a)
precisely when P(a) divides 4.  Clearly |P(a)| > 4 for
a not in {-6,-5,-4,-3,-2,-1,0,1,2}, so the question
reduces to checking P(a)|4 for the finitely many a
between -6 and 2.  The values that work are:

a = -6, -4, -1, 0, 2

Taking this argument to its logical conclusion, you can form
the resultant r of the polynomials P and Q. This number has
the property that there are integer-coefficient polynomials
f and g such that f P + g Q = r, so if P(a) divides Q(a)
then P(a) divides r, and that will really narrow down the
values of a you need to test.

An unsolved problem one gets by twisting things a little
is to find all primes p such that p^2 divides 2^p - 1.
--
GM
.

Relevant Pages

  • Re: JSH: Polynomial multiples
    ... divides Pin this case in the ring of polynomials, ... algebraic integers, just the integers), yet how it divides the factors x ...
    (sci.math)
  • Re: root of polynomial over galois field
    ... Here we've written "a" in the form of a squarefree factorization, ... Here we reach the Line 14, but now we see c = product, p divides ... not always exist for any element in a Galois field (that is true isnt ... of these polynomials could not be defined either as using the Euclidean ...
    (sci.math.symbolic)
  • Re: multiple.....
    ... ad is multiple of u. ... So any u in Z that divides rsmust divide rs. ... and if f,g are monic polynomials in Ksuch that fg is in Dthen ... Contents of polynomials and invertibility, ...
    (sci.math)
  • Re: Degree of a field extension
    ... in the polynomials c^n only the monomials ... Then it is necessarily a normal extension, ... generated by) of E and F, then s divides p and r divides q, or ... Herstein's Topics in Algebra around somewhere, and I will try to get ...
    (sci.math)