Results 1 to 3 of 3

Math Help - Not the division algorithm (but fairly similar)

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    9

    Not the division algorithm (but fairly similar)

    Prove that for any positive integer n, there exist unique positive integers k and r such that n = \frac{k(k-1)}{2}+r with 1\le r\le k.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Sigyn3 View Post
    Prove that for any positive integer n, there exist unique positive integers k and r such that n = \frac{k(k-1)}{2}+r with 1\le r\le k.
    Consider the set \{ n - \tfrac{x(x-1)}{2}\geq 0 | x\in \mathbb{Z}^+ \}. There exists a smallest integer n - \tfrac{k(k-1)}{2} = r. We claim that r\leq k. Assume not, then r>k and we can write r=r_0+k where r_0<r. Thus, we have n - \tfrac{k(k-1)}{2} = r_0+k which gives n-\tfrac{(k+1)k}{2} = r_0. And this is a contradiction since r was supposed to be minimal.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    9
    Does this also prove uniqueness?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The Division Algorithm 2
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 5th 2011, 01:18 PM
  2. The Division Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 3rd 2011, 05:52 PM
  3. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 01:51 PM
  4. The Division Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2009, 01:45 PM
  5. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum