Results 1 to 5 of 5

Math Help - Divisibility (gcd) 6

  1. #1
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50

    Divisibility (gcd) 6

    Show that: ab\neq 0 and (a,b)=1 \Rightarrow (a^{2}+b^{2} , a+b)=?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    different numbers different answer...
    I don't know..
    Last edited by Sea; December 18th 2008 at 11:56 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    I believe: d = (a^2 + b^2, a + b) = 1 \text{ or } 2

    Don't have a proof of it at the moment. But here's a start:

    Note that: a^2 + b^2 = (a+b)^2 - 2ab

    Let d = ((a+b)^2 - 2ab, \ a + b).

    Since d\mid (a+b) and d \mid (a+b)^2 - 2ab, then  d \mid 2ab
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Sea View Post
    Show that: ab\neq 0 and (a,b)=1 \Rightarrow (a^{2}+b^{2} , a+b)=?
    Let (a^{2}+b^{2} , a+b) = d

    Case 1: d|a or d|b

    If d|a then d|b (Why?)

    Forcing d = 1(Why?)

    Case 2: d neither divides a nor b

    Observe that (a,b) = 1 = (a,a-b) = (b,b-a)

    d| (a^2 + b^2) - a(a+b) = b(b-a)

    By case hypothesis, d|b-a which means d|2b. And similarly d|2a.

    Now only the following conditions can be true(since (a,b) = 1)

    (2,b) = 1 \Rightarrow d|2 \Rightarrow d = 1,2
    (2,a) = 1 \Rightarrow d|2 \Rightarrow d = 1,2

    Thus we have showed that d can only be 1 or 2.

    Now to show that there are numbers that achieve both gcd:

    Choose a=1,b=2, (a,b)=1, (a^{2}+b^{2} , a+b) = 1
    and
    Choose a=5,b=3, (a,b)=1, (a^{2}+b^{2} , a+b) = 2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Sea
    Sea is offline
    Junior Member Sea's Avatar
    Joined
    Dec 2008
    From
    Turkey
    Posts
    50
    Quote Originally Posted by Isomorphism View Post
    Case 1: d|a or d|b

    If d|a then d|b (Why?)

    Forcing d = 1(Why?)



     d|a and d|a+b \Rightarrow d|a and d|b \Rightarrow d|(a,b) \Rightarrow d|1 \Rightarrow d=1<br />
    d|b and  d|a+b \Rightarrow d|b and d|a \Rightarrow d|(b,a) \Rightarrow d|1 \Rightarrow d=1



    I can understand.Thanks a million......
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum