Results 1 to 3 of 3

Math Help - Euclid's Lemma Proof by Induction

  1. #1
    Newbie
    Joined
    Feb 2011
    Posts
    1

    Euclid's Lemma Proof by Induction

    Hi,

    I was hoping you could help me prove Euclid's lemma using induction. I want to show by induction that if a prime p, divides a product of n numbers, then it divides at least one of the numbers.

    I've attempted this myself but what I attempted did not make sense to me. I tried taking the approach that if p|a1a2...an then looking at the case n=1 if p|a1 then we're done by hypothesis and that didn't seem right to me because I kept going in a loop. Help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by mrspotatohead View Post
    Hi,

    I was hoping you could help me prove Euclid's lemma using induction. I want to show by induction that if a prime p, divides a product of n numbers, then it divides at least one of the numbers.

    I've attempted this myself but what I attempted did not make sense to me. I tried taking the approach that if p|a1a2...an then looking at the case n=1 if p|a1 then we're done by hypothesis and that didn't seem right to me because I kept going in a loop. Help!
    P(1): \ p|a \ \text{true}

    P(k): \ p|(a_1a_2\cdots a_k)

    Assume true for a fixed but arbitrary value k such that n\leq k

    P(k+1): \ p|(a_1a_2\cdots a_ka_{k+1})

    By using P(k), prove P(k+1) is true.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774
    The main difficulty here is when n = 2. This is where one has to use the fact that p is prime. This has to be proved separately. After that proving it for arbitrary n by induction is pretty simple, as described above.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Applying Euclid's Lemma to a problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 8th 2011, 07:05 PM
  2. some confusion on wording of Euclid's Lemma
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 25th 2011, 05:08 PM
  3. Replies: 0
    Last Post: May 28th 2009, 09:07 AM
  4. Euclid's lemma and induction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 25th 2008, 11:44 PM
  5. Euclid,s division lemma-please help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 7th 2007, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum