Results 1 to 2 of 2

Math Help - Proof of a lemma

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Proof of a lemma

    Lemma: Let a and n be integers with hcf(a,n)=1. Then

    n divides ab if and only if n divides b.
    I'm still not that brilliant at proving things and i'm having trouble with this lemma.

    I started with hcf(a,n)=1 \Rightarrow \ \exists u,v \in \mathbb{Z} \ s.t \ au+nv=1.

    Suppose n divides ab \Rightarrow \ n=kab \Rightarrow \ a=\frac{n}{kb}

    Combining both expressions gives: \frac{nu}{kb}+nv=1 \Rightarrow n \left( \frac{u}{kb}+v \right)=1 \Rightarrow \ n=\frac{kb}{u+vkb}.

    This is an integer multiple of b so n must divide b.

    Is this right?

    I'm also having trouble with the converse of the statement as well. I'll post any progress I make.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,792
    Thanks
    1532
    Quote Originally Posted by Showcase_22 View Post
    I'm still not that brilliant at proving things and i'm having trouble with this lemma.

    I started with hcf(a,n)=1 \Rightarrow \ \exists u,v \in \mathbb{Z} \ s.t \ au+nv=1.

    Suppose n divides ab \Rightarrow \ n=kab \Rightarrow \ a=\frac{n}{kb}

    Combining both expressions gives: \frac{nu}{kb}+nv=1 \Rightarrow n \left( \frac{u}{kb}+v \right)=1 \Rightarrow \ n=\frac{kb}{u+vkb}.

    This is an integer multiple of b so n must divide b.
    What? n is an integer multiple of b so n must divide b? 6 is an integer multiple of 3 but 6 does not divide three! You want to show that b is an integer multiple of n. In any case, n= \frac{kb}{u+ vkb} alone does NOT show that "this is an integer multiple of b". Some factors of u+ vkb may cancel factors of b.

    Is this right?

    I'm also having trouble with the converse of the statement as well. I'll post any progress I make.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid's Lemma Proof by Induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 7th 2011, 01:25 AM
  2. Proof of Pratt's Lemma
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 16th 2010, 12:04 PM
  3. Lemma proof help?
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 20th 2010, 03:08 PM
  4. Pumping Lemma proof...
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 15th 2010, 07:50 AM
  5. Proof of Lemma on Polynomials
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 30th 2009, 11:02 AM

Search Tags


/mathhelpforum @mathhelpforum