Results 1 to 5 of 5

Math Help - gcd(a,b) = 1 iff no primes divide a and b

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    gcd(a,b) = 1 iff no primes divide a and b

    (i) if the gcd(a,b) = 1, then p\nmid a \ \ \text{and} \ \ p\nmid b

    1|a \ \ \text{and} \ \ 1|b

    p|(pa) \ \ \text{and} \ \ p|(pb)

    \Rightarrow p|a \ \ \text{or} \ \ p|p \ \ \text{and} \ \ p|b \ \ \text{or} \ \ p|p

    Since p|p,  p\nmid a \ \ \text{and} \ \ p\nmid b

    (ii) if p\nmid a \ \ \text{and} \ \ p\nmid b, then the gcd(a,b) = 1

    p\nmid a, \ \ p\nmid b, \ \ \text{and} \ \ p|p

    p|(pa) \ \ \text{and} \ \ p|(pb)

    \Rightarrow 1|a \ \ \text{and} \ \ 1|b

    \Rightarrow 1=ar+bs \ \ r,s\in\mathbb{Z}

    \Rightarrow \text{gcd}(a,b)=1

    Correct?
    Last edited by dwsmith; June 11th 2011 at 08:19 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by dwsmith View Post
    (i) if the gcd(a,b) = 1, then p\nmid a \ \ \text{and} \ \ p\nmid b

    1|a \ \ \text{and} \ \ 1|b

    p|(pa) \ \ \text{and} \ \ p|(pb)

    \Rightarrow p|a \ \ \text{or} \ \ p|p \ \ \text{and} \ \ p|b \ \ \text{or} \ \ p|p

    Since p|p,  p\nmid a \ \ \text{and} \ \ p\nmid b
    Try including some words explaining what you are trying to achive (preferably at each step).

    Here you are trying to prove that if \gcd (a,b)=1 then there is no prime p that divides both a and b. The neatest way to do this is by contradiction, suppose that \gcd (a,b)=1 and that there exists prime p such that p|a and p|b and derive a contradiction.

    (ii) if p\nmid a \ \ \text{and} \ \ p\nmid b, then the gcd(a,b) = 1

    p\nmid a, \ \ p\nmid b, \ \ \text{and} \ \ p|p

    p|(pa) \ \ \text{and} \ \ p|(pb)

    \Rightarrow 1|a \ \ \text{and} \ \ 1|b

    \Rightarrow 1=ar+bs \ \ r,s\in\mathbb{Z}

    \Rightarrow \text{gcd}(a,b)=1

    Correct?
    Now you are trying to show that if for all primes p that p \nmid a and p\nmid b then \gcd(a,b)=1.

    Once again consider proof by contradiction ..

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    For the first part then, I would have:

    \text{Since} \  \exists p \ \text{such that} \ p|a \ \text{and} \ p|b, \ p|1

    However, since 1 isn't prime, a prime number can't divide 1.

    Thus, we have reached a contraction, and if the gcd(a,b) = 1, then no prime number divides both a and b.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by dwsmith View Post
    For the first part then, I would have:

    \text{Since} \  \exists p \ \text{such that} \ p|a \ \text{and} \ p|b, \ p|1

    However, since 1 isn't prime, a prime number can't divide 1.

    Thus, we have reached a contraction, and if the gcd(a,b) = 1, then no prime number divides both a and b.
    No;

    Suppose a,b \in \mathbb{R} such that \gcd(a,b)=1 and that there exists prime p such that p | a and p | b.

    As p | a and p | b p is a common divisor of a and b, so \gcd(a,b)\ge p >1 a contradiction.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    May 2011
    Posts
    54
    1) gcd(a,b)=1. Since all prime numbers > 1, no p exists that divides both a and b. No need to resort to contradiction imo

    2) let no p divide both a and b and let gcd(a,b)=m. p divides m iff it divides both a and b. Since no p divides both a and b, then no p divides m. The only number that cannot be written as a product of primes is 1 so m =1

    Q.E.D
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] How to divide GCF through...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 1st 2011, 04:15 PM
  2. Divide
    Posted in the Algebra Forum
    Replies: 1
    Last Post: June 2nd 2010, 02:52 PM
  3. Determine which primes > 3 divide...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 13th 2010, 03:38 PM
  4. Replies: 1
    Last Post: November 29th 2007, 05:17 AM
  5. Let P be the set of primes that divide 200!.
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 28th 2006, 07:20 PM

/mathhelpforum @mathhelpforum