5
$\begingroup$

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$.

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

3 Answers 3

Reset to default
8
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is there an easier way? $\endgroup$
    – ShreevatsaR
    Sep 21, 2010 at 12:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Sep 21, 2010 at 14:06
  • 2
    $\begingroup$ it always makes me a bit sad when I can't see these kinds of solutions! $\endgroup$
    – anon
    Sep 21, 2010 at 17:13
  • 1
    $\begingroup$ @Shree: Perhaps my answer is 'simpler'. $\endgroup$
    – Aryabhata
    Sep 21, 2010 at 22:09
6
$\begingroup$

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 $$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.