Results 1 to 2 of 2

Thread: Proof using induction

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    22

    Proof using induction

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

    I feel that I need to somehow show that there is a polynomial $\displaystyle q_{1}(x)$ such that $\displaystyle f(x) \equiv (x-a_{1})q_{1}(x)(mod p) $and that $\displaystyle q_{1}(x) \equiv 0 (mod p) $has solutions $\displaystyle 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 $\displaystyle f$. If $\displaystyle f$ has degree 1, there is nothing to show because it is already in the form $\displaystyle x-a$. So suppose it holds for all polynomials having degree $\displaystyle \leq n-1$. Let $\displaystyle f(x)=c_0+c_1x+...+c_nx^n$ be of degree $\displaystyle n$, and suppose $\displaystyle x \equiv a \mod p$ is a solution. Then $\displaystyle 0\equiv f(a) \equiv c_0+c_1a+...+c_na^n$. So we have

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

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

    $\displaystyle \equiv (x-a)g(x)$

    where $\displaystyle g(x)$ is of degree $\displaystyle \leq n-1$. Now use the fact that $\displaystyle p$ is prime to show that any other roots of $\displaystyle f(x)$ must in fact be roots of $\displaystyle g(x)$, and apply the induction hypothesis to obtain the desired factorization for $\displaystyle 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: Mar 5th 2010, 09:04 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 09:33 PM
  3. Induction Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Dec 29th 2008, 07:33 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. Proof By Induction help!
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Apr 29th 2008, 09:49 AM

Search Tags


/mathhelpforum @mathhelpforum