Results 1 to 2 of 2

Math Help - gcd integer proof

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    182
    Thanks
    1

    gcd integer proof

    Hi all,

    Let a and b > 0 be integers. Show that there exist integers u and v such that u+v = a and gcd(u, v) = b, if and only if b|a.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by sirellwood View Post
    Hi all,

    Let a and b > 0 be integers. Show that there exist integers u and v such that u+v = a and gcd(u, v) = b, if and only if b|a.
    Problem: if a\ \in\ \mathbb{Z},\ b\ \in\mathbb{N}, show that

    u,\ v\ \exists\ \in\ \mathbb{Z},\ u+v = a,\ gcd(u, v) = b\ \Leftrightarrow\ b|a

    Solutin: First suppose that b|a and show the left direction:

    Set u = b and v = a - b. Since a and b are natural numbers, u and v are both integers. Since b divides a, b also divides a-b, hence it divides both u and v, so gcd(u, v) > b. But gcd(u, v) cannot be > u, so gcd(u, v) < u = b. So b < gcd(u, v) < b, which means that gcd(u, v) = b. Also, u + v = b + a - b = a. So, if b|a, it does exist such u and v.

    Now show the right direction:

    gcd(u, v) = b, so b divides both u and v, hence also u + v, so it must divide a as well. So, if such u and v exist, b divides a.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Positive integer proof
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 2nd 2010, 09:15 PM
  2. Integer Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 2nd 2010, 01:53 AM
  3. Integer proof
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 1st 2010, 02:00 PM
  4. Integer Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 1st 2009, 11:09 AM
  5. Integer Proof
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 23rd 2008, 12:36 PM

Search Tags


/mathhelpforum @mathhelpforum