Results 1 to 6 of 6

Math Help - relatively prime

  1. #1
    Newbie
    Joined
    Apr 2007
    Posts
    10

    relatively prime

    By counting an appropriate geometric arrangement of points, prove that (PLEASE SEE IMAGE) if p and q are relatively prime.
    Attached Thumbnails Attached Thumbnails relatively prime-.bmp  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Follow the Gauss' 4th proof of Quadric Reciprocity.
    (Eisenstein Version).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2007
    Posts
    10
    im sorry but i dont understand how to use the recipocrity proof to answer this question. please help.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,861
    Thanks
    742
    Hello, demon1!

    The statement is not true . . .

    . . . . . . . . . . . . .
    q-1
    We have: .2(p/q)
    i . = . 2(p/q)q(q-1)/2 . = . p(q - 1)
    . . . . . . . . . . . . .
    i=1

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Soroban View Post
    Hello, demon1!

    The statement is not true . . .

    . . . . . . . . . . . . .
    q-1
    We have: .2(p/q)
    i . = . 2(p/q)q(q-1)/2 . = . p(q - 1)
    . . . . . . . . . . . . .
    i=1

    The meaning of "[ ]" means greatest integer function.

    ----

    The idea (which needs some work) is two create the following rectangle: {(0,0),{0,q),{p/2,0},{p/2,q}.
    Now draw all the points (integer coefficintes) inside this rectange.
    There are (p-1)/2 * (q-1) points.

    Now we will count them in a different way.
    Draw the line y=p/q*x.
    It is easy to see no points lie on this line.
    Then find the number of points above and below this rectange. Which I think happen to be the same.

    The number of such points (below diagnol) is:
    SUM(i=1,q-1) [ p/q* i]

    If you double this you get ALL the points.
    And by a counting argument we find that:
    2*SUM(i=1,q-1)[p/q *i]] = (p-1)/2*(q-1)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,861
    Thanks
    742
    The meaning of "[ ]" is the greatest integer function.
    "Oh ... that's different . . . Never mind."

    . . . . Emily Litella, 1982

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 08:51 AM
  4. why is a prime squared + itself + 1 also a prime
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: November 19th 2010, 08:03 PM
  5. Replies: 6
    Last Post: August 28th 2010, 12:44 AM

Search Tags


/mathhelpforum @mathhelpforum