Results 1 to 2 of 2

Math Help - Proof using induction

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    22

    Proof using induction

    Prove that if f(x) \equiv 0(mod p) has j solutions x \equiv a_{1}, x \equiv a_{2},..., <br />
x \equiv a_{j} (mod p), there is a polynomial q(x) such that f(x) \equiv (x - a_{1}) <br />
(x - a_{2}) ... (x - a_{j})q(x)(mod p).

    I feel that I need to somehow show that there is a polynomial q_{1}(x) such that f(x) \equiv (x-a_{1})q_{1}(x)(mod p) and that q_{1}(x) \equiv 0 (mod p) has solutions x=a_{2}, x=a_{3}, ..., x=a_{j} (mod p) , but I don't know start from there and finish the proof using induction.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    We proceed by induction on the degree of f. If f has degree 1, there is nothing to show because it is already in the form x-a. So suppose it holds for all polynomials having degree \leq n-1. Let f(x)=c_0+c_1x+...+c_nx^n be of degree n, and suppose x \equiv a \mod p is a solution. Then 0\equiv f(a) \equiv c_0+c_1a+...+c_na^n. So we have

    f(x)\equiv f(x)-f(a) \equiv c_1(x-a)+...+c_n(x^n-a^n)

    \equiv (x-a)(c_1+c_2(x+a)+...+c_n(x^{n-1}+x^{n-2}a+...+xa^{n-2}+a^{n-1}))

    \equiv (x-a)g(x)

    where g(x) is of degree \leq n-1. Now use the fact that p is prime to show that any other roots of f(x) must in fact be roots of g(x), and apply the induction hypothesis to obtain the desired factorization for f(x).

    Hope that helps!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. induction proof
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: March 5th 2010, 10:04 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  3. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 29th 2008, 08:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. Proof By Induction help!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: April 29th 2008, 10:49 AM

Search Tags


/mathhelpforum @mathhelpforum