MathLinks :: View topic

Art of Problem Solving \| News \| Galleries \| Blogs \| About \| Home
	$LaTeX Help$

Advanced Section

College Playground

International Mathematical Olympiad

National Forums

Galleries

Memberlist

Usergroups

The time now is Sat Nov 21, 2009 1:15 am
All times are UTC + 2

View posts since last visit
View unanswered posts

I 10

Post new topic Reply to topic

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Functions in Number Theory » Floor Function and Fractional Part Function

3 Posts • Page 1 of 1

Author

Message

Peter
Birch & Swinnerton Dyer

Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent

I 10
AMM, Problem 10346, David Doster

Show that for all primes $p$ , $\sum^{p-1}_{k=1}\left \lfloor \frac{k^{3}}{p}\right \rfloor =\frac{(p+1)(p-1)(p-2)}{4}.$

Posted: Fri May 25, 2007 2:25 am

Profile PM WWW Album

darij grinberg
Birch & Swinnerton Dyer

Offline
Joined: 10 Feb 2004
Posts: 5763
Location: Karlsruhe / Munich

Re: I 10
AMM, Problem 10346, David Doster

Peter wrote:

Show that for all primes $p$ , $\sum^{p-1}_{k=1}\left \lfloor \frac{k^{3}}{p}\right \rfloor =\frac{(p+1)(p-1)(p-2)}{4}.$

This is also a problem from the German National Olympiad (DeMO, 4th round) 2002, and I have written a solution for the op02 project. Since op02 does not seem to have survived, I am publishing the solution here:

We start by showing something really trivial:

Lemma 1. For any integer $n$ and any non-integer real number $a$ , we have $\lfloor a \rfloor+\lfloor n-a \rfloor = n-1$ .

Proof. Since $a$ is not an integer, we have $a=\lfloor a \rfloor+q$ for some real $q$ with $0<q<1$ . Hence, $n-a = n-\left(\lfloor a \rfloor+q\right) = \left(n-1-\lfloor a \rfloor\right)+\left(1-q\right)$ . Hereby, $0<1-q<1$ ; thus, $\lfloor n-a \rfloor = n-1-\lfloor a \rfloor$ , what yields Lemma 1.

For every $k$ such that $1\leq k\leq p-1$ , define the number $a = \frac{k^{3}}{p}$ . This number $a$ is trivially non-integer, since $k^{3}$ is not divisible by $p$ because $p$ is a prime and $k<p$ . Also, set $n = p^{2}-3pk+3k^{2}$ . Then, Lemma 1 yields

$\left\lfloor \frac{k^{3}}{p}\right\rfloor+\left\lfloor \left(p^{2}-3pk+3k^{2}\right)-\frac{k^{3}}{p}\right\rfloor = \left(p^{...$ .

This simplifies to

$\left\lfloor \frac{k^{3}}{p}\right\rfloor+\left\lfloor \frac{\left(p-k\right)^{3}}{p}\right\rfloor = p^{2}-3pk+3k^{2}-1$ .

Now, the problem is straightforward:

$2\sum^{p-1}_{k=1}\left \lfloor \frac{k^{3}}{p}\right \rfloor = \sum^{p-1}_{k=1}\left \lfloor \frac{k^{3}}{p}\right \rfloor+\s...$
$= \sum^{p-1}_{k=1}\left( \left\lfloor \frac{k^{3}}{p}\right\rfloor+\left\lfloor \frac{\left(p-k\right)^{3}}{p}\right\rfloor \...$
$= \left(p-1\right)p^{2}-3p \sum^{p-1}_{k=1}k+3 \sum^{p-1}_{k=1}k^{2}-\left(p-1\right)$
$= \left(p-1\right)p^{2}-3p \frac{\left(p-1\right)p}{2}+3 \frac{\left(p-1\right)p\left(2p-1\right)}{6}-\left(p-1\right) = \fra...$ ,

so that

$\sum^{p-1}_{k=1}\left \lfloor \frac{k^{3}}{p}\right \rfloor = \frac{\left(p-2\right)\left(p-1\right)\left(p+1\right)}{4}$ ,

completing the solution.

darij

Posted: Fri May 25, 2007 2:25 am

Profile PM WWW

ideahitme
Hodge Conjecture

Offline
Joined: 28 Nov 2003
Posts: 85

Re: I 10
AMM, Problem 10346, David Doster

Peter wrote:

Show that for all primes $p$ ,
$\sum^{p-1}_{k=1}\left\lfloor\frac{k^{3}}{p}\right\rfloor =\frac{(p+1)(p-1)(p-2)}{4}.$

The same idea, but with different style.

Lemma. Let $\alpha,\beta\in\mathbb{R}$ with $\alpha+\beta=n\in\mathbb{Z}$ . Then, we have
$\lfloor\alpha\rfloor+\lfloor\beta\rfloor =\begin{cases}\alpha+\beta &\left(\alpha\in\mathbb{Z}\right),\\ \alpha+\beta-1 &...$

Proof. In case when $\alpha\in\mathbb{Z}$ , we also have $\beta\in\mathbb{Z}$ . Then, we obtain $\lfloor\alpha\rfloor =\alpha$ and $\lfloor\beta\rfloor =\beta$ . Hence, $\lfloor\alpha\rfloor+\lfloor\beta\rfloor =\alpha+\beta$ . Now, we consider the case when $\alpha\not\in\mathbb{Z}$ . Since $\alpha+\beta\in\mathbb{Z}$ , we also have $\beta\not\in\mathbb{Z}$ . Since $\alpha$ is not an integer, one may write $a = k+q$ , where $k =\lfloor\alpha\rfloor\in\mathbb{Z}$ and $q\in (0,1)$ . Observer that $\beta = n-\alpha = (n-k-1)+(1-q)$ . Since $n-k-1\in\mathbb{Z}$ and $1-q\in (0,1)$ , this means that $\lfloor\beta\rfloor = n-k-1$ . It follows that
$\lfloor\alpha\rfloor+\lfloor\beta\rfloor = k+(n-k-1) = n-1 =\alpha+\beta-1 .$

Lemma. Whenever $k\in\{ 1,\cdots, p-1\}$ , we obtain
$\left\lfloor\frac{k^{3}}{p}\right\rfloor+\left\lfloor\frac{\left(p-k\right)^{3}}{p}\right\rfloor =\frac{k^{3}}{p}+\frac{\left...$

Proof. Let $k\in\{ 1,\cdots, p-1\}$ . Since $p$ is prime, we see that $k^{3}$ is not divisible by $p$ so that $\frac{k^{3}}{p}$ is not an integer. Furthermore, from the congruence $k^{3}+(p-k)^{3}\equiv k^{3}-k^{3}\equiv 0\; (mod\; p)$ , we see that
$\frac{k^{3}}{p}+\frac{\left(p-k\right)^{3}}{p}\in\mathbb{Z}.$
The above proposition yields the desired result.

Now, we compute the summation. By symmetry, we obtain
$\sum^{p-1}_{k = 1}\frac{k^{3}}{p}=\sum^{p-1}_{k = 1}\frac{(p-k)^{3}}{p}.$
and
$\sum^{p-1}_{k = 1}\left\lfloor\frac{k^{3}}{p}\right\rfloor =\sum^{p-1}_{k = 1}\left\lfloor\frac{(p-k)^{3}}{p}\right\rfloor.$
Applying the above results we proved, we compute

$\sum^{p-1}_{k = 1}\left\lfloor\frac{k^{3}}{p}\right\rfloor\\ =\frac{1}{2}\left(\sum^{p-1}_{k = 1}\left\lfloor\frac{k^{3}}{p}\...$

_________________
It gives me the same pleasure when someone else proves a good theorem as when I do it myself. <E. Landau>

Posted: Wed Aug 29, 2007 9:02 am

Profile PM

3 Posts • Page 1 of 1

Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Functions in Number Theory » Floor Function and Fractional Part Function

Post new topic Reply to topic

Jump to:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008