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
    9
    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,719
    Thanks
    635
    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
    9
    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,719
    Thanks
    635
    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, 12:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  3. Replies: 3
    Last Post: February 17th 2011, 07: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, 07:03 PM
  5. Replies: 6
    Last Post: August 27th 2010, 11:44 PM

Search Tags


/mathhelpforum @mathhelpforum