Results 1 to 4 of 4

Math Help - induction..prime number proof

  1. #1
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53

    induction..prime number proof

    confused:

    [im indicating a subscript by parenthesis... as in a sub 1 = a(1) not multiplying]

    By PMI, prove that this statement is true:
    "If p is a prime number and p | a(1)*a(2)...a(n), where a(i) is an integer for i=1,2,3...n then p | a(i) for some integer i.


    (im especially confused at what the make my proposition P(k) and where to substitute the k for PMI.)
    thank you so much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    Yes, formulating P(k) is the key in constructing a proof by induction.

    Here, in fact, you have a standard case. If your theorem can be formulated as, "For all integers n >= n0, P(n)", then usually you can take P(n) as the induction statement. Here the theorem is, "For all integers n >= 1, for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i". So, just strip the universal quantification over n and you get your P(n).

    The base case for n = 1 is obvious, and for the induction step you need to use Euclid's lemma.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member mremwo's Avatar
    Joined
    Oct 2010
    From
    Tampa, FL
    Posts
    53
    thats really helpful, thanks.


    but now im stuck after doing the base case.
    im not very good at induction, so some help on the induction step would be awesome, thanks


    Quote Originally Posted by emakarov View Post
    Yes, formulating P(k) is the key in constructing a proof by induction.

    Here, in fact, you have a standard case. If your theorem can be formulated as, "For all integers n >= n0, P(n)", then usually you can take P(n) as the induction statement. Here the theorem is, "For all integers n >= 1, for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i". So, just strip the universal quantification over n and you get your P(n).

    The base case for n = 1 is obvious, and for the induction step you need to use Euclid's lemma.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    The induction hypothesis: for all primes p and sequences of integers a(1), ..., a(n), if p | a(1) * ... * a(n), then p | a(i) for some i.

    Need to prove: for all primes p and sequences of integers a(1), ..., a(n), a(n+1), if p | a(1) * ... * a(n) * a(n+1), then p | a(i) for some i.

    Proof outline. Fix a prime p and n+1 integers a(1), ..., a(n+1). Assume that p | a(1) * ... * a(n) * a(n+1). Denote A = a(1) * ... * a(n), so p | A * a(n+1). Now apply Euclid's lemma. If p | a(n+1), we are done. If p | A, apply the induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 25th 2011, 01:52 AM
  2. Prime number Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 23rd 2009, 07:47 PM
  3. Proof of Prime number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 04:19 AM
  4. Prime Number Proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 16th 2009, 11:32 PM
  5. Prime Number Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 9th 2008, 12:22 PM

Search Tags


/mathhelpforum @mathhelpforum