Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
Is there an easier way? –  ShreevatsaR Sep 21 '10 at 12:44
2  
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
2  
it always makes me a bit sad when I can't see these kinds of solutions! –  anon Sep 21 '10 at 17:13
1  
@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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.