Results 1 to 2 of 2

Thread: Euclid's lemma and induction

  1. #1
    Junior Member
    Joined
    Apr 2008
    From
    Gainesville
    Posts
    68

    Euclid's lemma and induction

    Use Euclid's Lemma and induction to prove that if p and
    q1,q2,q3,...,qn (1,2,3 and n are subscripts) are prime numbers
    and p divides q1q2q3...qn ( the product), then p=qi for some
    i=1,2,3....n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by JCIR View Post
    Use Euclid's Lemma and induction to prove that if p and
    q1,q2,q3,...,qn (1,2,3 and n are subscripts) are prime numbers
    and p divides q1q2q3...qn ( the product), then p=qi for some
    i=1,2,3....n.
    Euclid's lemma tells you that this is true for $\displaystyle n=2$.

    Now suppose it true for some $\displaystyle n=k$, then we have for any prime numbers:

    $\displaystyle p, q_1, .., q_{k+1}$

    Then by Euclids lemma if $\displaystyle p | q_1q_2...q_{k+1}$ then either $\displaystyle p|q_1q_2...q_{k}$ or $\displaystyle p|q_{k+1}$. But we already have by assumption that if $\displaystyle p|q_1q_2...q_{k}$ then $\displaystyle p$ divides one of $\displaystyle p_1, ...,p_k. $ Hence the result if true for $\displaystyle n=k$ is true for $\displaystyle n=k+1$, and with the base case we have a proof by induction for all integers $\displaystyle n \in \{2,..\}.$

    RonL
    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: Nov 8th 2011, 07:05 PM
  2. some confusion on wording of Euclid's Lemma
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 25th 2011, 05:08 PM
  3. Euclid's Lemma Proof by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 7th 2011, 01:25 AM
  4. Replies: 0
    Last Post: May 28th 2009, 09:07 AM
  5. Euclid,s division lemma-please help
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 7th 2007, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum