sum of fractions $(modp)$

For discussing Olympiad Level Number Theory problems
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
sum of fractions $(modp)$

Unread post by mutasimmim » Tue Aug 26, 2014 11:19 pm

Compute $\sum\lfloor\frac{k^3}{p}\rfloor$ for nonnegative integers $r<p$ and an odd prime $p$.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: sum of fractions $(modp)$

Unread post by Masum » Wed Sep 03, 2014 11:36 am

ok, but where is $r$?
One one thing is neutral in the universe, that is $0$.

mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am

Re: sum of fractions $(modp)$

Unread post by mutasimmim » Wed Sep 03, 2014 12:00 pm

Sorry, that would be $ k $ instead of $ r $.

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: sum of fractions $(modp)$

Unread post by Nirjhor » Wed Sep 03, 2014 4:46 pm

Let \(0\le \{x\}<1\) be the fractional part of \(x\) so that \(x=\lfloor x\rfloor+\{x\}\). Now for \(1\le k\le p-1\) we have
\[\left\{\dfrac{k^3}{p}\right\}+\left\{\dfrac{\left(p-k\right)^3}{p}\right\}=\left\{\dfrac{k^3}{p}\right\}+\left\{p^2+3k^2-3kp-\dfrac{k^3}{p}\right\}=1.\] Therefore \[\begin{eqnarray}
\sum_{k=1}^{p-1}\left\lfloor\dfrac{k^3}{p}\right\rfloor &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \sum_{k=1}^{p-1}\left\{\dfrac{k^3}{p}\right\} \\ \\ &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \dfrac{1}{2}\sum_{k=1}^{p-1} \left(\left\{\dfrac{k^3}{p}\right\}+\left\{\dfrac{\left(p-k\right)^3}{p}\right\}\right) \\ \\ &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \sum_{k=1}^{p-1} 1\\ \\ &=& \dfrac{p(p-1)^2}{4} -\dfrac{p-1}{2} \\ \\ &=& \boxed{\dfrac{\left(p^2-1\right)\left(p-2\right)}{4}}
\end{eqnarray}\]
What does \(\bmod~p\) have to do with it?
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: sum of fractions $(modp)$

Unread post by *Mahi* » Wed Sep 03, 2014 9:09 pm

mutasimmim wrote:Compute $\sum\left \lfloor\dfrac{k^3}{p} \right \rfloor$ for nonnegative integers $r<p$ and an odd prime $p$.
If possible, please use \dfrac instead of \frac if you are writing an inline fraction with even smaller stuff in the numerator/denominator. I though the $k^3$ to be $k^2$ :|
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am

Re: sum of fractions $(modp)$

Unread post by mutasimmim » Wed Sep 03, 2014 9:32 pm

Ok, I will.

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: sum of fractions $(modp)$

Unread post by asif e elahi » Thu Sep 04, 2014 5:12 pm

Nirjhor wrote:Let \(0\le \{x\}<1\) be the fractional part of \(x\) so that \(x=\lfloor x\rfloor+\{x\}\). Now for \(1\le k\le p-1\) we have
\[\left\{\dfrac{k^3}{p}\right\}+\left\{\dfrac{\left(p-k\right)^3}{p}\right\}=\left\{\dfrac{k^3}{p}\right\}+\left\{p^2+3k^2-3kp-\dfrac{k^3}{p}\right\}=1.\] Therefore \[\begin{eqnarray}
\sum_{k=1}^{p-1}\left\lfloor\dfrac{k^3}{p}\right\rfloor &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \sum_{k=1}^{p-1}\left\{\dfrac{k^3}{p}\right\} \\ \\ &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \dfrac{1}{2}\sum_{k=1}^{p-1} \left(\left\{\dfrac{k^3}{p}\right\}+\left\{\dfrac{\left(p-k\right)^3}{p}\right\}\right) \\ \\ &=& \sum_{k=1}^{p-1}\dfrac{k^3}{p} - \sum_{k=1}^{p-1} 1\\ \\ &=& \dfrac{p(p-1)^2}{4} -\dfrac{p-1}{2} \\ \\ &=& \boxed{\dfrac{\left(p^2-1\right)\left(p-2\right)}{4}}
\end{eqnarray}\]
What does \(\bmod~p\) have to do with it?
${\dfrac{\left(p^2-1\right)\left(p-2\right)}{4}}\equiv \dfrac{p+1}{2}$ (mod $p$)

Nirjhor
Posts:136
Joined:Thu Aug 29, 2013 11:21 pm
Location:Varies.

Re: sum of fractions $(modp)$

Unread post by Nirjhor » Thu Sep 04, 2014 5:23 pm

The question asks to find the sum only, not \(\bmod~p\).
- What is the value of the contour integral around Western Europe?

- Zero.

- Why?

- Because all the poles are in Eastern Europe.


Revive the IMO marathon.

mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am

Re: sum of fractions $(modp)$

Unread post by mutasimmim » Fri Sep 05, 2014 7:07 pm

Sorry, I wrote $(mod p)$ by mistake, I only meant to determine the sum.

Post Reply