Results 1 to 3 of 3

Math Help - Please check argument for 2 questions about prime numbers.

  1. #1
    Junior Member
    Joined
    Apr 2009
    Posts
    54
    Thanks
    1

    Please check argument for 2 questions about prime numbers.

    1. Suppose a, b, and p are positive integers and p is prime.
    Prove that if p|ab, then either p|a or p|b.


    I think the easiest is to use proof by contradiction. Suppose it is not true that either p|a or p|b.
    Then this means p does not divide a AND p does not divide b.
    But if this is the case, then p must not divide ab as well.


    However, a more rigorous proof is go by using greatest common divisor. But I could not finish it.

    Let d be the greatest common divisor of a and p. Since p is a prime number, then d must be either 1 or p.
    If d = p, it follows by the definition of greatest common divisor that p|a. If d = 1,
    it follows that p does not divide a. By assumption p|ab.
    It should be reasonable to say that if p does not divide b, then p does not divide ab.
    But this seems I have returned to proof by contradiction.


    2. Suppose p_1, p_2, ..., p_j and q_1, q_2, ..., q_j
    are two nondecresing sequences of prime numbers, p_1 \leq p_2 \leq ... \leq p_j and
    q_1 \leq q_2 \leq q_k and  p_1p_2...p_j = q_1q_2...q_j
    Prove that j = k and p_i = q_i for 1 \leq i \leq j


    I went by induction on j and showing the base case that

     p_1 = q_1q_2...q_k which is not possible if k > 1 due to the fact that p is prime.

    As for the inductive step, I went by assuming p_1p_2...p_j = q_1q_2...q_k. j = k and p_i=q_i for for 1 \leq i \leq j So,

    p_1p_2...p_jp_{j+1} = (q_1q_2...q_k)  p_{j+1}

    If for another sequence q_1q_2q_3...q_k must be equal p_1p_2...p_jp_{j+1}, and the fact that p_{j+1} > p_j, there must be something more to q_1q_2...q_k, which is q_{k+1}. The inductive hypothesis, j = k and p_i=q_i for for 1 \leq i \leq j and the equality p_1p_2...p_j = q_1q_2...q_k. should ensure p_{j+1} = q_{k+1}.

    However, the right answer seems to be more rigorous but I think mine should be enough. What's wrong with my argument?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2008
    Posts
    182
    Suppose a, b, and p are positive integers and p is prime.
    Prove that if p|ab, then either p|a or p|b.


    <stolen from Laurent elsewhere on MHF>
    It results from Gauss Theorem: We assume that . If , we are done. Suppose . Then and are relatively prime.
    (If divides and , then or because is prime, hence necessarily since ; hence is the only positive common divisor of and )
    Because , you deduce from Gauss Theorem that . qed
    </stolen from Laurent elsewhere on MHF>
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Apr 2009
    Posts
    54
    Thanks
    1
    Quote Originally Posted by Unenlightened View Post
    Because , you deduce from Gauss Theorem that . qed
    Thanks, but I still do not get it. I think it is similar to my reasoning. What exactly does the Gauss Theorem said?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Complex Numbers - Argument of Z
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: February 9th 2011, 03:37 AM
  3. Complex Numbers (Principal Argument)
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 18th 2010, 03:41 AM
  4. A solved problem ..please check my argument.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: August 26th 2010, 12:50 PM
  5. Complex numbers: Argument of Z help
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: August 6th 2009, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum