Proving a floor sum.

Given that \(a,b\in\Bbb{Z}^+\) and \(\gcd(a,b)=1\).

Prove the following:

⌊ab⌋+⌊2⋅ab⌋+⌊3⋅ab⌋+…+⌊(b−1)⋅ab⌋=(a−1)(b−1)2\left\lfloor\frac{a}{b}\right\rfloor+\left\lfloor2\cdot\frac{a}{b}\right\rfloor+\left\lfloor3\cdot\frac{a}{b}\right\rfloor+\ldots+\left\lfloor(b-1)\cdot\frac{a}{b}\right\rfloor=\frac{(a-1)(b-1)}{2}

Clarifications:

  • ⌊⋅⌋\lfloor\cdot\rfloor denotes the floor function (greatest integer function).
  • gcd⁡(x,y)\gcd(x,y) denotes the greatest common divisor of xx and yy.

Hint:

It'd be helpful to prove this first before attempting to prove the main problem.

∀ a,b∈Z+∣gcd⁡(a,b)=1  ⟹  nab∉Z  ∀  0<n<b ∧ n∈Z\forall~a,b\in\Bbb{Z}^+\mid\gcd(a,b)=1\implies n\frac{a}{b}\not\in\Bbb{Z}~~\forall~~0\lt n\lt b~\land~n\in\Bbb{Z}

#NumberTheory #GreatestCommonDivisor(GCD/HCF/GCF) #Proofs #Summation #FloorFunction

Note by Prasun Biswas
6 years, 1 month ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Use the fact that ⌊x⌋=x−{x}\lfloor x\rfloor=x-\{x\} to rewrite as

∑k=1b−1⌊kab⌋=ab∑j=1b−1j−∑k=1b−1{kab}=a(b−1)2−∑k=1b−1{kab}.\sum_{k=1}^{b-1}\left\lfloor\dfrac{ka}{b}\right\rfloor=\dfrac a b\sum_{j=1}^{b-1} j-\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}=\dfrac{a(b-1)}{2}-\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}.

Now

∑k=1b−1{kab}=∑k=1(b−1)/2({kab}+{(b−k)ab})=∑k=1(b−1)/2({kab}+{a−kab}).\sum_{k=1}^{b-1}\left\{\dfrac{ka}{b}\right\}=\sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{\dfrac{(b-k)a}{b}\right\}\right)=\sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}\right).

Here no term can be zero since na/bna/b is not integer for 1≤n<b1\le n<b provided that (a,b)=1(a,b)=1. So ∀k∈[1,(b−1)/2]\forall k\in[1, (b-1)/2]

{kab}+{a−kab}=1  ⟹  ∑k=1(b−1)/2({kab}+{a−kab})=∑k=1(b−1)/21=b−12\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}=1\implies \sum_{k=1}^{(b-1)/2}\left(\left\{\dfrac{ka}{b}\right\}+\left\{a-\dfrac{ka}{b}\right\}\right)=\sum_{k=1}^{(b-1)/2}1=\dfrac{b-1}{2}

and we're, um, done.

Jubayer Nirjhor - 6 years, 1 month ago

Log in to reply

Very well done....

Vighnesh Raut - 6 years, 1 month ago

Consider b=8b=8 and a=9a=9. We have gcd⁡(a,b)=1\gcd(a,b)=1 but (b−1)2\frac{(b-1)}{2} is not a positive integer ≥1\geq 1. Then, what does the sum ∑k=1(b−1)/2(1)\displaystyle\sum_{k=1}^{(b-1)/2}(1) mean?

Prasun Biswas - 6 years, 1 month ago

Log in to reply

The sum is to b−1 b-1, as in ⌊(b−1)ab⌋ \lfloor (b-1) \frac{ a}{b} \rfloor , and not to b−12 \frac{ b-1}{2} as you had it.

Calvin Lin Staff - 6 years, 1 month ago

Warning: there is a huge hint below.

na(mod  b)na (\mod b) is pairwise distinct for n=1,2,...,bn=1, 2, ..., b. Proof: The opposite is false by Pigeonhole Principle. Hence if we limit nn to 1,2,3,...,b−11, 2, 3, ..., b-1 the possible remainders are 1,2,...,b−11, 2, ..., b-1, once each.

From here we can find the sum of the b−1b-1 fractional parts of n•ab,n=1,2,...,b−1n•\frac {a}{b}, n=1, 2, ..., b-1. We know their sum, so we know the sum of their floors.

Joel Tan - 6 years, 1 month ago

Log in to reply

There's an easier approach (though essentially based on the same idea).

Hint: Heads and tails.

Calvin Lin Staff - 6 years, 1 month ago
×

Problem Loading...

Note Loading...

Set Loading...