Results 1 to 2 of 2

Math Help - [SOLVED] Greatest Common Divisor Problems

  1. #1
    Member
    Joined
    Mar 2008
    From
    Acolman, Mexico
    Posts
    118

    [SOLVED] Greatest Common Divisor Problems

    Hello, I guess these problems are not supposed to be very hard, but I am confused.

    1. Let a,b \in \mathbb{Z}. Prove that gcd(a,b)=1 if and only if there exists s,t \in \mathbb{Z} such that as+bt=1.

    2. Prove that if a,b,d \in \mathbb{Z} with d|ab and gcd(a,d)=1, then d|b.


    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    gcd(a,b)=1\Rightarrow\ \text{the ideal}\ <a,b>=\mathbb{Z} \Rightarrow \exists s,t\in\mathbb{Z},\ as+bt=1 \Rightarrow(\forall c\in\mathbb{Z},\ c|a\ \text{and}\ c|b \Rightarrow c|1)\Rightarrow gcd(a,b)=1


    Let p be a prime divisor of d. Since d|ab,\ p has to divise a or b (because p is irreducible).
    But gcd(d,a)=1\Rightarrow p doesn't divide a. Hence p|b, and that is true for any prime divisor of d.
    Therefore d|b. (Be more precise than me to show that \forall m\in\mathbb{N},\ p^m|d\Rightarrow p^m|b)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 05:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2010, 03:16 PM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  5. [SOLVED] Greatest Common Divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2009, 03:00 PM

Search Tags


/mathhelpforum @mathhelpforum