Results 1 to 2 of 2

Math Help - Number Theory Proof

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    8

    Number Theory Proof

    Could anyone assist me with this problem...

    "Use mathematical induction to prove the following generalization.
    Suppose a_1, a_2, ..., a_n are integers and p is a prime number. If p|a_1 a_2 ... a_n, then p|a_i for some i = 1, 2, ..., n." [Hint: The induction step has two cases.]

    I believe I can use this theorem without proof:
    Suppose a and b are integers and p is a prime number. if p|ab, then p|a or p|b. This theorem comes from the uniqueness of prime factorization section.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Let P_n be the statement that if p \mid a_1 a_2 \cdots a_n, then p \mid a_i for some i \in [1, n].

    Base case: P_1 is a trivial statement. P_2 is the theorem you have.

    Inductive Step:
    Assume P_k to be true, that is, if p \mid {\color{red}a_1 a_2 \cdots a_k} then p \mid a_i for some i \in [1, k]. It remains to show that P_{k+1} also holds, that is, if p \mid a_1 a_2 \cdots a_k a_{k+1}, then p \mid a_j for some j \in [1, k+1].

    So if we have that p \mid ({\color{red}a_1a_2 \cdots a_k}){\color{blue}a_{k+1}}, by your theorem, we have 2 cases: (1) p \mid {\color{red}a_1a_2 \cdots a_k} or (2) p \mid {\color{blue}a_{k+1}}.

    (1) By the inductive hypothesis, we already have some j such that p \mid a_j, namely j = i.

    (2) Then let j = k+1 and we're done.
    Last edited by o_O; November 12th 2008 at 07:18 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] number theory: proof required!
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 1st 2011, 02:42 PM
  2. number theory proof
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: September 13th 2008, 05:17 PM
  3. number theory proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 1st 2008, 11:04 AM
  4. Number Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2008, 03:52 PM
  5. Number theory proof
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 12th 2006, 09:31 AM

Search Tags


/mathhelpforum @mathhelpforum