Results 1 to 5 of 5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Correct?
    Last edited by dwsmith; Jun 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
    5
    Quote Originally Posted by dwsmith View Post
    (i) if the gcd(a,b) = 1, then $\displaystyle p\nmid a \ \ \text{and} \ \ p\nmid b$

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

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

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

    Since p|p, $\displaystyle 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 $\displaystyle \gcd (a,b)=1$ then there is no prime $\displaystyle p$ that divides both $\displaystyle a$ and $\displaystyle b$. The neatest way to do this is by contradiction, suppose that $\displaystyle \gcd (a,b)=1$ and that there exists prime $\displaystyle p$ such that $\displaystyle p|a$ and $\displaystyle p|b$ and derive a contradiction.

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

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

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

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

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

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

    Correct?
    Now you are trying to show that if for all primes $\displaystyle p$ that $\displaystyle p \nmid a$ and $\displaystyle p\nmid b$ then $\displaystyle \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
    10
    For the first part then, I would have:

    $\displaystyle \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
    5
    Quote Originally Posted by dwsmith View Post
    For the first part then, I would have:

    $\displaystyle \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 $\displaystyle a,b \in \mathbb{R}$ such that $\displaystyle \gcd(a,b)=1$ and that there exists prime $\displaystyle p$ such that $\displaystyle p | a$ and $\displaystyle p | b$.

    As $\displaystyle p | a$ and $\displaystyle p | b$ $\displaystyle p$ is a common divisor of $\displaystyle a$ and $\displaystyle b$, so $\displaystyle \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: Apr 1st 2011, 04:15 PM
  2. Divide
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Jun 2nd 2010, 02:52 PM
  3. Determine which primes > 3 divide...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Apr 13th 2010, 03:38 PM
  4. Replies: 1
    Last Post: Nov 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: Sep 28th 2006, 07:20 PM

/mathhelpforum @mathhelpforum