Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By johng

Thread: Help with a proof - gcd

  1. #1
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    Help with a proof - gcd

    We define $\displaystyle a\mathbb{Z}+b\mathbb{Z}=\left \{ au+bv:u,v\in\mathbb{Z} \right \}$.

    I need to prove that $\displaystyle a\mathbb{Z}+b\mathbb{Z}=(a,b)\cdot\mathbb{Z}$.

    so, I need to prove $\displaystyle a\mathbb{Z}+b\mathbb{Z}\subseteq (a,b)\cdot\mathbb{Z}$ and $\displaystyle a\mathbb{Z}+b\mathbb{Z}\supseteq (a,b)\cdot\mathbb{Z}$.

    One direction is easy:

    ($\displaystyle \supseteq$) Let $\displaystyle n\in (a,b)\cdot\mathbb{Z}$, so $\displaystyle n=(a,b)\cdot k$, for some $\displaystyle k\in\mathbb{Z}$, and since there exist $\displaystyle s,t\in\mathbb{Z}$ such that $\displaystyle (a,b)=sa+tb$, we get:
    $\displaystyle n=(a,b)\cdot k$
    $\displaystyle n=(sa+tb)k$
    $\displaystyle n=ska+tkb$
    $\displaystyle n=(sk)a+(tk)b \Rightarrow n\in a\mathbb{Z}+b\mathbb{Z}$

    ($\displaystyle \subseteq$)
    I need help here...



    Thanks in advanced!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Help with a proof - gcd

    The ⊆ direction is easier: it does not even need Bézout's identity (a, b) = sa + tb.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    Re: Help with a proof - gcd

    Sorry, I couldn't think of anything.
    Can you give me another hint?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    1,141
    Thanks
    475

    Re: Help with a proof - gcd

    $\displaystyle a=(a,b)a_1$ and $\displaystyle b=(a,b)b_1$ with $\displaystyle a_1,b_1\in\mathbb{Z}$
    Thanks from Stormey
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [Abstract Algebra] Anyone care to proof-read a proof?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Dec 4th 2012, 01:13 PM
  2. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  3. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum