# Proving $\Bigl[\frac{8n+13}{25}\Bigr] - \Bigl[\frac{n-12 - \Bigl[\frac{n-17}{25}\Bigr]}{3}\Bigr]$ is independent of $n$

This an Exercise from Apostol's analytic number theory. I have been struggling with this problem for quite some time. Looks elementary though.

The question is to prove that this quantity

$$\Biggl[\frac{8n+13}{25}\Biggr] - \Biggl[\frac{n-12 - \Bigl[\frac{n-17}{25}\Bigr]}{3}\Biggr]$$ is independent of $n$.

-
BTW, [x] means "integer part". – kennytm Sep 21 '10 at 15:20
yes it means the integral part – anonymous Sep 21 '10 at 15:32
@Chandru1, maybe you could explain the notation in the question itself so that readers have to read just one place! :) – Mariano Suárez-Alvarez Sep 21 '10 at 16:08

There is a simpler way (in terms of manual computations) than the other answer.

We use the following facts:

1)

If $A$ is an integer then $$A -[x] = [A-x + \delta]$$ where $\delta = 0$ if $x$ is an integer, and $\delta = 1$ otherwise.

2)

If $n > 1$ is a positive integer then $$[\frac{[x]}{n}] = [\frac{x}{n}]$$

Using this we see that

$$[\frac{n-12 - [\frac{n-17}{25}]}{3}] = [\frac{n-12-\frac{(n-17)}{25}+\delta}{3}]$$

where $\delta = 0$ iff $n=17 \mod 25$.

$$= [\frac{24n-283+25\delta}{75}]$$

Let $24n+39 = r \mod 75$ where $0 \leq r < 75$.

Notice that $r$ must be divisible by $3$. Thus $0 \leq r \leq 72$.

Suppose $24n+39 = 75m+r$, then we have that

$$[\frac{8n+13}{25}] = [\frac{24n+39}{75}] = m$$

and $$[\frac{24n-283+25\delta}{75}] = [\frac{75m+r-375+53+25\delta}{75}]$$ = $$m-5 + [\frac{r + 53 + 25\delta}{75}]$$

Now $\delta = 0$ iff $n=17 \mod 25$ iff $r = 72$.

Thus for $r < 72$, $\delta = 1$, for which we have

$$[\frac{r + 53 + 25\delta}{75}] = [\frac{r + 53 + 25}{75}] = 1$$

For $r = 72$, we have $\delta=0$ for which we have

$$[\frac{r + 53 + 25\delta}{75}] = [\frac{r + 53}{75}] = 1$$

Thus the whole expression is

$$m - ((m-5)+1) = 4$$

-

Write $n=25m+r$ with $0\leq r<25$, and replace in the equation.You'll see that the result only depends on $r$. Now make the $25$ computations corresponding to each of the possible values of $r$, and check that the result is $4$ in all those finitely many cases.

-
Is there an easier way? – ShreevatsaR Sep 21 '10 at 12:44
My vague guess is that the problem is intended to be solved this way. That is, the point of the exercise is to realize that this general algorithm exists. – Qiaochu Yuan Sep 21 '10 at 14:06
it always makes me a bit sad when I can't see these kinds of solutions! – anon Sep 21 '10 at 17:13
@Shree: Perhaps my answer is 'simpler'. – Aryabhata Sep 21 '10 at 22:09

Using Apostol notation notice that $0\le\{\frac{n-17}{25}\}\le\frac{24}{25}$

So let $g(n)=\frac{8n+13}{25}-\frac{n-12-[\frac{n-17}{25}]}{3}$. Simplifying we see that $4-\frac{2}{75}\le g(n) \le4+\frac{22}{75}$

Now let $f(n)=[\frac{8n+13}{25}]-[\frac{n-12-[\frac{n-17}{25}]}{3}]=g(n)-{\frac{8n+13}{25}}+{\frac{n-12-[\frac{n-17}{25}]}{3}}$ and you get $4-\frac{74}{75}\le f(n)\le4+\frac{72}{75}$ so $f(n)=4$.

-